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,192 | 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 |
|---|---|---|---|---|
| 63 | Improved Histograms for Selectivity Estimation of Range Predicates | 1996 | SIGMOD | 0.00063595699 |
| 270 | Fast Incremental Maintenance of Approximate Histograms | 1997 | VLDB | 0.00029648047 |
| 325 | The History of Histograms (abridged) | 2003 | VLDB | 0.00027398081 |
| 326 | Optimal Histograms with Quality Guarantees | 1998 | VLDB | 0.0002737538 |
| 531 | Random Sampling for Histogram Construction: How much is enough? | 1998 | SIGMOD | 0.0002079072 |
| 849 | Dynamic Multidimensional Histograms | 2002 | SIGMOD | 0.00015919478 |
| 2,752 | REHIST: Relative Error Histogram Construction Algorithms | 2004 | VLDB | 8.1723418e-05 |
| 5,642 | Bloom Histogram: Path Selectivity Estimation for XML Data with Updates | 2004 | VLDB | 5.3964761e-05 |
| 5,832 | Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms | 2015 | PODS | 5.3085972e-05 |
| 6,634 | Approximating and Testing k-Histogram Distributions in Sub-linear Time | 2012 | PODS | 4.9784928e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,954 | A Tight Lower Bound for Comparison-Based Quantile Summaries | 2020 | PODS | 5.2542261e-05 |
| 326 | Optimal Histograms with Quality Guarantees | 1998 | VLDB | 0.0002737538 |
| 1,790 | Effective Use of Block-Level Sampling in Statistics Estimation | 2004 | SIGMOD | 0.00010529479 |
| 7,150 | Histograms Revisited: When are histograms the best approximation method for aggregates over joins? | 2005 | PODS | 4.8128138e-05 |
| 849 | Dynamic Multidimensional Histograms | 2002 | SIGMOD | 0.00015919478 |
| 11,437 | Data-Independent Space Partitionings for Summaries | 2021 | PODS | 4.1905499e-05 |
| 8,893 | Histograms Reloaded: The Merits of Bucket Diversity | 2010 | SIGMOD | 4.4232868e-05 |
| 13,192 | Corrigendum: Are Few Bins Enough: Testing Histogram Distributions | 2023 | PODS | - |
| 5,832 | Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms | 2015 | PODS | 5.3085972e-05 |
| 6,634 | Approximating and Testing k-Histogram Distributions in Sub-linear Time | 2012 | PODS | 4.9784928e-05 |