[發明專利]一種高精度多維計數布魯姆過濾器及其大數據處理方法

有效

• 申請號: 201210590482.1
• 申請日: 2012-12-31
• 公開（公告）號: CN103020296A
• 公開（公告）日: 2013-04-03
• 發明（設計）人: 張大方;李瑋;黃昆;謝鯤
• 申請（專利權）人: 湖南大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 長沙正奇專利事務所有限責任公司 43113
• 代理人: 馬強

技術領域

本發明涉及分布式系統、網絡等領域大數據處理，具體是指基于高精度多維計數布魯姆過濾器的大數據處理方法。

背景技術

未來的十年將是一個大數據引領的時代。大數據有三個典型特征：1）數據結構復雜，元素屬性多維化。如數字城市中空間數據具有三維坐標、地形等多維屬性；網絡Trace海量數據包具有源IP、目的IP、協議等多維屬性；2）數據價值密度低。價值密度的高低與數據總量的大小成反比。以視頻為例，一部一小時的視頻，在連續不間斷監控過程中，可能有用的數據僅僅只有一兩秒；3）數據動態變化更新快。如何在快速變化的海量數據中通過高精度的數據處理方法迅速地完成數據的價值“提純”，成為有效進行大數據處理過程中極具挑戰性的問題。

布魯姆過濾器（B?F,Bloom?Filter）是一種結構精簡的數據過濾方法，雖然它存在稍許查詢誤判，但由于其哈希查找的常數時間和存儲空間開銷較小，從而使它具有很好的實用價值，已廣泛應用于網絡、分布式計算等領域。BF采用長度為m的比特向量V表示n個元素集合S＝{s₁，s₂，...,s_n}，采用k個相互獨立的哈希函數h₁,h₂,..,h_k，其函數取值均勻分布在范圍為[1...m]。插入元素s時，設置V中第h₁(s),h₂(s),...,h_k(s)位為1。查詢元素u時，檢查V中第h₁(u),h₂(u),...,h_k(u)位是否全為1，如果全為1，則元素u在S中；否則，元素u不在S中。后面章節中采用三元組{n,m,k,}形式化表示單維屬性布魯姆過濾器，用四元組{n,m,k,L}表示多維屬性布魯姆過濾器。n為集合S中元素個數，m為向量V的長度，k為哈希函數的個數，L為元素屬性維數。

但目前布魯姆過濾器的研究主要集中在單維元素的處理，如標準布魯姆過濾器、計數布魯姆過濾器、光譜布魯姆過濾器，拆分型布魯姆過濾器、分檔布魯姆過濾器、索引拆分布魯姆過濾器等。這些算法從不同角度討論和優化布魯姆過濾器的設計以滿足實際應用的不同需求。目前存在少數針對多維元素處理的布魯姆過濾器方法，如MDBF（Multi-Dimension?Bloom?Filte）、CMDBF（Combined?Multi-Dimension?Bloom?Filter)）和PBF-BF（Parallel?Bloom?Filter-Bloom?Filter），但是這些方法由于沒有對多維屬性進行有效的關聯，仍然存在誤判率高的缺點，無法應用于未來大數據環境下多維數據處理精度需求。因此，針對大數據特點，設計出高精度的多維布魯姆過濾器來完成多維元素過濾和更新等大數據處理方法，成為大數據處理中迫切解決的問題。

發明內容

本發明所要解決的技術問題是，針對現有技術不足，提供一種高精度多維計數布魯姆過濾器及其大數據處理方法，更迅速地完成數據的價值“提純”，快速有效地對大數據進行加工處理。

為解決上述技術問題，本發明所采用的技術方案是，高精度多維計數布魯姆過濾器的結構由兩部分組成，即：第一部分是用來存儲多維元素各個屬性的高精度計數布魯姆過濾器，高精度計數布魯姆過濾器是一種基于分層結構的計數布魯姆過濾器，通過高效利用計數器的存儲空間來降低假陽性，提升其處理精度；第二部分是用來存儲元素整體信息的聯合計數布魯姆過濾器，采用雙射函數將元素多維屬性轉換為一維數值來表示元素整體信息，將這個一維數值映射到聯合計數布魯姆過濾器中，聯合元素各屬性值利用聯合計數布魯姆過濾器進行確認。下面分別介紹這兩部分詳細設計。

（1）高精度計數布魯姆過濾器設計

標準布魯姆過濾器不支持刪除操作，從而不支持集合的動態變化，CBF被提出以解決此問題，用計數器替代標準BF中的每個bit位，一般情況下，每個計數器由4個bit組成，最大值為16。CBF使用時，首先將m個計數器初始化為0。元素的插入操作和刪除操作分別將對應的k個計數器加1或者減1。進行元素是否在集合中的判斷時，只需要判斷這k個計數器的值是否都大于1。