Are Few Bins Enough: Testing Histogram Distributions
Summary: Test whether a distribution over [n] is a k-histogram (piecewise-constant on ≤k contiguous intervals) vs ε-far in ℓ1 with a new sample- and time-efficient tester. Provides a nearly-matching information-theoretic sample lower bound, substantially tightening prior bounds (Indyk et al.; Canonne et al.). (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 13,178 | Corrigendum: Are Few Bins Enough: Testing Histogram Distributions | 2023 | PODS | - |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 10 of 10 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 64 | Improved Histograms for Selectivity Estimation of Range Predicates | 1996 | SIGMOD | 0.00063612837 |
| 269 | Fast Incremental Maintenance of Approximate Histograms | 1997 | VLDB | 0.00029656549 |
| 325 | The History of Histograms (abridged) | 2003 | VLDB | 0.00027378328 |
| 326 | Optimal Histograms with Quality Guarantees | 1998 | VLDB | 0.00027358981 |
| 530 | Random Sampling for Histogram Construction: How much is enough? | 1998 | SIGMOD | 0.00020803682 |
| 852 | Dynamic Multidimensional Histograms | 2002 | SIGMOD | 0.00015941524 |
| 2,748 | REHIST: Relative Error Histogram Construction Algorithms | 2004 | VLDB | 8.1785955e-05 |
| 5,632 | Bloom Histogram: Path Selectivity Estimation for XML Data with Updates | 2004 | VLDB | 5.4014372e-05 |
| 5,879 | Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms | 2015 | PODS | 5.2908101e-05 |
| 6,637 | Approximating and Testing k-Histogram Distributions in Sub-linear Time | 2012 | PODS | 4.9816401e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,956 | A Tight Lower Bound for Comparison-Based Quantile Summaries | 2020 | PODS | 5.2566971e-05 |
| 326 | Optimal Histograms with Quality Guarantees | 1998 | VLDB | 0.00027358981 |
| 1,797 | Effective Use of Block-Level Sampling in Statistics Estimation | 2004 | SIGMOD | 0.00010523169 |
| 7,150 | Histograms Revisited: When are histograms the best approximation method for aggregates over joins? | 2005 | PODS | 4.8163484e-05 |
| 852 | Dynamic Multidimensional Histograms | 2002 | SIGMOD | 0.00015941524 |
| 11,434 | Data-Independent Space Partitionings for Summaries | 2021 | PODS | 4.1945683e-05 |
| 8,893 | Histograms Reloaded: The Merits of Bucket Diversity | 2010 | SIGMOD | 4.4275272e-05 |
| 13,178 | Corrigendum: Are Few Bins Enough: Testing Histogram Distributions | 2023 | PODS | - |
| 5,879 | Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms | 2015 | PODS | 5.2908101e-05 |
| 6,637 | Approximating and Testing k-Histogram Distributions in Sub-linear Time | 2012 | PODS | 4.9816401e-05 |