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)
Incoming Non-self Citations Over Time
Authors
- 1. Jayadev Acharya
- 2. Ilias Diakonikolas
- 3. Chinmay Hegde
- 4. Jerry Li
- 5. Ludwig Schmidt
Incoming Citations (Sorted by Pagerank)
Showing 6 of 6 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,574 | Approximate Query Processing: No Silver Bullet | 2017 | SIGMOD | 0.00011287495 |
| 2,580 | Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee | 2016 | SIGMOD | 8.5058814e-05 |
| 3,835 | I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making | 2017 | VLDB | 6.7163364e-05 |
| 7,467 | Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees | 2025 | SIGMOD | 4.7218691e-05 |
| 9,431 | PairwiseHist: Fast, Accurate and Space-Efficient Approximate Query Processing with Data Compression | 2024 | VLDB | 4.3434046e-05 |
| 11,821 | Are Few Bins Enough: Testing Histogram Distributions | 2016 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 269 | Fast Incremental Maintenance of Approximate Histograms | 1997 | VLDB | 0.00029656549 |
| 326 | Optimal Histograms with Quality Guarantees | 1998 | VLDB | 0.00027358981 |
| 327 | Balancing Histogram Optimality and Practicality for Query Result Size Estimation | 1995 | SIGMOD | 0.00027308479 |
| 530 | Random Sampling for Histogram Construction: How much is enough? | 1998 | SIGMOD | 0.00020803682 |
| 852 | Dynamic Multidimensional Histograms | 2002 | SIGMOD | 0.00015941524 |
| 2,748 | REHIST: Relative Error Histogram Construction Algorithms | 2004 | VLDB | 8.1785955e-05 |
| 6,637 | Approximating and Testing k-Histogram Distributions in Sub-linear Time | 2012 | PODS | 4.9816401e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 326 | Optimal Histograms with Quality Guarantees | 1998 | VLDB | 0.00027358981 |
| 3,310 | Optimal and Approximate Computation of Summary Statistics for Range Aggregates | 2001 | PODS | 7.2408955e-05 |
| 361 | Histogram-Based Approximation of Set-Valued Query Answers | 1999 | VLDB | 0.00025775749 |
| 7,150 | Histograms Revisited: When are histograms the best approximation method for aggregates over joins? | 2005 | PODS | 4.8163484e-05 |
| 996 | Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes | 2000 | SIGMOD | 0.00014741524 |
| 269 | Fast Incremental Maintenance of Approximate Histograms | 1997 | VLDB | 0.00029656549 |
| 3,619 | Fast Algorithms For Hierarchical Range Histogram Construction | 2002 | PODS | 6.9084829e-05 |
| 11,821 | Are Few Bins Enough: Testing Histogram Distributions | 2016 | PODS | 4.1945683e-05 |
| 852 | Dynamic Multidimensional Histograms | 2002 | SIGMOD | 0.00015941524 |
| 6,637 | Approximating and Testing k-Histogram Distributions in Sub-linear Time | 2012 | PODS | 4.9816401e-05 |