有損計數演算法如何查詢頻繁項？

使用者支援兩個輸入引數，包括最小支援閾值σ和先前指示的誤差範圍ε。理論上，傳入的資料流被劃分為寬度為w = [1/ε]的桶。

設N為當前資料流長度，即到目前為止檢視的專案數。該演算法需要一個頻率列表資料結構來儲存所有頻率高於0的元素。對於每個專案，列表支援f（近似頻率計數）和∆（f的最大可能誤差）。

該演算法如下所示對專案進行分桶。當一個新的桶到達時，桶中的專案將被插入到頻率列表中。如果列表中存在給定專案，則可以簡單地增加其頻率計數f。否則，可以將其新增到列表中，頻率計數為1。如果新專案來自第b個桶，則可以將其頻率計數的最大可能誤差∆設定為b-1。

每當獲得桶邊界（即N達到寬度的倍數w，包括w、2w、3w等）時，就會確定頻率列表。設b為當前桶號。如果對於某個條目，f + ∆ ≤ b，則刪除該條目。透過這種方法，演算法的目標是保持頻率列表較小，以便它可以放入主記憶體中。為每個專案儲存的頻率計數將是專案的真實頻率或其最小值。

近似演算法中的重要因素是近似比（或誤差範圍）。讓我們看看刪除專案的情況。當專案的f + ∆ ≤ b時出現這種情況，其中b是當前桶號。

可以理解的是b ≤ N/w，即b ≤ εN。專案的實際頻率最多為f+∆。因此，可以最小化專案的εN。如果該專案的實際支援度為σ（這是將其視為頻繁專案的最小支援度或下界），則實際頻率為σN，而頻率列表上的頻率f應至少為(σN −εN)。

因此，如果我們輸出頻率列表中所有f值至少為(σN −εN)的專案，則將輸出一些頻繁項。此外，還將輸出一些非頻繁項（實際頻率至少為σN −εN，但小於σN）。

Ginni

更新於：2022年2月17日

820 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習