Histograms Reloaded: The Merits of Bucket Diversity
Summary: Question the histogram paradigm of storing per-bucket distinct-values and average frequency, revealing large estimation errors in DB systems. Propose heterogeneous histograms with mixed bucket types to achieve upper error bounds under reduced space, with no single winner. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 6 of 6 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,981 | Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses | 2018 | VLDB | 9.8687545e-05 |
| 4,833 | MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions | 2019 | SIGMOD | 5.8916346e-05 |
| 5,905 | Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA | 2014 | SIGMOD | 5.2788785e-05 |
| 6,374 | Optimization of Conjunctive Predicates for Main Memory Column Stores | 2016 | VLDB | 5.0927058e-05 |
| 9,187 | POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance | 2024 | VLDB | 4.3780059e-05 |
| 10,639 | Cardinality Estimation for Having-Clauses | 2025 | VLDB | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 7 of 7 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 28 | Accurate Estimation Of The Number Of Tuples Satisfying A Condition | 1984 | SIGMOD | 0.00080435857 |
| 64 | Improved Histograms for Selectivity Estimation of Range Predicates | 1996 | SIGMOD | 0.00063612837 |
| 308 | Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports | 2001 | VLDB | 0.00028142852 |
| 327 | Balancing Histogram Optimality and Practicality for Query Result Size Estimation | 1995 | SIGMOD | 0.00027308479 |
| 378 | Towards Estimation Error Guarantees for Distinct Values | 2000 | PODS | 0.0002497492 |
| 629 | Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors | 2009 | VLDB | 0.00018942366 |
| 808 | Universality of Serial Histograms | 1993 | VLDB | 0.00016432772 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 808 | Universality of Serial Histograms | 1993 | VLDB | 0.00016432772 |
| 5,879 | Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms | 2015 | PODS | 5.2908101e-05 |
| 7,150 | Histograms Revisited: When are histograms the best approximation method for aggregates over joins? | 2005 | PODS | 4.8163484e-05 |
| 64 | Improved Histograms for Selectivity Estimation of Range Predicates | 1996 | SIGMOD | 0.00063612837 |
| 7,728 | Consistent Histograms In The Presence of Distinct Value Counts | 2009 | VLDB | 4.666214e-05 |
| 327 | Balancing Histogram Optimality and Practicality for Query Result Size Estimation | 1995 | SIGMOD | 0.00027308479 |
| 852 | Dynamic Multidimensional Histograms | 2002 | SIGMOD | 0.00015941524 |
| 116 | Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries | 1988 | SIGMOD | 0.00046148737 |
| 1,120 | Global Optimization of Histograms | 2001 | SIGMOD | 0.00013856211 |
| 326 | Optimal Histograms with Quality Guarantees | 1998 | VLDB | 0.00027358981 |