Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries

Summary: Equi-depth multi-dimensional histograms for estimating selectivity of multi-attribute queries. Proposes a practical two-dimensional algorithm extendable to higher dimensions, a compact in-memory histogram structure, two estimation schemes, and a low-cost sampling method; experiments confirm accuracy and efficiency gains. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2373
Venue: SIGMOD
Year: 1988
Pagerank: 0.00046148737
Overall Rank: 116 | 99.20%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. M. Muralikrishna
2. David J. DeWitt

Incoming Citations (Sorted by Pagerank)

Showing 48 of 48 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051315959
134	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00042452811
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041786333
252	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00030632263
325	The History of Histograms (abridged)	2003	VLDB	0.00027378328
327	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027308479
372	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00025354779
449	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00022846068
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022734812
512	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00021380733
523	Recovering Information from Summary Data	1997	VLDB	0.00021089782
526	A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data	1997	VLDB	0.00021044221
529	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00020828852
684	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018179769
790	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.0001663283
805	Evaluating Top-k Selection Queries	1999	VLDB	0.00016437265
808	Universality of Serial Histograms	1993	VLDB	0.00016432772
1,114	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.00013901031
1,120	Global Optimization of Histograms	2001	SIGMOD	0.00013856211
1,127	Dynamic Maintenance of Wavelet-Based Histograms	2000	VLDB	0.00013819179
1,379	Substring Selectivity Estimation	1999	PODS	0.00012286879
1,703	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010836769
1,758	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00010655546
1,789	Reducing the Braking Distance of an SQL Query Engine	1998	VLDB	0.00010555087
1,909	SciBORQ: Scientific data management with Bounds On Runtime and Quality	2011	CIDR	0.00010121304
2,377	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	8.9402115e-05
2,455	Optimizing Boolean Expressions in Object Bases	1992	VLDB	8.7770449e-05
2,974	Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension	1995	VLDB	7.789769e-05
3,511	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.0254052e-05
3,619	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS	6.9084829e-05
3,651	Conditional Selectivity for Statistics on Query Expressions	2004	SIGMOD	6.8768678e-05
3,893	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB	6.6584217e-05
3,966	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB	6.580483e-05
4,017	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS	6.524501e-05
4,438	Selectivity Estimation for Fuzzy String Predicates in Large Data Sets	2005	VLDB	6.1898903e-05
4,711	Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach	2006	VLDB	5.9790683e-05
4,831	DigitHist: a Histogram-Based Data Summary with Tight Error Bounds	2017	VLDB	5.8924198e-05
5,685	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	5.3717535e-05
5,982	Modeling skewed distributions using multifractals and the '80-20 law'	1996	VLDB	5.2446136e-05
7,136	Distributed Top-N Query Processing with Possibly Uncooperative Local Systems	2003	VLDB	4.8220711e-05
7,581	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	4.7057641e-05
9,061	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	4.4039656e-05
9,507	Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects	2010	SIGMOD	4.3341665e-05
9,728	SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning	2025	SIGMOD	4.2942813e-05
10,833	Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects	2025	VLDB	4.1945683e-05
12,648	Searching on the Secondary Structure of Protein Sequences	2002	VLDB	4.1945683e-05
12,651	A One-Pass Aggregation Algorithm with the Optimal Buffer Size in Multidimensional OLAP	2002	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0040449103
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032169493
5	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0018397217
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080435857

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,728	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	4.666214e-05
269	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029656549
8,893	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD	4.4275272e-05
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00027358981
512	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00021380733
996	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00014741524
327	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027308479
852	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015941524
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
1,241	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00013097578