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: 1656
Venue: PODS
Year: 2015
Pagerank: 6.2245831e-05
Overall Rank: 5,421 | 62.81%
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,108	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012145154
1,962	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.3978414e-05
3,288	I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making	2017	VLDB	7.5578177e-05
6,434	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	5.8799421e-05
7,351	PairwiseHist: Fast, Accurate and Space-Efficient Approximate Query Processing with Data Compression	2024	VLDB	5.6354898e-05
12,024	Are Few Bins Enough: Testing Histogram Distributions	2016	PODS	5.093636e-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
235	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023783792
267	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022798161
274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022645621
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
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	267	Optimal Histograms with Quality Guarantees	1998	VLDB
2	3,241	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS
3	435	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB
4	7,443	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS
5	850	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD
6	235	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB
7	4,889	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS
8	12,024	Are Few Bins Enough: Testing Histogram Distributions	2016	PODS
9	723	Dynamic Multidimensional Histograms	2002	SIGMOD
10	6,510	Approximating and Testing k-Histogram Distributions in Sub-linear Time	2012	PODS