什麼是有損計數？

Question

任何人都可以向我解釋有損計數算法嗎？它是查找流中項目頻率的流式算法。謝謝。

Answer 1

假設您正在查看Facebook個人資料的流量。你有數十億次點擊。您想要查找最常訪問的配置文件。你可以爲每個配置文件保留一個計數，但是你會有很多計數來跟蹤，其中絕大多數會毫無意義。

有損計數，您定期從表中刪除非常低的計數元素。最常訪問的配置文件幾乎不會有低計數，如果他們這樣做，他們將不可能長時間呆在那裏。

該算法基本上涉及將輸入分組爲塊或塊並在每個塊內計數。然後，將每個元素的計數減1，並刪除其計數降爲零的元素。

最頻繁命中的配置文件將得到您的計數並留在那裏。任何未經常擊中的配置文件將在幾個塊中降至零，您不必再跟蹤它們。

請注意，最終結果與訂單有關，給予最後處理的計數權重更大。在某些情況下，這是非常有意義的，並且是有利的而不是缺點。 （如果您基本知道哪些配置文件是最受歡迎的現在，那麼您希望今天訪問的訪問次數超過上個月的訪問次數。）

該算法有大量的改進。但基本的想法是 - 找到重擊者而不必跟蹤每一個元素，根據目前的數據定期清除任何看起來不太可能成爲重擊者的元素的數量。

Answer 2

你可以找到有損計數（和粘性採樣）如何工作on this blog post和open-source version here的解釋。

查看次數最多的項目「生存」。給定頻率閾值f，頻率誤差e和元素總數N，輸出可以表示如下：計數超過fN_eN的元素。

最糟糕的情況我們需要（1/e）* log（eN）計數器。例如，我們可能希望打印出擊率超過20％，誤差閾值爲2％（經驗法則：誤差=頻率閾值的10％）的Facebook頁面。對於頻率f = 20％，e = 2％，將輸出真實頻率超過f = 20％的所有元素 - 沒有誤報。但我們低估了。元件的輸出頻率可以比其真實頻率低至多2％。誤報可能會出現，頻率在18％ - 20％之間。最後，不會輸出頻率小於18％的元素。

由於尺寸1/E的窗口，以下保證持有：

• 頻率由最多E *低估ň
• 沒有出現假陰性
• 誤報有至少的F真實頻率N - e N