DBScholar

Back to papers

Improved Histograms for Selectivity Estimation of Range Predicates

Summary: Proposes a systematic taxonomy of histograms for range-predicate selectivity estimation, unifying prior types and enabling novel design combinations. Demonstrates sampling to reduce histogram construction cost and empirically evaluates types on range queries to identify the best performers. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h59bad86d8e781ff0
Venue
SIGMOD
Year
1996
Pagerank
0.00047731453
Overall Rank
37 | 99.76%
DOI
10.1145/233269.233342

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{poosala_sigmod96,
        title = {{Improved Histograms for Selectivity Estimation of Range Predicates}},
        author = {Poosala, Viswanath and Ioannidis, Yannis E. and Haas, Peter J. and Shekita, Eugene J.},
        series = {{SIGMOD} '96},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/233269.233342},
        url = {https://dl.acm.org/doi/10.1145/233269.233342},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 112 citing papers.

Rank Citing Paper Year Venue Pagerank
2,236 Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search? 2019 SIGMOD 8.7776298e-05
2,242 Automatic Categorization of Query Results 2004 SIGMOD 8.7685327e-05
2,303 Selectivity Estimation in Extensible Databases - A Neural Network Approach 1998 VLDB 8.6708797e-05
2,354 Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries 2008 VLDB 8.5896515e-05
2,368 Statistical Synopses for Graph-Structured XML Databases 2002 SIGMOD 8.5622073e-05
2,415 Using Probabilistic Models for Data Management in Acquisitional Environments 2005 CIDR 8.4985276e-05
2,688 Quality and Efficiency in Kernel Density Estimates for Large Data 2013 SIGMOD 8.1265396e-05
2,787 EVA: A Symbolic Approach to Accelerating Exploratory Video Analytics with Materialized Views 2022 SIGMOD 8.0158999e-05
3,052 A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021 SIGMOD 7.7052471e-05
3,092 Compressing Historical Information in Sensor Networks 2004 SIGMOD 7.6563998e-05
3,361 Conditional Selectivity for Statistics on Query Expressions 2004 SIGMOD 7.3760492e-05
3,562 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 7.2046519e-05
3,613 Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees 2020 VLDB 7.162283e-05
3,644 Optimal Histograms for Hierarchical Range Queries (Extended Abstract) 2000 PODS 7.1399991e-05
3,741 FACE: A Normalizing Flow based Cardinality Estimator 2022 VLDB 7.0594076e-05
3,851 Graph-Based Synopses for Relational Selectivity Estimation 2006 SIGMOD 6.9785886e-05
3,874 Accelerating Approximate Aggregation Queries with Expensive Predicates 2021 VLDB 6.953738e-05
3,967 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.8905715e-05
4,117 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.7958711e-05
4,267 Buffer Pool Aware Query Optimization 2005 CIDR 6.6967071e-05
4,457 Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian Process 2022 SIGMOD 6.5913732e-05
4,462 DigitHist: a Histogram-Based Data Summary with Tight Error Bounds 2017 VLDB 6.5880099e-05
4,659 Automated Statistics Collection in DB2 UDB 2004 VLDB 6.4822228e-05
4,932 Space efficiency in Synopsis construction algorithms 2005 VLDB 6.3483816e-05
4,933 A Comparison of Selectivity Estimators for Range Queries on Metric Attributes 1999 SIGMOD 6.3474817e-05
5,004 Fast Algorithms For Hierarchical Range Histogram Construction 2002 PODS 6.3186165e-05
5,044 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 6.30014e-05
5,045 KLL± Approximate Quantile Sketches over Dynamic Datasets 2021 VLDB 6.3001279e-05
5,622 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 6.0614658e-05
5,652 Building Wavelet Histograms on Large Data in MapReduce 2012 VLDB 6.0515502e-05
5,851 A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets 2006 VLDB 5.9718136e-05
5,902 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9536872e-05
6,182 Evaluating Interactive Data Systems: Workloads, Metrics, and Guidelines 2018 SIGMOD 5.8588933e-05
6,189 VergeDB: A Database for IoT Analytics on Edge Devices 2021 CIDR 5.8568233e-05
6,223 A Forward Scan based Plane Sweep Algorithm for Parallel Interval Joins 2017 VLDB 5.8457826e-05
6,557 Optimal Splitters for Temporal and Multi-version Databases 2013 SIGMOD 5.7498216e-05
6,721 Near-Optimal Distributed Band-Joins through Recursive Partitioning 2020 SIGMOD 5.6981399e-05
6,791 dbET: Execution Time Distribution-based Plan Selection 2023 SIGMOD 5.6811782e-05
7,247 Depth Estimation for Ranking Query Optimization 2007 VLDB 5.5748328e-05
7,332 Selectivity Functions of Range Queries are Learnable* 2022 SIGMOD 5.5499953e-05
7,364 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 5.5418075e-05
7,493 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS 5.5103311e-05
7,512 Compact Histograms for Hierarchical Identifiers 2006 VLDB 5.504973e-05
7,561 Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations 2015 VLDB 5.4958573e-05
7,633 Consistent Histograms In The Presence of Distinct Value Counts 2009 VLDB 5.4792473e-05
8,166 Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints 2020 SIGMOD 5.3849926e-05
8,223 PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees 2025 SIGMOD 5.3751366e-05
8,325 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 5.3540828e-05
8,576 Histograms as a Side Effect of Data Movement for Big Data 2014 SIGMOD 5.3111243e-05
9,142 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 5.220581e-05
Previous Page 2 / 3 Next

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Previous Page 1 / 1 Next

Semantically Similar Papers