fast, small-space algorithms for approximate histogram maintenance
(MATH) A vector A of length N is defined implicitly, via a stream of updates of the form "add 5 to A 3 ." We give a sketching algorithm, that constructs a small sketch from the stream of updates, and a reconstruction algorithm, that produces a B -bucket piecewise-constant representation (histogram) H for A from the sketch, such that || AH ||&xie;(1+&egr;)|| AH opt |&#124, where the error || AH || is either $\ell_1$ (absolute) or $\ell_2$ (root-mean-square) error. The time to process a single update, time to reconstruct the histogram, and size of the sketch are each bounded by poly( B ,log( N ),log|| A ,1/&egr;. Our result is obtained in two steps. First we obtain what we call a robust histogram approximation for A , a histogram such that adding a small number of buckets does not help improve the representation quality significantly. From the robust histogram, we cull a histogram of desired accruacy and B buckets in the second step. This technique also provides similar results for Haar wavelet representations, under $\ell_2$ error. Our results have applications in summarizing data distributions fast and succinctly even in distributed settings.
algorithm approximation histogram maintenance vectorization streams update sketching representation errors timing process size log robust help quality wavelet applications data distributed space mean