郭玲

（珠海城市職業(yè)技術學院，廣東珠海 519090）

基于本地敏感信息過濾的大數(shù)據(jù)查詢優(yōu)化算法研究

郭玲

（珠海城市職業(yè)技術學院，廣東珠海 519090）

在數(shù)據(jù)快速訪問和網(wǎng)絡數(shù)據(jù)快速訪問領域,信息過濾的效率高低直接影響訪問速度，因而信息過濾的性能倍受矚目.通過信息過濾，可以在相對較短時間內(nèi)完成信息檢索并經(jīng)常能夠提供出相應的統(tǒng)計分析結果，并進一步實現(xiàn)了大數(shù)據(jù)檢索的成本降低.因此，如果將信息過濾器技術在大數(shù)據(jù)中應用，將極大提高大數(shù)據(jù)信息檢索的效率.本文基于本地信息的內(nèi)容特征，提出一種基于本地敏感信息過濾的大數(shù)據(jù)查詢優(yōu)化算法，該算法可以有效改善單純依靠精確比對法的檢索性能，從而明顯提高數(shù)據(jù)快速訪問和網(wǎng)絡數(shù)據(jù)快速訪問的速度.

大數(shù)據(jù)；信息過濾；本地敏感信息

1 引言

隨著電子化的快速發(fā)展，人們的日常生活越來越離不開信息化數(shù)據(jù)的幫助.數(shù)據(jù)體積越來越大，不得不消耗更多的內(nèi)存容量進行讀取和訪問，需要研發(fā)更先進的技術來處理這些大量數(shù)據(jù).對如此龐大規(guī)模數(shù)據(jù)的檢索就是其中非常嚴峻的挑戰(zhàn)之一.相比之下，如果想用精確的成員比對查詢（q∈S）還不如使用近似成員比對查詢（q→S），但這樣一來就需要證明近似成員查詢成員q有多么“接近”集合S才算精確.對查詢內(nèi)容進行精確比對，當數(shù)據(jù)量非常大的時候輸出就很難控制.因此暴力查詢精確對象一般會消耗太多的資源，這時近似成員比對查詢就顯得更為實際.同時，使用近似查詢還有助于我們校正錯誤或者不精確的查詢輸入值.實際上這個問題并不是只在大量數(shù)據(jù)查詢領域中存在，對于通過傳統(tǒng)查詢方法無法完全解決的查詢提速問題早已受到關注［1］.對近似成員對比查詢的研究為節(jié)約用戶時間和提升軟件性能提供了一個可能的方向［2］［3］.近似成員對比查詢有助于我們確定數(shù)據(jù)集合S中近似存在成員q的問題，這里的近似成員也會被認為成精確成員.

布隆過濾器在業(yè)務查詢中處理信息錯誤波動概率較低的緊湊集表達方面非常有效［4］.布隆過濾器使用簡單的哈希查詢（如設置并測試0和1的值）時，求解精確比對查詢的運算復雜度是O（1）.該過濾器的距離隔離結構也因此被很多領域采用，比如重負載數(shù)據(jù)流識別［5］、最優(yōu)替換［6］、文本總結［7］、最長前綴匹配［8］、路徑查詢［9］及數(shù)據(jù)包分類［10］都有這種過濾器的應用.但是，標準的布隆過濾器并不支持近似成員比對查詢，而且經(jīng)常會忽略掉可能的近似成員查詢項，這主要是受限于使用統(tǒng)一的獨立哈希函數(shù)（比如MD5、SHA-1等）計算答案是布爾數(shù)據(jù)類型的問題.本地敏感哈希算法對大數(shù)據(jù)中近似成員比對查詢有所幫助，該算法通過將相似項合并，在局部數(shù)據(jù)中避免了布隆過濾器忽略相似項的問題［11］.目前，已有開始嘗試在近似成員合并中引入經(jīng)過優(yōu)化改造的布隆過濾器的研究［12］.本文的研究主要目標是優(yōu)化大數(shù)據(jù)查詢效率，同時避免無效的查詢結果.

本文首先將哈希過程進行優(yōu)化以提高效率，隨后改進布隆過濾器以進一步提升檢索和

查詢的性能.改進的哈希過程和布隆過濾器共同組成了基于本地敏感信息過濾的大數(shù)據(jù)查詢優(yōu)化算法（Local Sensitive Information Filtering based Big Data Inquiry,LSIFBDI）.

2 信息過濾

2.1 引入布隆過濾的重要性

布隆過濾器最早于1970年由Burton H. Bloom發(fā)明.本文以對n個對象組成的數(shù)據(jù)集合S={a1，a2，…，an}形成的m比特向量對應的布隆過濾為例介紹其原理.初始化將過濾器中全部置0.布隆過濾器采用長度為k的獨立哈希函數(shù){h1，h2，…，hn}實現(xiàn)集合S向比特向量的映射.每個哈希函數(shù)hi基于相同的隨機分布生成集合元素ai到m比特向量任意位置的映射.如果每一hi（ai）個的值都是1，那說明確實是集合S的一個成員.對每一個集合成員的判定實質上就是一個正誤識別判定過程.布隆過濾器在組網(wǎng)方面應用非常廣泛.

現(xiàn)在對快速得到精確結果的要求越來越強烈.因為數(shù)據(jù)在網(wǎng)絡中越來越多，那么以便于查找的方式存儲就越來越重要.傳統(tǒng)的數(shù)據(jù)存儲格式看起來能夠應付這種需求，但數(shù)據(jù)描述對象的屬性的差異嚴重限制了傳統(tǒng)存儲格式在解決這類問題方面的能力.大數(shù)據(jù)處理中，輸入數(shù)據(jù)量大到必須進行分割成更小的文件進一步處理，這就需要引入借助哈希函數(shù)的布隆過濾器.

2.2 大數(shù)據(jù)信息過濾建模

仍舊以n個對象組成的數(shù)據(jù)集合S={a1，a2，…，an}為例，假設要進行的查詢是類似“y是否在S中？”的要求，其輸出的答案并非S集合的成員或者子集本身，而是是否存在的一個判定結果.另外，布隆過濾器也是存在容差的.本例中，布隆過濾器先將全部序列值初始化為0再根據(jù)哈希函數(shù)進行映射運算.那么在回答本例中類似問題過程中，并不需要逐一檢測完全部的向量元素值是否為1，只要表征存在y在S中即可.但這樣就有可能出現(xiàn)虛報y存在于S的錯誤.

傳統(tǒng)意義上講，應用布隆過濾器解決一般的查詢問題的優(yōu)勢包括如下幾方面：

（1）運算空間利用率更高：布隆過濾器的長度與被處理數(shù)據(jù)的量之間是線性關系，且與被查詢數(shù)據(jù)具體存儲位置無關.

（2）快速構建：構建布隆過濾器的過程非?？焖?，耗時極少，只要掃描一次數(shù)據(jù)集合就可以完成.

（3）測試歸屬類查詢效率很高：所占用的查詢序列長度通常是常數(shù)，且與被查詢集合的大小相比微乎其微.

（4）設置布隆過濾器長度可節(jié)約查詢時間：但同時需要注意長度過短可能增大上文提到的虛報問題.

2.3 映射與化簡

映射與化簡是并行處理數(shù)據(jù)量在TB以上級別數(shù)據(jù)時應以的一種編程模型.

正如其名，映射與化簡函數(shù)包含映射功能和化簡功能.映射過程選取一組數(shù)據(jù)將其映射為另外的數(shù)據(jù)，比如將各項物品的數(shù)據(jù)拆分并重新以特定的符號進行簡化替代用于后續(xù)數(shù)據(jù)處理的過程就是典型的映射過程.化簡過程以映射的輸出作為其輸入，將映射的結果壓縮為更小的集合.程序框架自動排序映射過程的結果，將最近似的一組結果向化簡函數(shù)輸出.輸入和輸出存儲在文件系統(tǒng)中.框架則負責任務的調(diào)度、構建、進度監(jiān)控和結束錯誤進程.化簡過程的輸出結果最終作為整體輸出.映射與化簡框架與Hadoop分布式文件系統(tǒng)同時并行在存儲文件系統(tǒng)中同一個節(jié)點上運行.這種方式有效降低了可能引發(fā)的在節(jié)點之間傳輸大量過程量的風險. Hadoop平臺中設置一個獨立運行的總控進程，每一個節(jié)點上存在一個本節(jié)點的從屬進程.從屬進程接受總控進程對數(shù)據(jù)處理的調(diào)度，總控進程則需控制全部從屬進程運行和銜接管理.

2.4 布隆過濾器中的哈希過程

哈希過程實質上是將通常以字符串格式存儲的數(shù)據(jù)轉化為一個長度更小、大小幾乎固定的數(shù)值，這個數(shù)值在哈希函數(shù)內(nèi)部可以識別其所代表的字符串.正是由于這一點，哈希函數(shù)所存儲的僅僅是m比特的哈希值而非字符串本身，因此在索引和取值操作中大量應用哈希過程加快程序相應速度、提高執(zhí)行效率.布隆過濾器也是應用哈希函數(shù)將原始數(shù)值轉換為哈希值存儲在過濾器中的.

3 本地敏感信息哈希過程

定義哈希函數(shù)為：

其表達域可以表示為（R，cR，P1，P2），該函數(shù)對距離敏感，可表述為：

圖1 哈希過程的數(shù)據(jù)表示意圖

對于相似搜索，假設c>l且P1>P2，那么每個哈希函數(shù)ha，b可以映射一個d長度的向量v到一系列整數(shù)上去.哈希函數(shù)IH可以通過下式計算：

其中，a是根據(jù)一個有s個穩(wěn)態(tài)的分布函數(shù)生成的d長度的隨機向量，b是從區(qū)間[0，w）中選取的任意實數(shù)，w為常數(shù).

圖2 對兩元素的哈希檢索示意圖

研究通過多個哈希函數(shù)實現(xiàn)的相似檢索，只對兩個元素（P1和P2）檢索，且兩元素的存儲距離足夠大（c>l），如圖2所示.本地敏感信息檢索過程測量元素的存儲距離來計算亮點之間近似位置.如果將q看做是以R為半徑的圓，點P1處于圓內(nèi)，那么這個點處于q的近點，本地敏感哈希過程將繼續(xù)擴大其半徑至cR，此時P2進入了圓的范圍，但是P3仍不在圓內(nèi).

對應到基于本地敏感信息的哈希檢索過程，圖2的含義為由多張哈希表決定的P1和P2均被檢索到，但相對來講P1的敏感度更高.而P3則不是該哈希過程的檢索結果.

4 本地敏感信息布隆過濾器設計

為了進一步提高上節(jié)設計的哈希查詢的準確性，同時更好地克服虛報的問題，布隆過濾器也需要進一步改進.本文在應用改進的哈希查詢的基礎上，在布隆過濾器設計中引入了逐比特驗證算法來減輕虛報問題的影響，同時也可降低誤判的概率.改進的濾波器由L個本地敏感哈希函數(shù)gi（q）（1≤i≤L）將數(shù)據(jù)分類至哈希緩存表.基于哈希查詢，通過檢查對象的本地位置信息可以將之映射至哈希表中相應位置，這個過程中哈希表的值可能被多次修改，但是僅第一次修改值有效，這樣保證了修改效果的誤操作.集合S的所有成員將分散到一個m比特的向量中.這樣設計的濾波器在執(zhí)行對q的查詢或者基于哈希查詢插入一個成員值的時候，實際上是執(zhí)行對L比特的哈希距離gi（q）（1≤i≤L）的計算.如果全部L個比特的值均為1，則判定q確實在集合S中.圖3給出了這一設計的示意圖.

圖3 本地敏感信息布隆過濾器示意圖

為了便于檢查哈希結果，每一比特計算的輸出如果為1代表所查詢的成員在集合S中，如果全部比特均顯示為1代表所查詢的對象是集合S的近似成員，也即完成了本次查詢.

5 本地敏感信息查詢優(yōu)化算法實現(xiàn)

布隆過濾器通過哈希查詢將對象進行標記來存儲數(shù)據(jù)，那么這一算法就可以用于大數(shù)據(jù)的信息檢索了.大數(shù)據(jù)的內(nèi)容可能包含多種格式，比如.doc、.jpg、.mpeg、.xls，還可能存在其他格式的視頻、音頻等等，但是在內(nèi)存中這些均存儲成了不同的0或1.那么在公共存儲區(qū)存儲不同類型的數(shù)據(jù)時，數(shù)據(jù)格式就顯得非常重要了.好的數(shù)據(jù)格式選擇將大幅降低檢索耗時，相似格式的數(shù)據(jù)也便于存儲在鄰近的位置.因為大數(shù)據(jù)的查詢過程是先進行映射，映射的結果再合并成最終的檢索結果，所以應采取本文提出的改進算法進行數(shù)據(jù)的存儲和檢索.

本文所提出的算法，以類程序結構表述如下：

6 算法性能評估

為檢驗LSIFBDI的性能，本文提取了某在線教學課程網(wǎng)站的后臺數(shù)據(jù)作為數(shù)據(jù)處理的基礎.分別應用LSIFBDI和傳統(tǒng)的精確查詢（Traditional Exact Inquiry,TEI），對給定的課程或學習信息進行查詢操作.分別檢查兩種算法在查詢準確率（查詢到的記錄與實際存儲的記錄之間的比例）、查詢占用內(nèi)存比例（為方便對比，以精確查詢占用內(nèi)存為基礎系數(shù)1，換算LSIFBDI的占用內(nèi)存比例）、LSIFBDI算法在設置不同的過濾器位數(shù)時誤報和漏報的比例.

首先，我們對比LSIFBDI與TEI在查準率方面的性能.當數(shù)據(jù)量較小的時候，兩者的查準率相差很小.但是隨著數(shù)據(jù)量的增大，LSIFBDI的查準率能夠仍然維持在相對穩(wěn)定的水平上，但是TEI的查準率則出現(xiàn)了不規(guī)則的抖動，如圖4所示.

圖4 查準率對比圖

隨后，本文研究了兩算法查詢占用內(nèi)存比例關系，為方便對比，以TEI占用內(nèi)存量為基礎，以LSIFBDI占用內(nèi)存是TEI占用內(nèi)存的倍數(shù)進行數(shù)據(jù)呈現(xiàn)，如圖5所示.可見，隨著數(shù)據(jù)量的增大，LSIFBDI占用內(nèi)存相對于TEI出現(xiàn)非常明顯的降低.

圖5 內(nèi)存占用量比較

最后，本文對比了LSIFBDI算法在設置不同的過濾器位數(shù)時誤報和漏報的比例.隨著過濾器位數(shù)的上升，錯報和漏報比例均出現(xiàn)了明顯的下降.但當過濾器位數(shù)達到一定長度后，錯報和漏報比例幾乎不變，如圖6所示.可見，在設置LSIFBDI算法過濾器長度時，不必一味追求精度而增加濾波器長度.

圖6 LSIFBDI算法漏報與錯報比例

7 結語

提升信息的快速訪問和檢索的性能是大數(shù)據(jù)應用的重要技術難點.基于本地信息特征，本文提出了一種基于本地敏感信息過濾的大數(shù)據(jù)查詢優(yōu)化算法（Local Sensitive Information Filtering based Big Data Inquiry,LSIFBDI），該算法可以在大數(shù)據(jù)查詢中替代傳統(tǒng)的精確查詢算法，用以提高查詢的精度和消耗的時間同時達到降低內(nèi)存占用的效果.本文將所提算法與傳統(tǒng)算法進行對比，在查準率、內(nèi)存占用量、漏報與錯報方面所提算法均有較好表現(xiàn).通過查詢項之間存儲距離的計算，本文提出的算法可以更好地處理相似項的檢索問題.數(shù)據(jù)驗證可證明本文所提算法在查詢精度和資源消耗方面的性能提升.

［1］L.Carter,R.Floyd,J.Gill,Markowsky and Wegman, Exact and Approximate Membership Testers［C］,Proc. 10th Ann.ACM Symp.Theory of Computing,1978:59-65.

［2］孫炯寧.基于混合式子樹算法的大數(shù)據(jù)匿名化［J］.南京理工大學學報,2015（5）:950-961.

［3］覃雄派,王會舉,杜小勇,王珊.大數(shù)據(jù)分析——RDBMS與MapReduce的競爭與共生［J］.軟件學報,2012（1）: 6-13.

［4］Y.Zhu and H.Jiang,False Rate Analysis of Bloom Filter Replicas in Distributed Systems［C］,Proc.Int’1 Conf.Parallel Processing,2006:255-262.

［5］W.ChangFeng,Kandlur,SahaandK.G.Shin, Stochastic Fair Blue:A Queue Management Algorithm forEnforcingFairness［C］,Proc.IEEEINFOCOM, 2001.

［6］李建中,劉顯敏,大數(shù)據(jù)的一個重要方面:數(shù)據(jù)可用性［J］,計算機研究與發(fā)展,2013(6):7-11.

［7］余祖坤,許景楠,鄭小林,陳德人,基于信任的真實數(shù)據(jù)判定方法［J］.2013(9):11-18.

［8］CVitolo，YElkhatib，DReusser，CJAMacleod，W Buytaert,Web technologies for environmental Big Data［J］,Environmental Modelling&Software,2015(63): 185-198.

［9］A.BroderandMitzenmacher,Usingmul tipleHash Functions to Improve IP Lookups［C］,Proc.IEEE INFOCOM,2001:1454-1463

［10］F.Baboescu and Varghese,Scalable Packet Classification［J］,IEEE/ACM Trans.Networking,2006,13(1): 2-14.

［11］X Jin，BW Wah，X Cheng，Y Wang,Significance and Challenges of Big Data Research［J］,Big Data Research,2015,2(2):59-64.

［12］A.KirschandMitzenmacher,Distance-Sensitive Bloom filters［C］,Proc.Eighth Workshop Algorithm Eng and Experiments(ALENEX),2006.

［13］MMNajafabadi，F(xiàn)Villanustre，TMKhoshgoftaar，N Seliya，RWald，Deeplearningapplicationsandchallenges in big data analytics［J］,Journal of Big Data》, 2015,2(1):1-21

［14］ATVu，F(xiàn)MGDe，JGama，ABifet,Distributed AdaptiveModelRulesforminingbigdatastreams［C］,IEEEInternationalConferenceonBigData, 2015:345-353

［15］Zhijian Chen;Dan Wu;Wenyan Xie;Jiazhi Zeng; Jian He;di Wu,A Bloom Filter-Based Approach for EfficientMapreduceQueryProcessingonOrdered Datasets［C］,Advanced cloud and Big Data,2013 International Conference on,2013:93-98.

［16］Mayank Bhushan&Sumit Yadav,Cost based Model for Big Data Processing with Hadoop Architecture［M］, 2014.

［責任編輯：王曉軍］

A Local Sensitive Information Filtering based on Big Data Inquiry Algorithm

GUOLing

（ZhuHai City PolytechZhuhaiGuangdong519090，China）

Information filter affects the accessing efficiency in the areas of data fast access and network information fast access.This attracts attentions from the researchers.Via information filtering,it becomes possible to finish information searching within a relatively short time period and provides statistic analyses.Moreover, information filter reduces the cost of information fast access.By applying this advance,the big data inquiry efficiency will be greatly increased if information filtering technique is utilized.A Local Sensitive Information Filtering based Big Data Inquiry is proposed in this paper,based on the features of local information.The proposed algorithm could improve the performance of exacting matching inquiring method and enhance the performance of data fast access and network information fast access.

Big data；Information filtering；Local sensitive information

TP 399

A

1672-402X（2016）11-0047-06

2016-08-10

郭玲（1970-），女，湖南長沙人，珠海城市職業(yè)技術學院講師.研究方向：計算機應用、教育技術.