Space-optimal heavy hitters with strong error bounds
Space-optimal heavy hitters with strong error bounds
复制标题
DOI：
10.1145/1559795.1559819
复制
发表时间：
2009-06
期刊：
影响因子：
--
通讯作者：
Radu Berinde;Graham Cormode;P. Indyk;M. Strauss
中科院分区：
文献类型：
--
作者：
Radu Berinde;Graham Cormode;P. Indyk;M. Strauss
在数据流分析中，找到重要的关键词和近似项的频率是许多问题的核心。已经观察到，针对该问题提出的几种解决方案可以在真实的数据上超过其最坏情况保证。这就引出了一个问题，即是否可以保证一些更强的边界。我们回答这个问题的积极表明，一类“计数器为基础的算法”（包括流行的和非常节省空间的频繁和节省空间的算法）提供更强的近似保证比以前已知的。具体来说，我们表明，在个别元素的近似误差不依赖于最频繁的元素的频率，但只对剩余的频率“尾巴”。“这表明基于计数器的方法是最具空间效率（实际上是空间最优）的算法，具有这种强错误界。这种尾部保证允许这些算法解决“稀疏恢复”问题。这里，目标是恢复频率向量f的忠实表示。我们证明了使用空间O（k），算法构造了频率向量f的近似f*，使得L1误差||f -- f*|| 1接近最佳可能误差minf 2|| f2 -- f|| 1，其中f2的范围覆盖具有至多k个非零条目的所有向量。对于没有元素删除的流（其中n是从中提取流元素的域的大小），这改进了以前最好的已知空间边界约为O（k log n）。尾部保证的其他结果是偏斜（Zipfian）数据的结果，并保证合并多个汇总流的准确性。
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 space O(k), the algorithms construct an approximation f* to the frequency vector f so that the L1 error ||f -- f*||1 is close to the best possible error minf2 ||f2 -- f||1, where f2 ranges over all vectors with at most k non-zero entries. This improves the previously best known space bound of about O(k log n) for streams without element deletions (where n is 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.