[發(fā)明專利]一種基于主動哈希和布隆過濾器的高效緩存方法有效
| 申請?zhí)枺?/td> | 201310237798.7 | 申請日： | 2013-06-17 |
| 公開（公告）號： | CN103294822A | 公開（公告）日： | 2013-09-11 |
| 發(fā)明（設(shè)計）人： | 劉建偉;馬妍 | 申請（專利權(quán)）人： | 北京航空航天大學(xué) |
| 主分類號： | G06F17/30 | 分類號： | G06F17/30 |
| 代理公司： | 北京慧泉知識產(chǎn)權(quán)代理有限公司 11232 | 代理人： | 王順榮;唐愛華 |
| 地址： | 100191*** | 國省代碼： | 北京;11 |
| 權(quán)利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關(guān)鍵詞： | 一種 基于 主動 過濾器 高效 緩存 方法 | ||
1.一種基于主動哈希和布隆過濾器的高效緩存方法，其特征在于：該方法的具體步驟如下：
步驟一：計算待查找關(guān)鍵詞的哈希值，定位對應(yīng)的哈希鏈表；
步驟二：計算布隆過濾表標(biāo)記位的坐標(biāo)，查找到對應(yīng)的布隆過濾表中標(biāo)記位值；即由高效查找模塊中的標(biāo)記生成單元完成，結(jié)果保存到全局存儲模塊中的過濾表數(shù)組單元中；
步驟三：檢測所有標(biāo)記位的值，若全為1，則無法過濾，進行步驟四，只要有一位為0，即可判斷出關(guān)鍵詞不存在，可行過濾，進行步驟十一；
步驟四：遍歷鏈表的下一個節(jié)點；
步驟五：判斷該節(jié)點的數(shù)據(jù)是否與關(guān)鍵詞匹配，“是”進行步驟六，“否”進行步驟七；
步驟六：查詢已經(jīng)命中，讀取該節(jié)點訪問次數(shù)，判斷該值是否超過該節(jié)點所述鏈表的最大訪問次數(shù)，“是”進行步驟八，“否”進行步驟十；所述的“讀取該節(jié)點訪問次數(shù)，判斷該值是否超過該節(jié)點所述鏈表的最大訪問次數(shù)”是由高效查找模塊中的閾值判斷單元完成，其讀取的數(shù)據(jù)來源于全局存儲模塊中的全局統(tǒng)計量單元；
步驟七：判斷下一個節(jié)點是否為空，“是”回到步驟四，“否”進行步驟十一；
步驟八：判斷節(jié)點是否已經(jīng)處于鏈表頭部，“是”進行步驟十，“否”進行步驟九；
步驟九：移動鏈表至表頭，先將鏈表從表中摘下，再插入到表頭即可；
步驟十：更新表頭最大訪問次數(shù)；
步驟十一：返回查詢失敗。
2.根據(jù)權(quán)利要求1所述的一種基于主動哈希和布隆過濾器的高效緩存方法，其特征在于：在步驟一中所述的“計算待查找關(guān)鍵詞的哈希值，定位對應(yīng)的哈希鏈表”，其計算定位對應(yīng)的哈希鏈表節(jié)點，是由哈希尋址模塊中的ELF哈希單元和尋址定位單元完成，結(jié)果保存到全局存儲模塊中的哈希表數(shù)組單元中。
3.根據(jù)權(quán)利要求1所述的一種基于主動哈希和布隆過濾器的高效緩存方法，其特征在于：在步驟三中所述的“檢測所有標(biāo)記位的值”是由高效查找模塊中的布隆過濾單元完成，其讀取的數(shù)據(jù)來源于全局存儲模塊中的過濾表數(shù)組單元。
4.根據(jù)權(quán)利要求1所述的一種基于主動哈希和布隆過濾器的高效緩存方法，其特征在于：在步驟四中所述的“遍歷鏈表的下一個節(jié)點”為計算機的基本鏈表操作，是直接對全局存儲模塊中的哈希表數(shù)組單元進行操作。
5.根據(jù)權(quán)利要求1所述的一種基于主動哈希和布隆過濾器的高效緩存方法，其特征在于：在步驟五中所述的“判斷該節(jié)點的數(shù)據(jù)是否與關(guān)鍵詞匹配”，是由高效查找模塊的查詢匹配單元完成，直接對全局存儲模塊中的哈希表數(shù)組單元進行操作。
6.根據(jù)權(quán)利要求1所述的一種基于主動哈希和布隆過濾器的高效緩存方法，其特征在于：在步驟七中所述的“判斷下一個節(jié)點是否為空”為計算機的基本鏈表操作，直接對全局存儲模塊中的哈希鏈頭數(shù)組單元進行判斷操作。
7.根據(jù)權(quán)利要求1所述的一種基于主動哈希和布隆過濾器的高效緩存方法，其特征在于：在步驟八中所述的“判斷節(jié)點是否已經(jīng)處于鏈表頭部”，為計算機的基本鏈表操作，直接對全局存儲模塊中的哈希鏈頭數(shù)組單元進行判斷操作。
8.根據(jù)權(quán)利要求1所述的一種基于主動哈希和布隆過濾器的高效緩存方法，其特征在于：在步驟九中所述的“移動鏈表至表頭，先將鏈表從表中摘下，再插入到表頭即可”是由高效查找模塊中的主動哈希單元完成，該功能為基本鏈表操作的組合。
9.根據(jù)權(quán)利要求1所述的一種基于主動哈希和布隆過濾器的高效緩存方法，其特征在于：在步驟十中所述的“更新表頭最大訪問次數(shù)”,是由高效查找模塊中的更新信息單元完成，結(jié)果保存到全局存儲模塊中的全局統(tǒng)計量單元中。
10.根據(jù)權(quán)利要求1所述的一種基于主動哈希和布隆過濾器的高效緩存方法，其特征在于：在步驟十一中所述的“返回查詢失敗”，是由高效查找模塊的布隆過濾單元;如果過濾器不理想時，也會由查詢匹配單元完成，如果為理想過濾器時，全部由布隆過濾單元完成。
該專利技術(shù)資料僅供研究查看技術(shù)是否侵權(quán)等信息，商用須獲得專利權(quán)人授權(quán)。該專利全部權(quán)利屬于北京航空航天大學(xué)，未經(jīng)北京航空航天大學(xué)許可，擅自商用是侵權(quán)行為。如果您想購買此專利、獲得商業(yè)授權(quán)和技術(shù)合作，請聯(lián)系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/201310237798.7/1.html，轉(zhuǎn)載請聲明來源鉆瓜專利網(wǎng)。
