Back to papers

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

1657

Venue

PODS

Year

2015

Pagerank

5.3085972e-05

Overall Rank

5,832 | 59.47%

DOI

10.1145/2745754.2745772