Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms

Summary: Gives a sample-optimal (m=O(1/ε^2)), sample-linear (O(m)) algorithm that—independent of domain size n—returns an O(k)-histogram approximating a distribution p to l2 error O(opt_k)+ε. Extends to multi-scale and piecewise-polynomial approximations and achieves 1–2 orders-of-magnitude faster empirical runtimes than prior methods. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: ha4a660ad0c9675a8
Venue: PODS
Year: 2015
Pagerank: 6.0923159e-05
Overall Rank: 5,534 | 62.80%
DOI: 10.1145/2745754.2745772

Incoming Non-self Citations Over Time

Authors

1. Jayadev Acharya (Massachusetts Institute of Technology)
2. Ilias Diakonikolas (University of Edinburgh)
3. Chinmay Hegde (Massachusetts Institute of Technology)
4. Jerry Li (Massachusetts Institute of Technology)
5. Ludwig Schmidt (Massachusetts Institute of Technology)

BibTeX Citation

@inproceedings{acharya_pods15,
        address = {New York, NY, USA},
        series = {{PODS} '15},
        title = {{Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms}},
        url = {https://dl.acm.org/doi/10.1145/2745754.2745772},
        doi = {10.1145/2745754.2745772},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Acharya, Jayadev and Diakonikolas, Ilias and Hegde, Chinmay and Li, Jerry and Schmidt, Ludwig},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,082	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012122749
2,000	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.2112617e-05
3,341	I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making	2017	VLDB	7.4063139e-05
5,902	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	5.9536872e-05
7,375	PairwiseHist: Fast, Accurate and Space-Efficient Approximate Query Processing with Data Compression	2024	VLDB	5.5400509e-05
12,319	Are Few Bins Enough: Testing Histogram Distributions	2016	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023363722
275	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022413521
283	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022214789
519	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00016942879
742	Dynamic Multidimensional Histograms	2002	SIGMOD	0.0001431602
3,163	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	7.5789852e-05
6,639	Approximating and Testing k-Histogram Distributions in Sub-linear Time	2012	PODS	5.7259633e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	275	Optimal Histograms with Quality Guarantees	1998	VLDB
2	3,305	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS
3	448	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB
4	7,568	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS
5	866	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD
6	242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB
7	5,004	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS
8	12,319	Are Few Bins Enough: Testing Histogram Distributions	2016	PODS
9	742	Dynamic Multidimensional Histograms	2002	SIGMOD
10	6,639	Approximating and Testing k-Histogram Distributions in Sub-linear Time	2012	PODS