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
2954
Venue
SIGMOD
Year
1996
Pagerank
0.00048481081
Overall Rank
35 | 99.77%
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,204 Automatic Categorization of Query Results 2004 SIGMOD 8.959723e-05
2,222 Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search? 2019 SIGMOD 8.9255716e-05
2,281 Selectivity Estimation in Extensible Databases - A Neural Network Approach 1998 VLDB 8.8129279e-05
2,308 Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries 2008 VLDB 8.7738996e-05
2,326 Statistical Synopses for Graph-Structured XML Databases 2002 SIGMOD 8.748172e-05
2,367 Using Probabilistic Models for Data Management in Acquisitional Environments 2005 CIDR 8.6855754e-05
2,638 Quality and Efficiency in Kernel Density Estimates for Large Data 2013 SIGMOD 8.3130624e-05
2,933 EVA: A Symbolic Approach to Accelerating Exploratory Video Analytics with Materialized Views 2022 SIGMOD 7.9474026e-05
3,034 Compressing Historical Information in Sensor Networks 2004 SIGMOD 7.8302786e-05
3,086 A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021 SIGMOD 7.7708642e-05
3,309 Conditional Selectivity for Statistics on Query Expressions 2004 SIGMOD 7.5368417e-05
3,545 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 7.3249967e-05
3,575 Optimal Histograms for Hierarchical Range Queries (Extended Abstract) 2000 PODS 7.2946291e-05
3,595 Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees 2020 VLDB 7.2736195e-05
3,688 FACE: A Normalizing Flow based Cardinality Estimator 2022 VLDB 7.201795e-05
3,788 Graph-Based Synopses for Relational Selectivity Estimation 2006 SIGMOD 7.1244416e-05
3,893 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 7.04191e-05
3,907 Accelerating Approximate Aggregation Queries with Expensive Predicates 2021 VLDB 7.0278233e-05
4,035 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.9439151e-05
4,197 Buffer Pool Aware Query Optimization 2005 CIDR 6.8406917e-05
4,368 Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian Process 2022 SIGMOD 6.7393882e-05
4,405 DigitHist: a Histogram-Based Data Summary with Tight Error Bounds 2017 VLDB 6.7218674e-05
4,591 Automated Statistics Collection in DB2 UDB 2004 VLDB 6.614318e-05
4,819 Space efficiency in Synopsis construction algorithms 2005 VLDB 6.4940349e-05
4,846 A Comparison of Selectivity Estimators for Range Queries on Metric Attributes 1999 SIGMOD 6.4807645e-05
4,889 Fast Algorithms For Hierarchical Range Histogram Construction 2002 PODS 6.4600939e-05
4,945 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 6.4321265e-05
5,184 KLL± Approximate Quantile Sketches over Dynamic Datasets 2021 VLDB 6.3283918e-05
5,490 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 6.200262e-05
5,522 Building Wavelet Histograms on Large Data in MapReduce 2012 VLDB 6.1871697e-05
5,733 A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets 2006 VLDB 6.1062071e-05
6,059 Evaluating Interactive Data Systems: Workloads, Metrics, and Guidelines 2018 SIGMOD 5.9915079e-05
6,061 VergeDB: A Database for IoT Analytics on Edge Devices 2021 CIDR 5.9910733e-05
6,106 A Forward Scan based Plane Sweep Algorithm for Parallel Interval Joins 2017 VLDB 5.973703e-05
6,434 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.8799421e-05
6,547 Optimal Splitters for Temporal and Multi-version Databases 2013 SIGMOD 5.8444303e-05
6,596 Near-Optimal Distributed Band-Joins through Recursive Partitioning 2020 SIGMOD 5.828647e-05
7,123 Depth Estimation for Ranking Query Optimization 2007 VLDB 5.6966694e-05
7,193 dbET: Execution Time Distribution-based Plan Selection 2023 SIGMOD 5.6770249e-05
7,206 Selectivity Functions of Range Queries are Learnable* 2022 SIGMOD 5.6731116e-05
7,256 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 5.6625146e-05
7,375 Compact Histograms for Hierarchical Identifiers 2006 VLDB 5.6299286e-05
7,388 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS 5.6268292e-05
7,433 Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations 2015 VLDB 5.6197531e-05
7,554 Consistent Histograms In The Presence of Distinct Value Counts 2009 VLDB 5.6001388e-05
8,002 Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints 2020 SIGMOD 5.5085906e-05
8,155 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 5.4766319e-05
8,204 PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees 2025 SIGMOD 5.4667903e-05
8,420 Histograms as a Side Effect of Data Movement for Big Data 2014 SIGMOD 5.4279873e-05
8,986 One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting 2024 SIGMOD 5.3387783e-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