Fast and Near-Optimal Algorithms for Approximating Distributions by Histograms
Jayadev Acharya, Ilias Diakonikolas, Chinmay D Hegde, Jerry Zheng Li, Ludwig Schmidt · 2015
Histograms are among the most popular structures for the succinct summarization of data in a variety of database applications. In this work, we provide fast and near-optimal algorithms for approximating arbitrary one dimensional data distributions by histograms.