| Approximation and streaming algorithms for histogram construction problems (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Histograms are typically used to approximate data distributions. Histograms and related synopsis structures have been successful in a wide variety of popular database applications including approximate querying, similarity searching and data mining. Histograms were a few of the earliest synopsis structures proposed and continue to be popular tools. Typically, the histograms are used as quick and easy estimates, and thus the slight loss of accuracy can be offset by fast histogram construction algorithms. A natural question arises in this context: can we find a fast near optimal approximation algorithm for the histogram construction problem? In this paper, we give the first linear time (1 + ɛ)-factor approximation algorithms (for any ɛ> 0) for several histogram construction problems. Several of our algorithms extend to data streams. We also show that our method generalizes to a large number of histogram construction problems including the use of piecewise small degree polynomials to approximate data. Using synthetic and real-life data sets, we demonstrate that the approximate histograms have almost identical quality in many scenarios and offer significant performance benefits. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||