论文标题
用于确定性搜索热元素的有效算法
Efficient Algorithm for Deterministic Search of Hot Elements
论文作者
论文摘要
当面对大量数据时，通常希望在短时间内在线提取最重要的统计信息并使用较小的内存。例如，人们可能希望快速找到最有影响力的用户在线生成帖子，或检查流是否包含许多相同的元素。在本文中，我们研究了包含插入和删除元素的流，可能会大小$ | n | = n $，正在通过在线确定性算法处理。在流中的任何点，都可以查询算法以在已经处理过的流中的某些频率的输出元素中查询。更确切地说，到目前为止，流中最常见的元素。如果返回的元素包含所有频率大于给定参数$φ$且没有频率小于$φ-ε$的元素的元素，则将视为正确。我们提出了一种有效的在线确定性算法，用于使用$ o（\ min（n，\ frac {polylog（n）}ε））$内存和$ O（polylog（n））$每次处理和输出元素的时间。这是第一个算法，因为先前的算法要么是随机的，要么是在较大的时间$ω（\ min（n，\ frac {\ log n}ε））$中进行的处理元素，或者仅处理插入并需要在流中进行两次通过（即不是真正在线）。我们的解决方案几乎是可伸缩的（只有一个多毛的开销），并且不需要随机性或通过流进行两次扫描。我们在所需的内存上与下边界的$ω（\ min（n，\ frac {1}ε））$补充算法分析。
When facing a very large stream of data, it is often desirable to extract most important statistics online in a short time and using small memory. For example, one may want to quickly find the most influential users generating posts online or check if the stream contains many identical elements. In this paper, we study streams containing insertions and deletions of elements from a possibly large set $N$ of size $|N| = n$, that are being processed by online deterministic algorithms. At any point in the stream the algorithm may be queried to output elements of certain frequency in the already processed stream. More precisely, the most frequent elements in the stream so far. The output is considered correct if the returned elements it contains all elements with frequency greater than a given parameter $φ$ and no element with frequency smaller than $φ-ε$. We present an efficient online deterministic algorithm for solving this problem using $O(\min(n, \frac{polylog(n)}ε))$ memory and $O(polylog(n))$ time per processing and outputting an element. It is the first such algorithm as the previous algorithms were either randomized, or processed elements in substantially larger time $Ω(\min(n, \frac{\log n}ε))$, or handled only insertions and required two passes over the stream (i.e., were not truly online). Our solution is almost-optimally scalable (with only a polylogarithmic overhead) and does not require randomness or scanning twice through the stream. We complement the algorithm analysis with a lower bound $Ω(\min(n, \frac{1}ε))$ on required memory.
