計數布隆過濾器

基本概念

計數布隆過濾器被定義為布隆過濾器的一種泛化資料結構，用於在給定一系列元素時測試給定元素的計數是否小於給定閾值。作為布隆過濾器的一種泛化形式，它存在誤報的可能性，但沒有誤判的可能性——換句話說，查詢要麼返回“可能高於或等於閾值”，要麼返回“肯定低於閾值”。

演算法描述

• 計數布隆過濾器中使用的大多數引數與布隆過濾器中的定義相同，例如 n、k。m 表示計數布隆過濾器中計數器的數量，它是布隆過濾器中 m 位的擴充套件。
• 一個空的計數布隆過濾器被設定為 m 個計數器，所有計數器都初始化為 0。
• 與布隆過濾器類似，也必須定義 k 個不同的雜湊函式，每個函式負責將某個集合元素對映或雜湊到 m 個計數器陣列位置中的一個，從而建立均勻的隨機分佈。k 也是一個常數，遠小於 m，它與要追加的元素數量成正比。
• 布隆過濾器的主要泛化是追加元素。要追加元素，將其插入到 k 個雜湊函式中的每一個函式中以獲得 k 個數組位置，並在所有這些位置將計數器加 1。
• 要查詢具有閾值 θ 的元素（驗證元素的計數是否小於 θ），將其插入到 k 個雜湊函式中的每一個函式中以獲得 k 個計數器位置。
• 如果這些位置中的任何一個計數器小於 θ，則元素的計數肯定小於 θ——如果它更高或等於，則所有相應的計數器都將高於或等於 θ。
• 如果所有計數器都高於或等於 θ，則計數確實高於或等於 θ，或者計數器碰巧高於或等於 θ。
• 即使計數小於 θ，如果所有計數器都高於或等於 θ，則這種情況被定義為誤報。與布隆過濾器一樣，這也應該最小化。

Arnab Chakraborty

更新於: 2020年1月3日

449 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習