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: 2374
Venue: SIGMOD
Year: 1988
Pagerank: 0.00046317654
Overall Rank: 114 | 99.21%
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
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051431888
133	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00043220055
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041819767
250	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00030640525
325	The History of Histograms (abridged)	2003	VLDB	0.00027398081
328	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027301497
373	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00025354685
430	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00023406426
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022796106
512	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00021385343
523	Recovering Information from Summary Data	1997	VLDB	0.00021101376
526	A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data	1997	VLDB	0.00021046587
527	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00020862475
680	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018193263
786	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.00016624743
801	Universality of Serial Histograms	1993	VLDB	0.00016440976
802	Evaluating Top-k Selection Queries	1999	VLDB	0.00016440813
1,111	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.0001389881
1,116	Global Optimization of Histograms	2001	SIGMOD	0.00013863484
1,126	Dynamic Maintenance of Wavelet-Based Histograms	2000	VLDB	0.0001381102
1,379	Substring Selectivity Estimation	1999	PODS	0.00012280308
1,699	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010848882
1,735	SciBORQ: Scientific data management with Bounds On Runtime and Quality	2011	CIDR	0.00010713691
1,756	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00010659753
1,780	Reducing the Braking Distance of an SQL Query Engine	1998	VLDB	0.00010558417
2,369	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	8.9462051e-05
2,455	Optimizing Boolean Expressions in Object Bases	1992	VLDB	8.7667904e-05
2,978	Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension	1995	VLDB	7.7848117e-05
3,516	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.018912e-05
3,621	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS	6.9022467e-05
3,656	Conditional Selectivity for Statistics on Query Expressions	2004	SIGMOD	6.8712579e-05
3,896	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB	6.6526869e-05
3,965	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB	6.5786424e-05
4,018	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS	6.5250686e-05
4,433	Selectivity Estimation for Fuzzy String Predicates in Large Data Sets	2005	VLDB	6.1852739e-05
4,718	Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach	2006	VLDB	5.9664602e-05
4,815	DigitHist: a Histogram-Based Data Summary with Tight Error Bounds	2017	VLDB	5.8978716e-05
5,696	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	5.367449e-05
5,967	Modeling skewed distributions using multifractals and the '80-20 law'	1996	VLDB	5.247088e-05
7,134	Distributed Top-N Query Processing with Possibly Uncooperative Local Systems	2003	VLDB	4.8174665e-05
7,573	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	4.7034681e-05
9,059	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	4.3997447e-05
9,508	Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects	2010	SIGMOD	4.3300131e-05
9,727	SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning	2025	SIGMOD	4.2901665e-05
10,837	Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects	2025	VLDB	4.1905499e-05
12,657	Searching on the Secondary Structure of Protein Sequences	2002	VLDB	4.1905499e-05
12,660	A One-Pass Aggregation Algorithm with the Optimal Buffer Size in Multidimensional OLAP	2002	VLDB	4.1905499e-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.0040465394
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032118946
5	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0018380955
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080571183

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,725	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	4.6621296e-05
270	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029648047
8,893	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD	4.4232868e-05
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002737538
512	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00021385343
995	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00014745185
328	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027301497
849	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015919478
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
1,240	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00013090678