The problem of finding heavy hitters and approximating the frequencies of items is at the heart of many problems in data stream analysis. It has been observed that several proposed solutions to this problem can outperform their worst-case guarantees on real data. This leads to the question of whether some stronger bounds can be guaranteed. We answer this in the positive by showing that a class of “counter-based algorithms” (including the popular and very space-efficient Frequent and SpaceSaving algorithms) provide much stronger approximation guarantees than previously known. Specifically, we show that errors in the approximation of individual elements do not depend on the frequencies of the most frequent elements, but only on the frequency of the remaining “tail.” This shows that counter-based methods are the most space-efficient (in fact, space-optimal) algorithms having this strong error bound.This tail guarantee allows these algorithms to solve the “sparse recovery” problem. Here, the goal is to recover a faithful representation of the vector of frequencies,

f. We prove that using spaceO(k), the algorithms construct an approximationf^{*}to the frequency vectorfso that theL_{1}error ||f-f^{*}||_{1}is close to the best possible error min_{f'}||f' -f||_{1}, wheref' ranges over all vectors with at mostknon-zero entries. This improves the previously best known space bound of aboutO(klogn) for streams without element deletions (wherenis the size of the domain from which stream elements are drawn). Other consequences of the tail guarantees are results for skewed (Zipfian) data, and guarantees for accuracy of merging multiple summarized streams.

*This file was generated by
bibtex2html 1.92.*