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)

Paper ID: 1668
Venue: PODS
Year: 2016
Pagerank: 5.093636e-05
Overall Rank: 12,024 | 17.51%
DOI: 10.1145/2902251.2902274

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Clément L. Canonne (Columbia University)

BibTeX Citation

@inproceedings{canonne_pods16,
        address = {New York, NY, USA},
        series = {{PODS} '16},
        title = {{Are Few Bins Enough: Testing Histogram Distributions}},
        url = {https://dl.acm.org/doi/10.1145/2902251.2902274},
        doi = {10.1145/2902251.2902274},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Canonne, Clément L.},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
13,381	Corrigendum: Are Few Bins Enough: Testing Histogram Distributions	2023	PODS	-

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
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
235	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023783792
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
267	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022798161
508	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00017275873
723	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014620977
3,111	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	7.7470414e-05
5,421	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS	6.2245831e-05
5,459	Bloom Histogram: Path Selectivity Estimation for XML Data with Updates	2004	VLDB	6.2108888e-05
6,510	Approximating and Testing k-Histogram Distributions in Sub-linear Time	2012	PODS	5.8569033e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,599	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS
2	267	Optimal Histograms with Quality Guarantees	1998	VLDB
3	1,806	Effective Use of Block-Level Sampling in Statistics Estimation	2004	SIGMOD
4	7,443	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS
5	723	Dynamic Multidimensional Histograms	2002	SIGMOD
6	11,632	Data-Independent Space Partitionings for Summaries	2021	PODS
7	8,998	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD
8	13,381	Corrigendum: Are Few Bins Enough: Testing Histogram Distributions	2023	PODS
9	5,421	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS
10	6,510	Approximating and Testing k-Histogram Distributions in Sub-linear Time	2012	PODS