[發明專利]一種可擴充型Bloom Filter方法

無效

• 申請號: 201110187114.8
• 申請日: 2011-07-06
• 公開（公告）號: CN102243657A
• 公開（公告）日: 2011-11-16
• 發明（設計）人: 強彥;趙涓涓;王小剛;遆鳴;姜華杰
• 申請（專利權）人: 太原理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種可擴充型布隆過濾器方法(EBF，Extendable?Bloom?Filter)，其特征在于，具體步驟如下：

步驟A1，向量集合A中的n個位元，拆分成s組較小的相互獨立的段。假設每段都有相同的位元個數位；接著建立一個新的Hash函數c^s(x)(1≤c^s(x)≤s)，它的作用就是確定是哪組位元參與了計算。對于集合T＝{t₁，t₂，…t_n}，這個集合可動態的增加元素，它和普通的BF相同，EBF用k個Hash函數c_i(x)，1≤i≤k。與前一種算法的區別就是則c_i(x)就是在某段中偏移量哈希函數。

步驟A2，一個元素加入到EBF中；在加入新元素之前，先判斷c^s(x)段是否已滿，即是否已達到可處理數據的極限，即是否在允許的誤報率范圍之內；若超出了這個范圍，則創建一個大小為的新段，這個段的段序號仍然記做c^s(x)；然后通過公式將新加入進去的元素映射到新創建的段中；若該段沒有滿，則用上述公式計算，直接將計算所得的位元位置置1。

步驟A3，判斷新加入的元素是否在特定的集合中；

對于加入的元素x，首先計算c^s(x)，然后檢索所有段號為c^s(x)的段的第c_i(x)位置，若如果其中的一個段中所有c_i(x)位置的位元都是1，則就稱在一定的誤報率下該元素屬于集合T；反之，則x不是集合T中的元素。

2.根據權利要求1所述的可擴充型Bloom?Filter方法，其特征在于，所述步驟A2執行以下步驟：

A21、首先，判斷已有的位元集合c^s(t_i)是否還能容納新的元素，即計算若大于允許的誤報率，則跳到A23；否則繼續；

A22、計算t_i的哈希值c_i(t_i)，并根據哈希值將其映射至位第c^s(t_i)段的位置上，即將c^s(t_i)的位置的位元置1，元素t_i插入完成，算法結束；

A23、創建一個大小為的段，段序號仍記做c^s(t_i)，并根據哈希值將其映射至新生成的段上，即將新生成段c^s(t_i)的第c_i(t_i)個位元置為1，元素t_i在擴展的段中插入，算法結束。

3.根據權利要求1所述的可擴充型Bloom?Filter方法，其特征在于，所述步驟A3執行以下步驟：

A31、計算c^s(x)值，在位元空間中查找所有段號為c^s(x)的段；

A32、計算c_i(x)值，遍歷段號為c^s(x)的段的第c_i(x)位置的值；

A33、在所有段號為c^s(x)的集合中，當且僅當存在某一段號為c^s(x)中所有c_i(x)位置位元值為1，則元素x屬于集合T；否則，在所有段號為c^s(x)的集合中都找不到某段所有c_i(x)位置都為1的位元段，則可以判定在一定誤報率下，元素x不是集合T中的元素。

A34、查找算法結束。