面向缺失數(shù)據(jù)的布魯姆近似成員查詢算法*

吳佳雯 ，王宇科 ，裴書玉 ，謝 鯤 ，劉楚達

(1.湖南大學 信息科學與工程學院，湖南 長沙 410082；2.湖南大學 校園信息化建設與管理辦公室，湖南 長沙 410082；3.長沙航空職業(yè)技術學院，湖南 長沙 410082)

0 引言

標準的布魯姆過濾器(Bloom Filter，BF)[1]是一個空間效率很高的數(shù)據(jù)結(jié)構，它可以表示集合并支持集合的成員查詢，快速判斷查詢元素是否在集合中。當給定一個查詢元素e 時，它被用來回答查詢元素是否在這個集合。一個標準的布魯姆構造一個長度為m 的比特位數(shù)組，初始化為0。在插入階段，它使用k 個獨立的哈希函數(shù)h1(·)，…，hk(·)來計算插入元素在數(shù)組中對應的k 個哈希位置h1(e)%m，…，hk(e)%m，并將這k 個哈希位置置位為“1”。在查詢階段，通過檢查是否所有的k 個哈希位置都置位為“1”，來判斷元素是否在集合中。如果它們都置位為“1”，則認為查詢元素e 在集合S 中；否則，則認為查詢元素e 不在集合S 中。

現(xiàn)有標準布魯姆過濾器通常用于常規(guī)的精確匹配的成員集合查詢(Exact-matching Membership Query，EMQ)，即：檢查查詢數(shù)據(jù)本身是否存儲在布魯姆過濾器，它是否是集合的一個成員。布魯姆過濾器作為一種空間精簡、查詢高效的支持成員集合查詢結(jié)構，一直被廣泛用于各種實際應用中[2-3]。在網(wǎng)絡領域應用中，布魯姆過濾器可以用來存儲防火墻海量的黑名單數(shù)據(jù)[4]，以及在網(wǎng)站中進行內(nèi)容去重等[5]。在大數(shù)據(jù)應用中，例如HBase 中使用布魯姆過濾器來減少代價高昂的I/O 次數(shù)，提升數(shù)據(jù)庫查詢效率[6]。

然而，在新興的網(wǎng)絡應用中，傳統(tǒng)的布魯姆過濾器所提供的精確匹配已不足以應對各種各樣的網(wǎng)絡應用需求。這些應用要求現(xiàn)有算法可以對數(shù)據(jù)進行近似成員查詢(Approximate Membership Query，AMQ)[7]。與精確匹配不同的是，如果AMQ 返回肯定的結(jié)果，那么這里存在兩種情況：第一是查詢元素本身存在于BF 中，第二是查詢元素本身在某個范圍內(nèi)與BF 中存儲的一條或多條元素近似。AMQ 是給定距離度量下，考察查詢數(shù)據(jù)與集合S 中任意成員的接近程度。這個距離的度量可以是漢明距離(Hamming distance)[8]、歐氏距離(Euclidean distance)[9]等。AMQ 常常應用在各種領域，如信息中心網(wǎng)絡(Information-Centric Networking，ICN)[10-12]利用AMQ 來進行IP路由選擇，在圖像檢索領域使用AMQ 進行相似圖像檢索等。

近些年來針對AMQ 的布魯姆過濾器研究得到了學術界越來越多的關注[7，13-15]。Kirsch 等人最先將局部敏感哈希函數(shù)(Locality-Sensitive Hashing，LSH)[15]和BF 結(jié)合，提出距離敏感的布魯姆近似查詢算法(Distance-Sensitive Bloom Filters，DSBF)[9]。在DSBF 基礎上，Qian Jiangbo 等人提出了一種漢明多粒度局部敏感布魯姆過濾器(Hamming Metric Multi-Granularity Locality-Sensitive Bloom Filter，HLBF)[7]，HLBF 支持不同粒度漢明距離的近似成員查找。

然而這些支持近似成員查詢的布魯姆過濾器結(jié)構都有一個共同的局限性。存儲和查詢元素必須是完整的數(shù)據(jù)，無法處理請求查詢含有缺失數(shù)據(jù)的情況?，F(xiàn)實生活中的數(shù)據(jù)集合并不是完整無缺的，它們元素通常為高維空間的元素，高維數(shù)據(jù)往往還伴隨著維度冗余的情況，且存在數(shù)據(jù)缺失。

為了解決這個問題，本文提出一種面向缺失數(shù)據(jù)的布魯姆近似查詢算法。它先對缺失數(shù)據(jù)進行預填充，再通過PCA(Principal Component Analysis，PCA)算法[16]將高維數(shù)據(jù)轉(zhuǎn)換到低維數(shù)據(jù)，使用低維數(shù)據(jù)進行布魯姆的近似查詢。在近似查詢中，采用局部敏感哈希函數(shù)與標準哈希函數(shù)結(jié)合的方式來插入、查詢低維數(shù)據(jù)。本文使用局部敏感哈希函數(shù)中AND 和OR 操作相結(jié)合的方法進一步降低算法的假陽性率與假陰性率，提高了算法的性能。本文在真實數(shù)據(jù)集上對所提算法進行了驗證，充分證明所提算法有效地解決了存在缺失數(shù)據(jù)的情況下近似成員的查詢問題。

1 方案概述

本文設計一個新穎的布魯姆結(jié)構，用來實現(xiàn)面向高維缺失數(shù)據(jù)的近似成員查詢。近似成員查詢指的是，當查詢元素與現(xiàn)有集合中的某些元素在某個范圍內(nèi)相似時，該查詢元素就被視為集合的一個近似成員。本文給出近似成員查詢的基本定義如下：

定義1(近似成員查詢)給定一個距離參數(shù)R、元素集合S，查詢元素q 被視為近似于集合S，當且僅當：?p∈S，||q，p||≤R，其中，||*||表示q 與p 之間 的距離，距離的度量方式可以是漢明距離、歐氏距離等。當R=0時，該查詢就是一個精確的成員查詢，因此精確查詢可視為是一個特殊的近似查詢。

設計的面向缺失數(shù)據(jù)的布魯姆近似查詢算法的方案如圖1 所示，主要分為3 個步驟：

圖1 面向缺失數(shù)據(jù)的布魯姆近似成員查詢方案

(1)填充高維的缺失數(shù)據(jù)。缺失的原始數(shù)據(jù)無法直接在布魯姆過濾器中存儲/查詢，需要對缺失的數(shù)據(jù)進行填充；

(2)基于PCA 技術，將高維填充數(shù)據(jù)降維表示到低維空間，去除不相關屬性，提取出數(shù)據(jù)的重要特征；

(3)在插入階段，利用LSH 哈希函數(shù)族為降維后數(shù)據(jù)生成L 個獨立的組，每一組看作是原數(shù)據(jù)的哈希值表示。并將每一組作為一個整體輸入，再通過b個傳統(tǒng)隨機哈希函數(shù)進行哈希運算，對映射在BF 上的哈希位置置位為“1”，完成低維數(shù)據(jù)在布魯姆過濾器的存儲。

2 詳細設計

2.1 缺失數(shù)據(jù)預填充與PCA 降維

由于原數(shù)據(jù)帶有缺失，而使用PCA 降維[16]的數(shù)據(jù)需要維度對齊，因此需處理數(shù)據(jù)的缺失處。

具體地，首先計算出原始數(shù)據(jù)每個維度無缺失處的均值，記錄下各個維度的均值，并使用維度均值補全缺失處的值，以上即為對數(shù)據(jù)的初步處理操作。

接著，將處理后的數(shù)據(jù)組織成一個n×d 的矩陣X，X中每行代表一條數(shù)值向量，每列代表一個維度。并使用標準的PCA 降維技術：矩陣去中心化X—協(xié)方差矩陣計算—選取投影矩陣P—降維計算×P，至此，完成了缺失數(shù)據(jù)的預處理和降維操作。

2.2 插入算法

在PCA 降維后，使用降維后的數(shù)據(jù)作為下一階段的輸入數(shù)據(jù)進行插入操作，具體地：

(1)利用p-stable LSH[9]得到L 個哈希值的集合，哈希函數(shù)為h(a，e)=(a·v+e)/w」，其中v 為輸入數(shù)據(jù)，a 為與v 維度相同的一個隨機向量，a 中的每個分量均從p-stable 分布中獲取，w 為桶寬，e 是一個大于等于0且不大于w 的隨機數(shù)。本文在高斯分布中選取a 的值，通過變換a 和e 的取值得到一個大小為k 個的哈希值集合：

其中，hj(1≤j≤k)表示利用p-stable LSH 得到的第j 個哈希值，一個gi組包含k 個哈希值，gi(1≤i≤L)表示第i組哈希值集合，重復上述生成一個組的步驟，一共生成L 個組。

(2)將每個gi組作為輸入，使用b 個獨立的隨機哈希函數(shù)將其映射到布魯姆過濾器的b 個位置。具體地，一個標準的隨機哈希函數(shù)將一個gi組映射為一個值，然后將該值模上位數(shù)組大小得到一個數(shù)值，這個數(shù)值即為插入的位置。此步驟可表示為：

其中，Hl(*)表示第l 個標準的隨機哈希函數(shù)，m 表示位數(shù)組大小，indexl表示使用第l 個哈希函數(shù)定位到的位置，然后將位數(shù)組中第indexl位的值置為1。重復上述第二階段，使得L 組gi都被映射到布魯姆過濾器位數(shù)組中，這樣就完成了一次插入操作。綜上所述，對于每一條輸入數(shù)據(jù)，位數(shù)組中共有L×b 個位置被置為“1”。

2.3 查詢算法

布魯姆過濾器的查詢操作一般發(fā)生在插入操作完成之后。帶有缺失的查詢數(shù)據(jù)在使用近似查詢布魯姆過濾器進行近似查詢之前，同樣需要對數(shù)據(jù)進行預填充和PCA 降維處理。使用降維后的數(shù)據(jù)作為輸入數(shù)據(jù)在布魯姆中查詢，具體地：

(1)與插入算法的第一步相同，使用p-stable LSH 函數(shù)得到L 組哈希值集合{g1，…，gL}，其中每一組gi包含k 個哈希值，即：gi={h1，h2，…，hk}。相似查詢中，相近 的值可能會落于相鄰的桶中，因此與插入操作不同是，除了每一組gi，還需要擴展每一組哈希值集合gi為2k 組哈希值集合，作為下一步隨機哈希函數(shù)的輸入。

(2)將每一組gi和由它擴展的2k 組哈希值集合(1≤j≤2k)，一共作2k+1 組哈希函數(shù)集合，作為隨機哈希函數(shù)輸入。計算每一組哈希函數(shù)映射到布魯姆的b 個位置，判斷b 個位置是否全部被置為“1”。

如圖2 所示，將每一組gi擴展成2k 組哈希值集合的方式是：對于組中{h，h，…，h}每一個哈希值，將其12k值減1 而其他值保持不變得到一組哈希值集合，然后將其值加1 而其他值保持不變得到另一組哈希值集合，這樣原來的一組哈希值集合gi就擴展成了2k 組哈希值集合，1≤j≤2k，即：

圖2 近似成員查詢操作

對于每組哈希值集合gi和它對擴展的2k 組哈希值集合，若任意一組在BF 的b 個索引位置都被置為1，則查詢元素存在。否則，查詢數(shù)據(jù)與給定集合并不相似。

2.4 假陽性分析

假陽性率出現(xiàn)在原數(shù)據(jù)不與插入到布魯姆過濾器中的集合近似，但是查詢結(jié)果返回true 的時候，也就是說算法誤認為在插入集合中存在與查詢數(shù)據(jù)相近的數(shù)據(jù)。因此，假陽性誤判率由兩個部分組成：局部敏感哈希產(chǎn)生的假陽性誤判率、標準哈希函數(shù)產(chǎn)生的假陽性誤判率，因此假陽性率可表示為：

其中，PLSH表示由局部敏感哈希產(chǎn)生的假陽性誤判率，F(xiàn)PRSBF表示由帶有b 個哈希函數(shù)的標準布魯姆過濾器產(chǎn)生的誤判率。

其中，L 表示組數(shù)，k 表示每組包含的哈希值個數(shù)，n 表示插入到布魯姆過濾器中數(shù)據(jù)的個數(shù)，C 是常量，x(?)可表示為：

其中，a 是和原數(shù)據(jù)維度相同的隨機向量，w 表示桶寬，e為[0，w]范圍內(nèi)的隨機數(shù)。

又由[7]可知，在標準的BF，其假陽性誤判率為：

其中，m 表示位數(shù)組大小，b 表示使用的標準哈希函數(shù)個數(shù)，k 表示每組包含的哈希值個數(shù)。

2.5 假陰性分析

算法的假陰性發(fā)生在局部敏感哈希函數(shù)產(chǎn)生假陰性并且在查詢布魯姆過濾器位數(shù)組時b 個位置不都為1。因此根據(jù)假陽性率的分析可得，算法的假陰性率為：

3 實驗評估

3.1 數(shù)據(jù)集介紹

本文實驗所使用的數(shù)據(jù)均來自真實數(shù)據(jù)集。

(1)CoverType 數(shù)據(jù)集

CoverType 數(shù)據(jù)集[17]屬于一個分類數(shù)據(jù)集，該數(shù)據(jù)集有581 012 條不含缺失的數(shù)據(jù)，每條數(shù)據(jù)包含54 個維度，數(shù)據(jù)集線性不可分。具體來說，這54 個屬性包括10個定量變量、4 個二元荒野地區(qū)和40 個二元土壤類型變量。

(2)HandWrite 數(shù)據(jù)集

手寫字體識別數(shù)據(jù)集[17]是一個分類數(shù)據(jù)集，共有5 620個不重復且無缺失數(shù)據(jù)，每條數(shù)據(jù)都有64+1 個維度，其中前64 個維度都是0～16 之間的整數(shù)，最后一個維度是數(shù)據(jù)的標簽。

3.2 評價指標

假陽性誤判率(False Positive Rate，F(xiàn)PR)，如果一個查詢數(shù)據(jù)不近似于插入到布魯姆過濾器中的數(shù)據(jù)集合，但是查詢返回true，這就是一個假陽性錯誤。

假陰性誤判率(False Negative Rate，F(xiàn)NR)，如果一個查詢數(shù)據(jù)近似于插入到布魯姆過濾器中的數(shù)據(jù)集合，但是查詢返回false，這就是一個假陰性錯誤。

3.3 實驗結(jié)果及分析

為了檢驗近似查詢布魯姆過濾器的參數(shù)與查詢速率以及誤判率之間的關系，本節(jié)進行了參數(shù)實驗，并固定布魯姆過濾器位數(shù)組大小為m=224bit，使用的標準隨機哈希函數(shù)的個數(shù)為b=3。插入到布魯姆過濾器中的數(shù)據(jù)量為7 413 條，查詢數(shù)據(jù)為3 177 條，總?cè)笔蕿?.005。

圖3 是在數(shù)據(jù)集CoverType 下，固定條件(數(shù)據(jù)降到10 維、w=12、k 變 化時L=3、L 變 化時k=7) 下，L 與k 的值不斷增加時，平均每條數(shù)據(jù)近似查詢所需的時間曲線圖。由圖可知，當二者取值不斷增加時，平均查詢時間也隨之增加，其中查詢時間隨k 呈指數(shù)增加，隨L 呈線性增加。這是由于k 增加意味著每個gi組包含的哈希值增多，哈希計算所需時間增多，并且一個gi組除了自身外，還需檢查2k 個擴展組，因此平均查詢時間隨k 呈指數(shù)增加，隨L 呈線性增加。

圖3 平均查詢時間

圖4 為在CoverType 和HandWrite 數(shù)據(jù)集下，假陽性誤判率、假陰性誤判率的隨L 變化曲線圖。由圖可看出在兩個數(shù)據(jù)集中，當L 增加時，假陽性率均隨之增加。

圖4 兩個數(shù)據(jù)集下不同L 取值的誤判率

圖5 為在CoverType 和HandWrite 數(shù)據(jù)集下，假陽性誤判率、假陰性誤判率隨每組哈希函數(shù)個數(shù)k 變化的曲線圖。當k 增加時，每個組的哈希值越多，在進行映射時，要將組內(nèi)哈希值作為一個整體插入到位數(shù)組中，因此哈希值越多，組與組之間差異越大，碰撞的概率越小，假陽性率隨之降低，假陰性率隨之上升。

圖5 兩個數(shù)據(jù)集下不同k 取值的誤判率

圖6 為在兩個數(shù)據(jù)集中，算法假陽性誤判率以及假陰性誤判率隨p-stable LSH 哈希函數(shù)中桶寬w 的變化曲線圖，從圖中可看出，算法假陽性率隨著w 的增加而增大，假陰性率隨著w 的增加而減小。這是由于w 越大意味著桶寬越大，因此近似范圍越大，落入同一桶的數(shù)據(jù)越多，哈希沖突的概率越大，假陽性率越大，同時相近的值越可能落入同一個桶，因此假陰性率越小。

圖6 不同w 下的誤判率

圖7 為在數(shù)據(jù)集CoverType 中，本節(jié)方案在不同的近似距離下誤判率變化曲線圖，實驗時本方案將數(shù)據(jù)維度從54 維降到8 維，使用L=4 個組，每組使用k=6 個局部敏感哈希函數(shù)，同時設置桶寬w=12。圖中顯示隨著近似性度量的歐氏距離增加，假陰性誤判率漸漸增加，這是因為當距離增加，認為距離較遠的點也近似于插入集合，但是原有的判定條件以及參數(shù)均不變，所以對于假陰性誤判率，其分母真陽性數(shù)增加，但是原有的查詢數(shù)目不變，而假陰性數(shù)目=真陽性數(shù)-查詢出true 的數(shù)目，所以當真陽性數(shù)tp 增加時，假陰性誤判率增加。同理，對于假陽性誤判率，當真陰性數(shù)減小時，假陽性誤判率減少。

圖7 不同歐式距離下的誤判率

表1 中，在兩個數(shù)據(jù)集下本方案將查詢數(shù)據(jù)降維到不同維度然后進行近似查詢，線性查找(Linear Search)在查詢數(shù)據(jù)具有不同維度時進行暴力查詢。由表可看出，本方案所需的平均查找時間比線性查詢明顯少得多。所謂線性查找就是遍歷插入集合，計算查詢數(shù)據(jù)與每一個插入數(shù)據(jù)的距離并判斷是否小于指定值，若是則認為近似，因此線性查找所需時間與插入集合的數(shù)目有關。但是本文方案基于布魯姆過濾器，所需查找時間僅僅與L、k、b 的值有關，通常這些參數(shù)較小且固定，算法是常數(shù)級查詢時間，所以所需時間代價較小。從表中亦可看出，隨著數(shù)據(jù)維度的降低，兩者所需的平均查詢時間均明顯下降，基于降維的近似查找布魯姆過濾器算法又通過降低查詢數(shù)據(jù)維度進一步加快了查詢速度。

表1 不同維度下算法的平均查詢時間(ms)

4 結(jié)論

本文提出了一種面向缺失數(shù)據(jù)的布魯姆近似成員查詢算法，可以判斷查詢的缺失數(shù)據(jù)是否與存儲在布魯姆中的數(shù)據(jù)相似。本文使用兩個真實數(shù)據(jù)集對所提算法的有效性進行驗證，在假陽性率、假陰性率和查詢時間上，優(yōu)于當前基于線性搜索的近似查詢算法。