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
2893
Venue
SIGMOD
Year
1996
Pagerank
0.00063595699
Overall Rank
63 | 99.57%
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,322 Statistical Synopses for Graph-Structured XML Databases 2002 SIGMOD 9.0348397e-05
2,359 Consistently Estimating the Selectivity of Conjuncts of Predicates 2005 VLDB 8.967267e-05
2,364 Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries 2020 SIGMOD 8.955077e-05
2,734 Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search? 2019 SIGMOD 8.2082721e-05
2,779 Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries 2008 VLDB 8.1314377e-05
2,844 Selectivity Estimation in Extensible Databases - A Neural Network Approach 1998 VLDB 8.0308994e-05
3,127 Compressing Historical Information in Sensor Networks 2004 SIGMOD 7.5200903e-05
3,220 Quality and Efficiency in Kernel Density Estimates for Large Data 2013 SIGMOD 7.3590708e-05
3,597 Graph-Based Synopses for Relational Selectivity Estimation 2006 SIGMOD 6.9337747e-05
3,610 EVA: A Symbolic Approach to Accelerating Exploratory Video Analytics with Materialized Views 2022 SIGMOD 6.919859e-05
3,621 Fast Algorithms For Hierarchical Range Histogram Construction 2002 PODS 6.9022467e-05
3,656 Conditional Selectivity for Statistics on Query Expressions 2004 SIGMOD 6.8712579e-05
3,720 Space efficiency in Synopsis construction algorithms 2005 VLDB 6.8139746e-05
3,801 Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees 2020 VLDB 6.7528979e-05
3,896 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.6526869e-05
3,924 A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021 SIGMOD 6.6227223e-05
4,018 Optimal Histograms for Hierarchical Range Queries (Extended Abstract) 2000 PODS 6.5250686e-05
4,352 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 6.2542257e-05
4,353 Buffer Pool Aware Query Optimization 2005 CIDR 6.2535805e-05
4,431 Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian Process 2022 SIGMOD 6.1870601e-05
4,433 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.1852739e-05
4,543 FACE: A Normalizing Flow based Cardinality Estimator 2022 VLDB 6.0953507e-05
4,703 Accelerating Approximate Aggregation Queries with Expensive Predicates 2021 VLDB 5.9793615e-05
4,815 DigitHist: a Histogram-Based Data Summary with Tight Error Bounds 2017 VLDB 5.8978716e-05
5,019 Automated Statistics Collection in DB2 UDB 2004 VLDB 5.7492033e-05
5,066 A Comparison of Selectivity Estimators for Range Queries on Metric Attributes 1999 SIGMOD 5.7157182e-05
5,543 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 5.4486922e-05
5,588 XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data 2004 VLDB 5.4193309e-05
5,636 KLL± Approximate Quantile Sketches over Dynamic Datasets 2021 VLDB 5.3985928e-05
5,908 Building Wavelet Histograms on Large Data in MapReduce 2012 VLDB 5.2731311e-05
6,232 A Forward Scan based Plane Sweep Algorithm for Parallel Interval Joins 2017 VLDB 5.1391814e-05
6,285 A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets 2006 VLDB 5.1231886e-05
6,311 VergeDB: A Database for IoT Analytics on Edge Devices 2021 CIDR 5.1112212e-05
6,448 Evaluating Interactive Data Systems: Workloads, Metrics, and Guidelines 2018 SIGMOD 5.0532741e-05
6,618 Near-Optimal Distributed Band-Joins through Recursive Partitioning 2020 SIGMOD 4.9864636e-05
6,697 Optimal Splitters for Temporal and Multi-version Databases 2013 SIGMOD 4.9538866e-05
6,826 Depth Estimation for Ranking Query Optimization 2007 VLDB 4.9090969e-05
7,340 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 4.7526052e-05
7,442 Selectivity Functions of Range Queries are Learnable* 2022 SIGMOD 4.7248554e-05
7,460 Compact Histograms for Hierarchical Identifiers 2006 VLDB 4.7198214e-05
7,465 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 4.7186055e-05
7,573 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS 4.7034681e-05
7,644 Selectivity Estimation on Streaming Spatio-Textual Data Using Local Correlations 2015 VLDB 4.6853638e-05
7,725 Consistent Histograms In The Presence of Distinct Value Counts 2009 VLDB 4.6621296e-05
7,833 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 4.6367487e-05
7,854 dbET: Execution Time Distribution-based Plan Selection 2023 SIGMOD 4.6306186e-05
8,139 Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints 2020 SIGMOD 4.5727142e-05
8,433 Histograms as a Side Effect of Data Movement for Big Data 2014 SIGMOD 4.5078508e-05
8,893 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 4.4232868e-05
8,952 One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting 2024 SIGMOD 4.4195459e-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