Database Paper Browser

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
2892
Venue
SIGMOD
Year
1996
Pagerank
0.00063612837
Overall Rank
64 | 99.56%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 111 citing papers.

Rank Citing Paper Year Venue Pagerank
2,316 Statistical Synopses for Graph-Structured XML Databases 2002 SIGMOD 9.0419716e-05
2,356 Consistently Estimating the Selectivity of Conjuncts of Predicates 2005 VLDB 8.9620762e-05
2,364 Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries 2020 SIGMOD 8.9554751e-05
2,732 Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search? 2019 SIGMOD 8.2087602e-05
2,779 Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries 2008 VLDB 8.1320575e-05
2,841 Selectivity Estimation in Extensible Databases - A Neural Network Approach 1998 VLDB 8.0287389e-05
3,121 Compressing Historical Information in Sensor Networks 2004 SIGMOD 7.5271941e-05
3,313 Quality and Efficiency in Kernel Density Estimates for Large Data 2013 SIGMOD 7.2381634e-05
3,593 Graph-Based Synopses for Relational Selectivity Estimation 2006 SIGMOD 6.9385476e-05
3,606 EVA: A Symbolic Approach to Accelerating Exploratory Video Analytics with Materialized Views 2022 SIGMOD 6.9260354e-05
3,619 Fast Algorithms For Hierarchical Range Histogram Construction 2002 PODS 6.9084829e-05
3,651 Conditional Selectivity for Statistics on Query Expressions 2004 SIGMOD 6.8768678e-05
3,719 Space efficiency in Synopsis construction algorithms 2005 VLDB 6.8204683e-05
3,798 Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees 2020 VLDB 6.7592302e-05
3,893 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.6584217e-05
3,924 A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021 SIGMOD 6.6271553e-05
4,017 Optimal Histograms for Hierarchical Range Queries (Extended Abstract) 2000 PODS 6.524501e-05
4,358 Buffer Pool Aware Query Optimization 2005 CIDR 6.2571485e-05
4,359 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 6.2569955e-05
4,434 Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian Process 2022 SIGMOD 6.1929999e-05
4,438 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.1898903e-05
4,543 FACE: A Normalizing Flow based Cardinality Estimator 2022 VLDB 6.1011198e-05
4,712 Accelerating Approximate Aggregation Queries with Expensive Predicates 2021 VLDB 5.9787986e-05
4,831 DigitHist: a Histogram-Based Data Summary with Tight Error Bounds 2017 VLDB 5.8924198e-05
5,025 Automated Statistics Collection in DB2 UDB 2004 VLDB 5.7533741e-05
5,082 A Comparison of Selectivity Estimators for Range Queries on Metric Attributes 1999 SIGMOD 5.711623e-05
5,535 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 5.4539235e-05
5,579 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 5.4245689e-05
5,627 KLL± Approximate Quantile Sketches over Dynamic Datasets 2021 VLDB 5.403782e-05
5,903 Building Wavelet Histograms on Large Data in MapReduce 2012 VLDB 5.2791351e-05
6,154 A Forward Scan based Plane Sweep Algorithm for Parallel Interval Joins 2017 VLDB 5.1815134e-05
6,286 A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets 2006 VLDB 5.1280225e-05
6,311 VergeDB: A Database for IoT Analytics on Edge Devices 2021 CIDR 5.1161316e-05
6,444 Evaluating Interactive Data Systems: Workloads, Metrics, and Guidelines 2018 SIGMOD 5.059132e-05
6,619 Near-Optimal Distributed Band-Joins through Recursive Partitioning 2020 SIGMOD 4.9910152e-05
6,694 Optimal Splitters for Temporal and Multi-version Databases 2013 SIGMOD 4.9586454e-05
6,829 Depth Estimation for Ranking Query Optimization 2007 VLDB 4.9136064e-05
7,358 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 4.7529363e-05
7,457 Selectivity Functions of Range Queries are Learnable* 2022 SIGMOD 4.7247191e-05
7,459 Compact Histograms for Hierarchical Identifiers 2006 VLDB 4.7243492e-05
7,467 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 4.7218691e-05
7,581 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS 4.7057641e-05
7,645 Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations 2015 VLDB 4.6896215e-05
7,728 Consistent Histograms In The Presence of Distinct Value Counts 2009 VLDB 4.666214e-05
7,827 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 4.6411831e-05
7,854 dbET: Execution Time Distribution-based Plan Selection 2023 SIGMOD 4.6350172e-05
8,138 Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints 2020 SIGMOD 4.5771031e-05
8,443 Histograms as a Side Effect of Data Movement for Big Data 2014 SIGMOD 4.5119257e-05
8,893 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 4.4275272e-05
8,948 One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting 2024 SIGMOD 4.423786e-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