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.00047654188
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,247 Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search? 2019 SIGMOD 8.7591557e-05
2,260 Automatic Categorization of Query Results 2004 SIGMOD 8.7355244e-05
2,310 Selectivity Estimation in Extensible Databases - A Neural Network Approach 1998 VLDB 8.6493038e-05
2,362 Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries 2008 VLDB 8.5601252e-05
2,378 Statistical Synopses for Graph-Structured XML Databases 2002 SIGMOD 8.5315761e-05
2,428 Using Probabilistic Models for Data Management in Acquisitional Environments 2005 CIDR 8.466877e-05
2,702 Quality and Efficiency in Kernel Density Estimates for Large Data 2013 SIGMOD 8.0958339e-05
2,792 EVA: A Symbolic Approach to Accelerating Exploratory Video Analytics with Materialized Views 2022 SIGMOD 7.9895218e-05
3,060 A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021 SIGMOD 7.6828463e-05
3,106 Compressing Historical Information in Sensor Networks 2004 SIGMOD 7.6276487e-05
3,371 Conditional Selectivity for Statistics on Query Expressions 2004 SIGMOD 7.3493132e-05
3,555 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 7.1877332e-05
3,611 Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees 2020 VLDB 7.1443694e-05
3,653 Optimal Histograms for Hierarchical Range Queries (Extended Abstract) 2000 PODS 7.1149642e-05
3,740 FACE: A Normalizing Flow based Cardinality Estimator 2022 VLDB 7.0398782e-05
3,747 Accelerating Approximate Aggregation Queries with Expensive Predicates 2021 VLDB 7.0351475e-05
3,858 Graph-Based Synopses for Relational Selectivity Estimation 2006 SIGMOD 6.9543709e-05
3,977 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.8707656e-05
4,138 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.7706361e-05
4,260 Buffer Pool Aware Query Optimization 2005 CIDR 6.6824533e-05
4,479 Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian Process 2022 SIGMOD 6.5665703e-05
4,480 DigitHist: a Histogram-Based Data Summary with Tight Error Bounds 2017 VLDB 6.566036e-05
4,672 Automated Statistics Collection in DB2 UDB 2004 VLDB 6.4593469e-05
4,744 KLL± Approximate Quantile Sketches over Dynamic Datasets 2021 VLDB 6.4278327e-05
4,956 A Comparison of Selectivity Estimators for Range Queries on Metric Attributes 1999 SIGMOD 6.326039e-05
4,962 Space efficiency in Synopsis construction algorithms 2005 VLDB 6.3244317e-05
5,031 Fast Algorithms For Hierarchical Range Histogram Construction 2002 PODS 6.2950911e-05
5,056 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 6.282339e-05
5,636 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 6.0385837e-05
5,664 Building Wavelet Histograms on Large Data in MapReduce 2012 VLDB 6.0293278e-05
5,864 A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets 2006 VLDB 5.9498215e-05
5,911 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9338021e-05
6,195 Evaluating Interactive Data Systems: Workloads, Metrics, and Guidelines 2018 SIGMOD 5.8374071e-05
6,202 VergeDB: A Database for IoT Analytics on Edge Devices 2021 CIDR 5.8347611e-05
6,238 A Forward Scan based Plane Sweep Algorithm for Parallel Interval Joins 2017 VLDB 5.8236947e-05
6,569 Optimal Splitters for Temporal and Multi-version Databases 2013 SIGMOD 5.7280982e-05
6,743 Near-Optimal Distributed Band-Joins through Recursive Partitioning 2020 SIGMOD 5.6766099e-05
6,812 dbET: Execution Time Distribution-based Plan Selection 2023 SIGMOD 5.6597129e-05
7,266 Depth Estimation for Ranking Query Optimization 2007 VLDB 5.55407e-05
7,355 Selectivity Functions of Range Queries are Learnable* 2022 SIGMOD 5.529034e-05
7,387 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 5.5212177e-05
7,512 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS 5.490671e-05
7,536 Compact Histograms for Hierarchical Identifiers 2006 VLDB 5.4844135e-05
7,581 Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations 2015 VLDB 5.4753678e-05
7,654 Consistent Histograms In The Presence of Distinct Value Counts 2009 VLDB 5.4588598e-05
7,745 PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees 2025 SIGMOD 5.4457135e-05
8,192 Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints 2020 SIGMOD 5.3646457e-05
8,346 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 5.3339321e-05
8,600 Histograms as a Side Effect of Data Movement for Big Data 2014 SIGMOD 5.2913419e-05
9,173 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 5.2011875e-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