Approximating and Testing k-Histogram Distributions in Sub-linear Time

Summary: Sublinear-time, sample-efficient algorithms that from samples produce a k-interval piecewise-constant approximation minimizing L2 error to an unknown distribution over [n]. Also gives testers distinguishing k-histograms from distributions ε-far in L1 or L2 with improved complexity. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1561
Venue: PODS
Year: 2012
Pagerank: 4.9784928e-05
Overall Rank: 6,634 | 53.90%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,841	I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making	2017	VLDB	6.7090738e-05
5,832	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS	5.3085972e-05
8,986	High Performance Stream Query Processing With Correlation-Aware Partitioning	2014	VLDB	4.4128163e-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	-

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
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

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
846	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00015949293
4,969	Relative Error Streaming Quantiles	2021	PODS	5.790405e-05
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044753012
5,954	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	5.2542261e-05
995	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00014745185
274	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00029383266
849	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015919478
3,621	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS	6.9022467e-05
11,829	Are Few Bins Enough: Testing Histogram Distributions	2016	PODS	4.1905499e-05
5,832	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS	5.3085972e-05