计数最小草图如何找到流中最频繁的项目？ - Heavy Hitters

Question

Count min sketch使用不同的散列函数将流中的元素映射到散列函数。如何从草图中找回最常见的项目？考虑到足够的元素已经通过（数百万）并且我们不知道这些元素。

Answer 1

首先，为了存储数据，CMS使用成对独立的散列函数来映射其结构中的元素（将其视为表格）。 其次，不支持反向过程，它是从表中区分CMS中不同的元素。

使用单独的元素作为查询，您可以使用同一系列散列函数（点查询）在流中检索其估计计数。

为了检索最频繁的项目/项目，应该使用额外的数据结构，如堆。 来自CMS论文的公寓，您的问题快速和有用的演示文稿在这里找到：http://theory.stanford.edu/~tim/s15/l/l2.pdf