DBScholar

Back to papers

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
h6107e5cd35b0ac92
Venue
SIGMOD
Year
1988
Pagerank
0.0003136296
Overall Rank
119 | 99.21%
DOI
10.1145/50202.50205

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{muralikrishna_sigmod88,
        title = {{Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries}},
        author = {Muralikrishna, M. and DeWitt, David J.},
        series = {{SIGMOD} '88},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/50202.50205},
        url = {https://dl.acm.org/doi/10.1145/50202.50205},
        year = {1988}
}

Incoming Citations (Sorted by Pagerank)

Showing 48 of 48 citing papers.

Rank Citing Paper Year Venue Pagerank
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.0004772731
79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00036476265
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033884854
181 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00026384065
232 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.0002378554
255 The History of Histograms (abridged) 2003 VLDB 0.00022974524
272 An Overview of Query Optimization in Relational Systems 1998 PODS 0.0002251422
284 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00022205848
286 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.00022112534
371 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00019822444
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.0001971778
454 Self-tuning Histograms: Building Histograms Without Looking at Data 1999 SIGMOD 0.00017955913
569 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD 0.00016244162
643 Evaluating Top-k Selection Queries 1999 VLDB 0.0001521012
644 Exploiting Statistics on Query Expressions for Optimization 2002 SIGMOD 0.00015209065
785 A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data 1997 VLDB 0.00013999898
806 Universality of Serial Histograms 1993 VLDB 0.00013786471
969 Recovering Information from Summary Data 1997 VLDB 0.00012788914
1,004 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00012588952
1,065 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00012202293
1,142 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00011843746
1,258 Sampling-Based Query Re-Optimization 2016 SIGMOD 0.00011308863
1,462 Substring Selectivity Estimation 1999 PODS 0.00010578962
1,574 Reducing the Braking Distance of an SQL Query Engine 1998 VLDB 0.00010190239
1,608 SciBORQ: Scientific data management with Bounds On Runtime and Quality 2011 CIDR 0.00010085907
1,687 Global Optimization of Histograms 2001 SIGMOD 9.8614576e-05
1,892 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.4150583e-05
2,827 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB 7.9637452e-05
2,975 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.7905662e-05
2,984 Optimizing Boolean Expressions in Object Bases 1992 VLDB 7.780464e-05
3,361 Conditional Selectivity for Statistics on Query Expressions 2004 SIGMOD 7.3726415e-05
3,646 Optimal Histograms for Hierarchical Range Queries (Extended Abstract) 2000 PODS 7.1368554e-05
3,969 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.8874168e-05
4,118 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.7927394e-05
4,463 DigitHist: a Histogram-Based Data Summary with Tight Error Bounds 2017 VLDB 6.5861255e-05
4,546 Random Sampling from Pseudo-Ranked B+ Trees 1992 VLDB 6.5406658e-05
4,651 Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach 2006 VLDB 6.4836419e-05
5,007 Fast Algorithms For Hierarchical Range Histogram Construction 2002 PODS 6.3156906e-05
5,200 Exact Cardinality Query Optimization with Bounded Execution Cost 2019 SIGMOD 6.2303304e-05
6,169 Modeling skewed distributions using multifractals and the '80-20 law' 1996 VLDB 5.8600493e-05
7,324 Distributed Top-N Query Processing with Possibly Uncooperative Local Systems 2003 VLDB 5.5512232e-05
7,496 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS 5.5081355e-05
9,396 Optimality and Scalability in Lattice Histogram Construction 2009 VLDB 5.1843659e-05
9,825 Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects 2010 SIGMOD 5.1233734e-05
9,917 Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects 2025 VLDB 5.1079647e-05
10,062 SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning 2025 SIGMOD 5.0851868e-05
13,137 Searching on the Secondary Structure of Protein Sequences 2002 VLDB 4.9769913e-05
13,140 A One-Pass Aggregation Algorithm with the Optimal Buffer Size in Multidimensional OLAP 2002 VLDB 4.9769913e-05
Previous Page 1 / 1 Next

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.0023943337
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0019923528
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.00081200096
36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00047864281
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 7,639 Consistent Histograms In The Presence of Distinct Value Counts 2009 VLDB
2 242 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB
3 9,151 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD
4 275 Optimal Histograms with Quality Guarantees 1998 VLDB
5 371 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD
6 867 Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes 2000 SIGMOD
7 284 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD
8 743 Dynamic Multidimensional Histograms 2002 SIGMOD
9 37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD
10 1,078 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD