[發(fā)明專利]一種可擴展的布魯姆過濾器查詢方法及其元素插入方法

無效

• 申請?zhí)枺?/td>: 200710035385.5
• 申請日: 2007-07-18
• 公開（公告）號: CN101082923A
• 公開（公告）日: 2007-12-05
• 發(fā)明（設計）人: 謝鯤;閔應驊;張大方;文吉剛;謝高崗
• 申請（專利權）人: 湖南大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 長沙正奇專利事務所有限責任公司
• 代理人: 馬強

1、一種可擴展布魯姆過濾器查詢方法，其特征在于，該方法為：

1)布魯姆過濾器的擴展：當可擴展布魯姆過濾器SBF所表示的集合元素增長超過可擴展布魯姆過濾器容量限制時，添加一個長度為前一個可擴展布魯姆過濾器向量的2倍的向量，即添加了可擴展布魯姆過濾器向量的向量長度m_i＝2m_i-1，此時添加了可擴展布魯姆過濾器向量的向量容量限制也為前一個向量容量限制的2倍，即n_i＝2n_i-1；

2)可擴展布魯姆過濾器元素查詢步驟：

第一步：利用SBF查詢元素x是否在集合S中，令j＝i；

第二步：通過k個哈希函數(shù)計算x在SBF_j的k個映射位，檢查所有位是否都為1；

第三步：所述結果為是時，元素x是SBF_j表示的元素，x在集合S中，返回True；

第四步：所述結果為否時，元素x不是SBF_j表示的元素，需要繼續(xù)檢查x是否為SBF_j-1表示的元素，j←j-1，轉到第二步持續(xù)檢查x是否為當前向量SBF_j直至j＝-1。

2、一種如權利要求1所述可擴展布魯姆過濾器查詢方法的元素插入方法，其特征在于，若c為SBF已經(jīng)表示的元素個數(shù)，則所述可擴展布魯姆過濾器SBF查詢方法的元素插入流程為：

第一步，新元素x插入SBF時，首先檢查c≥Σj=0inj]]>成不成立；

第二步，如果步驟1中式成立，創(chuàng)建新的過濾器向量SBF_i+1，通過k個哈希函數(shù)計算x在SBF_i+1的k個映射位，并置位，將x插入到SBF_i+1中，c←c+1，i←i+1；

第三步，如果步驟1中式不成立，通過k個哈希函數(shù)計算x在SBF_i的k個映射位，并置位，將x插入到當前過濾器向量SBF_i中，c←c+1。