algorithm - 请识别此算法 : probabilistic top-k elements in a data stream

Question

我记得几年前听说过以下算法，但在网上找不到任何引用资料。它仅使用 m 计数器识别 n 元素数据流中的前 k 元素(或重击者)。这对于使用最少的内存查找热门搜索词、网络滥用者等特别有用。

算法:对于每个元素，

1. 如果元素还没有计数器和计数器 <m，为元素创建一个计数器并初始化为 1。
2. 否则，如果元素确实有计数器，则递增它。
3. 否则，如果元素没有计数器并且计数器 > m，则递减现有计数器 c。如果 c 达到 0，则用当前元素替换其对应的元素。 (c 是现有计数器列表的索引，其中 c 以循环方式为到达此步骤的每个元素增加。)

我发现了许多其他类似的算法(其中许多已在关于 streaming algorithms 的维基百科文章中列出，但未描述)，但不是这个。我特别喜欢它，因为它实现起来和描述起来一样简单。

但我想更多地了解它的概率特征——如果我只对前 100 个项目感兴趣，那么使用 1,000 个计数器而不是 100 个计数器有什么效果？

Answer 1

您正在谈论著名的 Misra-Gries 算法，而节省空间的算法是 Misra-Gries 算法的更快版本。详情请查看本讲义Streaming Algorithm Dartmouth第 1.2 节。

我想指出的一件事是，如果你只使用 k 个计数器，这个算法不会给你前 k 个元素，相反，它会给出所有频率 > m/k 的元素，其中 m 是数据流。

详分割析可以在我附上的讲义中找到。