Corrigendum: Are Few Bins Enough: Testing Histogram Distributions

Summary: Corrigendum to PODS'16 'Are Few Bins Enough' identifying a flaw in the analysis of its histogram-distribution tester. The claimed sample complexity O~(√n/ε^2 + k/ε^3) is incorrect and must be rederived. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1871
Venue: PODS
Year: 2023
Pagerank: -
Overall Rank: 13,178 | 8.33%
DOI: 10.1145/3584372.3588652

Incoming Non-self Citations Over Time

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

Authors

1. Clément Louis Canonne

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
11,821	Are Few Bins Enough: Testing Histogram Distributions	2016	PODS	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
327	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027308479
7,150	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS	4.8163484e-05
4,966	Relative Error Streaming Quantiles	2021	PODS	5.7959749e-05
530	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00020803682
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00027358981
8,893	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD	4.4275272e-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
11,821	Are Few Bins Enough: Testing Histogram Distributions	2016	PODS	4.1945683e-05
13,372	Erratum for: Approximating and Testing k-Histogram Distributions in Sub-linear Time	2015	PODS	-