Dav*_*rtz 42
假设您正在查看Facebook个人资料的流量.你有数十亿的点击率.您想要查找最常访问的配置文件.您可以为每个配置文件保留一个计数,但是您需要记录大量的计数,其中绝大多数都没有意义.
使用有损计数,您可以定期从表中删除非常低的计数元素.最频繁访问的配置文件几乎从不会有低计数,如果他们这样做,他们就不可能长时间呆在那里.
该算法基本上涉及将输入分组为块或块并在每个块内进行计数.然后将每个元素的计数减少一个,删除计数下降到零的任何元素.
频率最高的个人资料会计入您的计算并留在那里.任何未经常命中的配置文件将在几个块中降至零,您将不再需要跟踪它们.
请注意,最终结果与顺序相关,对最后处理的计数给予更大的权重.在某些情况下,这是完美的意义,是一个好处,而不是一个缺点.(如果你想知道现在最流行的哪些配置文件,你想要权衡今天的访问量而不是上个月的访问权限.)
算法有很多改进.但基本的想法是 - 找到重型击球手而不必跟踪每个元素,根据目前的数据,定期清除你看起来不太可能是重击手的任何元素的数量.
你可以在这篇博客文章和开源版本中找到有关Lossy Counting(和Sticky Sampling)如何工作的解释.
最常见的项目"生存".给定频率阈值f,频率误差e和元素总数N,输出可以表示如下:计数超过fN-eN的元素.
最坏的情况我们需要(1/e)*log(eN)计数器.
例如,我们可能希望打印遭受命中率超过20%的人的Facebook页面,误差阈值为2%(经验法则:误差=频率阈值的10%).
对于频率f = 20%,e = 2%,将输出具有超过f = 20%的真实频率的所有元素 - 没有假阴性.但我们数不胜数.元素的输出频率可以比其真实频率小至多2%.误报可能出现频率在18%-20%之间.最后,不会输出频率低于18%的元素.
给定1/e的窗口,以下保证: