Histogramming data streams with fast per-item processing

A vector A of length N can be approximately represented by a histogram H, by writing [0,N) as the non-overlapping union of B intervals I_j, assigning a value b_j to I_j, and approximating A _i by H_i = b_j for i ∈ I_j. An optimal histogram representation H_opt consists of the choices of I_j and b_j that minimize the sum-square-error ∥A - H∥₂² = ∑_i|A_i-H _i|². Numerous applications in statistics, signal processing and databases rely on histograms; typically B is (significantly) smaller than N and, hence, representing A by H yields substantial compression. We give a deterministic algorithm that approximates H_opt and outputs a histogram H such that ∥A -H∥₂²≤ (1 + ε) ∥A -H_opt∥₂² Our algorithm considers the data items A₀,A₁,.. in order, i.e., in one pass, spends processing time O(1) per item, uses total space B poly(log(N), log ∥A∥, 1/ε ), and determines the histogram in time poly((B, log(N), log ∥A∥, 1/ε ). Our algorithm is suitable to emerging applications where signal is presented in a stream, size of the signal is very large, and one must construct the histogram using significantly smaller space than the signal size. In particular, our algorithm is suited to high performance needs where the per-item processing time must be minimized. Previous algorithms either used large space, i.e., Ω(N), or worked longer, i.e., N log ^Ω(1)(N) total time over the N data items. Our algorithm is the first that simultaneously uses small space as well as runs fast, taking O(1) worst case time for per-item processing. In addition, our algorithm is quite simple.