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,192 | 8.32%
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,829	Are Few Bins Enough: Testing Histogram Distributions	2016	PODS	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
328	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027301497
7,150	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS	4.8128138e-05
4,969	Relative Error Streaming Quantiles	2021	PODS	5.790405e-05
531	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.0002079072
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002737538
8,893	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD	4.4232868e-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
11,829	Are Few Bins Enough: Testing Histogram Distributions	2016	PODS	4.1905499e-05
13,385	Erratum for: Approximating and Testing k-Histogram Distributions in Sub-linear Time	2015	PODS	-