请确定此算法:数据流中的概率top-k元素

Question

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

算法:对于每个元素,

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

我发现了许多其他类似的算法(其中许多已列出,但未在此维基百科关于流式算法的文章中进行描述),但不是这个.我特别喜欢它,因为它的实现和描述一样简单.

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

Answer 1

您可能正在寻找“频繁”算法。它使用k - 1 计数器来查找所有超过总数1/ k的元素，由 Misra 和 Gries 于 1982 年发布。它是 Boyer 和 Moore（或 Fischer-Salzberg）“多数”算法的推广，其中k为 2。这些算法和相关算法在一篇有用的文章“布兰妮·斯皮尔斯问题”中介绍。

我在 StackOverflow 上的其他地方对该算法进行了详细解释，这里不再重复。重要的一点是，在一次通过之后，计数器值并不能精确地指示某项的频率；而是表明某项出现的频率。它们可能会少计数，其幅度取决于流的长度，并且与计数器的数量 ( n / k ) 成反比。如果您想要精确的计数而不是频率的估计，所有这些算法（包括 Metwally 的“SpaceSaving”）都需要第二遍。