多維數據近似檢索的分層LSH索引算法模型研究

房華蓉

摘要：該文鑒于數據管理技術發展的前瞻性考慮，以多維數據為處理對象，探索高性能數據過濾器的若干理論和實現技術，針對假陽性和假陰性過高的問題，以及對時空效率的要求，設計了適合多維數據近似檢索的分層LSH索引算法模型。

關鍵詞：多維數據；布魯姆過濾器；局部敏感哈希；分層局部敏感哈希索引

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2018）02-0213-03

隨著互聯網、電子商務等信息技術的高速發展，數據規模呈海量增長，多個領域已經或正在積累TB、PB甚至EB級的大數據[1，2]。如沃爾瑪超市數據庫超過2.5PB，每小時需要處理100余萬條用戶請求；社交網絡Facebook存儲了超過500億張的照片；互聯網數據資源每兩年翻一番；全球的工業設備、汽車、電表上有無數的傳感器，隨時產生多種多樣的海量數據信息。這些都標志著大數據時代已經來到，學術界、工業界和政府都已經開始密切關注大數據及其檢索問題。

2012年美國奧巴馬政府發布了“Big Data Research and DevelopmentInitiative”[3]，投資2億以上美元，計劃在科學研究、環境、生物醫學等領域利用大數據技術進行突破性研究，將“大數據戰略”上升為國家戰略。我國政府多部規劃和項目指南都對“大數據”相關技術密切關注：《國家中長期科技發展規劃綱要（2006-2020年）》提出“重點研究……海量信息處理及知識挖掘的理論與方法”；2014國家自然科學基金優先資助重點領域包括“大數據技術和應用中的挑戰性科學問題”，并列出10個研究方向。

1 多維數據及其檢索策略

信息存儲空間的多元化給網絡中數據資源的存儲管理及新資源開發帶來了新的挑戰。大數據的存儲與表示，大數據中知識快速且高效的挖掘是目前各互聯網服務供應商關注的熱點，普通網絡用戶也希望通過大數據獲得更多的增值服務。數據量及數據復雜度急劇增長時，知識發現的難度及大大增加，計算量和響應時間也隨之變化。研究與之對應的高效查詢算法查找定位信息資源已經成為現代網絡發展分布式信息共享中最常見的問題。精簡結構的查詢算法已經成為提升網絡軟件體系結構和完成大規模高效數據管理的關鍵。

由于大數據的數據體量巨大、類型繁多、價值大但有效信息比例低、要求處理速度快的特點，對當代信息傳輸、計算、存儲以及面向各種應用的數據處理技術提出了前所未有的挑戰。針對這些特征，學術界公認的大數據處理策略是先用過濾器快速過濾掉大部分無用的數據，留下可能有用的數據做進一步處理。但是，如何從靜態或動態的海量數據中“提純”出有價值的數據面臨諸多困難，如：1）大數據時代的算法由于實時性的特點，其準確率不再是最主要指標，很多算法需要在實時性和準確率之間取得平衡；2）數據過濾必須更加謹慎，如果粒度過細，很容易將有用的信息過濾掉；如果過粗，又無法達到真正的清洗效果，因此需要在質和量之間仔細考慮和權衡。

大數據檢索的實際應用中多采用近似查詢，一般而言與目標距離越近，數據的價值就越高。為提高速度，可以設置一個多維數據過濾器，根據距離過濾掉大部分查詢數據，少量剩下的數據可以再通過常規方法進一步處理，可以顯著提高系統的整體性能。這個過濾器完成的就是近似成員查詢（ApproximateMembership Query，AMQ），即回答“查詢對象q是否接近于數據集合中的某個對象”。現有AMQ技術主要是結合局部敏感哈希（Locality Sensitive Hashing，LSH）和布魯姆過濾器（Bloom Filter，BF）設計的，如DSBF和LSBF。不過布魯姆過濾器存在假陽性錯誤，局部敏感哈希算法需要大量的哈希表來建立索引結構，這就導致了大量的內存消耗，查詢時也會帶來大量的I/O訪問。此外，盡管LSH的查詢時間效率已經比較高了，但是依然存在進一步優化的空間。典型DSBF和LSBF這兩個技術都有一個限制，即它們僅能過濾給定距離的AMQ查詢。因此研究BF和LSH算法的特性，針對BF及LSH的缺點提出改進方案或者提出性能更優的相似性檢索算法具有重要的研究意義。為了提出性能及適應性更好的相似性檢索算法，以優化LSH結構、提升AMQ的質量和效率：設計多維數據近似檢索的分層LSH索引算法模型。

2 基于BF及LSH的不同維度數據檢索技術

布魯姆過濾器（Bloom Filter，BF）是由B.H.Bloom在1970提出的經典過濾器[4]，被廣泛用在網絡服務、數據包內容檢測、信息檢索、分布式數據庫、協作緩存等領域。它對集合采用一個位串表示并能有效支持元素的哈希查找，對每個元素的表示只需要幾個比特，是一種能夠表示集合、支持集合查詢的簡潔數據結構，能夠有效地過濾掉不屬于集合的元素。布魯姆過濾器結構的實質是將集合中的元素通過n個哈希函數映射到位串向量中，與傳統的哈希查詢算法中哈希存儲表不同，布魯姆過濾器中哈希表退化為一個位串，一個元素僅占用幾個比特位。進行元素查詢時，計算n個哈希函數，判斷這個位串向量的n個對應比特位是否都為1。不過，布魯姆過濾器作為一種集合查詢的數據結構，在達到其高效簡潔表示集合的同時，卻存在可控的假陽性誤判。

LSH技術是由P.Indyk等在1998年提出，它的思想是：先對數據集中的點進行哈希函數的映射，這樣近距離點的沖突概率提高而遠距離點的沖突概率降低。在查詢時，將查詢點按照相同的哈希函數哈希到桶中，然后取出桶中的所有點作為候選近似最近鄰點，最后計算查詢點與每個候選近似最近鄰點的距離，通過該距離判斷是否符合查詢條件。使用哈希函數對整個數據集進行過濾，得到可能滿足查詢條件的點再計算距離，就避免點與數據集中所有點進行距離計算，提高了查詢效率且無需降維。

2.1 單維數據布魯姆過濾器

針對不同應用，布魯姆過濾器有很多改進。計數布魯姆過濾器CBF[5]將1位的比特擴展為3位或4位的計數器，能夠處理元素刪除操作。CBF可以正確地刪除已經在集合中的元素，但如果這一先決條件不滿足，就會產生假陰性（false negative）問題。為解決此問題，Guo等人[6]提出了一種新方案，在不減少0比特的情況下增加1比特，使得假陰性和假陽性一樣減少。Time Decaying BF[7]在遞減計數器值的同時也考慮時間因素。SBF[8]是另一個重復元素檢測的解決方案，在SBF中0的預期分位數保持恒定，使得它適合在數據流中的重復檢測，它還降低了假陽性和假陰性率。Space-code BF[9]關注測量精度、計算及存儲復雜性之間的權衡。與標準的BF需要k次訪問內存不同，Qiao等[10]提出Bloom-1只需要訪問一次內存，他們還分析了不同的數據結構和性能，以獲得查詢代價和假陽性率都可接受的折中方案。endprint

2.2 低維數據布魯姆過濾器

以上這些研究針對的是單維數據，而實際應用中，很多數據都是多維的。但目前多維布魯姆過濾器研究還比較少，且主要集中在數據的集合判斷問題。Guo等[11]提出了多維動態布魯姆的過濾器（MDDBF）來判斷多維數據是否屬于一個集合，基本的想法是對于s維的集合，設置s個標準BF 過濾器。由于MDDBF方法失去了屬性間的關聯信息，將增加誤報的概率。Xiao等[12]意識到這個問題，提出輔助結構捕捉所有屬性的內在相關性。與MDDBF相比，能夠處理多個屬性，可以提供更快的查詢服務，出現假陽性的概率要低得多，也節省了存儲空間。聯合多維布魯姆過濾器（CMDBF）[13]新增一個用于表示數據整體的聯合布魯姆過濾器CBF，CMDBF中數據表示和查找分兩步進行，即將MDBF的各屬性的表示和查詢作為第一步，第二步聯合數據所有屬性域，利用CBF完成數據整體的表示和查詢確認。

以上這些多維布魯姆過濾器的更新離不開原始數據，即將原始數據的各個維通過哈希運算后才能更新多維過濾器。但在實際應用中，為節省空間，一般只保留概要數據（即布魯姆過濾器），于是無法根據某一屬性刪除的原始數據來更新過濾器。

2.3 多維數據的近似查詢-LSH和BF的優化組合

傳統算法中基于空間劃分的樹形檢索算法，如各類樹型算法，在檢索對象低維度、低數據量的前提下，加速效果明顯。隨著數據維度的增加和數據量的加大，這些算法的加速效果明顯降低。所以，面對高維度的海量數據，這些樹形檢索算法速度上的改進微乎其微，甚至還比不上暴力檢索或者線性檢索的速度。

目標函數中近鄰關系確定是解決最近鄰檢索的速度瓶頸問題，有人提出近似的思想，把如果目標函數中的近近鄰關系定為似最近鄰，如此更改的原因是在多數情況下，近似最近鄰的結果和最近鄰是一致的，而且在大多數的應用場合下，近似最近鄰同樣也可以滿足實際的需求。近似最近鄰的概念最早是由Indyk和Motwani提出的[14]，近似最近鄰的檢索時間及數據容量成亞線性關系得到證明，他們舍棄釆用以往的基于空間劃分的方法，比如樹形分割法，提出了一種新的基于哈希索引的思想實現近似最近鄰檢索，即局域敏感哈希（LSH）。此算法的核心思想是設計幾個哈希函數來映射數據點，每個哈希函數要能保證距離近的點被映射到同一個桶的概率（又叫碰撞概率）比距離遠的點被映射到同一個桶的概率大得多；查詢時，使用對應的哈希函數可以把詢問點也映射到對應的桶中，檢索到的桶中的點即為近鄰點。基于這種映射思想，他們在漢明空間（{0，l}d）中提出了一種局域敏感哈希函數，跟以往的樹形結構算法相比，他們用實驗驗證了這種算法的快速性。2004年，斯坦福大學的Indy等提出了基于P穩態分布的局域敏感哈希，成功地用在了原始的非漢明空間，即P范數空間。

LSH是一種近似的近鄰檢索算法，最近鄰數據點的檢索概率很高，但也不是絕對準確，有人通過使用多個哈希函數構建多個哈希表來提高檢索的準確率，這樣做的問題是存儲空間浪費太大。為了解決這個問題， multi-probe LSH[15]連續探測多個可能包含查詢對象的桶，而不是只探測一個桶，以提高空間和時間效率。Collision Counting LSH（C2LSH）[16]采用了多個LSH函數構造動態復合哈希函數，并設定碰撞閾值來提高精確度。BayesLSH[17]能迅速剪枝大多數的假陽性候選對象，顯著提高處理的速度。

這些查詢都具有多維、實時、且多數查詢都不命中等三個特征。為提高速度，可以設置一個多維數據過濾器，根據距離過濾掉大部分查詢數據，少量剩下的數據可以再通過常規方法進一步處理，可以顯著提高系統的整體性能。這個過濾器完成的就是近似成員查詢AMQ，即回答“查詢對象q是否接近于數據集合中的某個對象”。現有AMQ過濾器主要是結合LSH和Bloom filter 設計的，如DSBF和LSBF。如今，LSH技術及其變種是高維空間檢索最先進的索引技術之一。

DSBF首次綜合LSH和BF來過濾AMQ查詢，返回組成員的近似查詢結果。它可以改善網絡和數據庫應用的速度和空間，從而避免很多代價昂貴的比較操作，如最近鄰查詢等。LSBF使用LSH 函數來構造BF過濾AMQ查詢，LSBF還采用了額外的位向量來降低假陽性率。DSBF和LSBF這兩個技術都有一個限制，即他們僅能過濾給定距離的AMQ 查詢。然而，給定一個合適的距離并不容易，過大或過小的距離值，可能會導致不可接受的查詢結果。一旦距離值被確定，就不能改變，除非根據原始數據重新構造過濾器。然而，為節省空間，原始數據一般并不保存。另外，這兩種過濾器也占用較多的空間開銷，錯誤率相對較大。

2.4 已有技術的不足

從上面分析可知：（1）單維數據過濾器的研究和應用相對比較充分；（2）低維數據過濾器的研究局限在判斷數據是否在集合中，在沒有原始數據支持下，無法根據某一屬性刪除數據的布魯姆過濾器更新其余維度的過濾器（項目組成員在這個問題方面已經實現了2維數據的關聯刪除技術的研究，并已投稿國際頂級會議被錄用）；（3）多維數據過濾器的過濾距離固定，無法支持多粒度的過濾距離；（4）多維數據的近似查詢中LSH索引表建立時，耗費過多內存資源；查詢時，頻繁進行I/O操作，耗費過多的計算時間。

3 分層LSH索引算法模型

3.1 分層LSH算法流程

針對已有的結合BF和LSH在近似近鄰檢索算法，由于內存消耗過大和時空效率不高（頻繁進行I/O處理）問題，提出了分層LSH索引算法流程如下：

1） 索引建立：首先對原始多維數據利用已有基于p穩定分布的哈希函數族G（多維哈希）進行局部敏感哈希到多個哈希表中，對每個數據在多哈希表散列的桶號進行編碼，形成桶編號；然后對桶編號進行一維哈希散列到一維向量（BF）中，相鄰數據點有著相近的桶編號，那么相近的桶編號散列到一維向量中也是相近位；再對一維向量中存放的桶編號散列的位進行地址合并，完成索引建立。endprint

2） 查詢處理：查詢時，首先對查詢點做多維哈希函數族的局部敏感哈希到多個桶，將這些桶中的數據作為其候選近鄰數據點（這樣可以避免假陽性偏高問題，如果相應桶中數據個數已達查詢結果要求，則結束）；如果沒有查找到足夠的候選近鄰則繼續對桶編號散列到BF中位的近鄰進行查詢（這樣可以避免假陰性偏高問題），直至查到查詢目標。

3.2 分層LSH索引算法模型設計

結合傳統LSH在近似近鄰檢索算法中，由于內存消耗過大、時空效率不高和假陽性、假陰性過多問題，我們提出了分層LSH索引算法流程，如圖1所示。

分層LSH索引構建流程：對多維的原始數據進行多哈希函數的局部敏感哈希，先建立一個哈希表，每個哈希表對應哈希函數族G中隨機選出[l]個g函數[g1，g2，...，gl]中的一個g函數，這個方法能大大提高近鄰點的碰撞概率。而每個數據點散列到[l]個哈希表的不同桶中，對這些桶號進行編碼形成查詢數據的哈希桶編號，然后對這些哈希桶編號再進行一次一維哈希函數的散列，將散列地址映射到BF的有關位中。設計過程中，考慮到多維數據的近似性，近似數據的桶編號經過一維哈希函數的散列后的地址在BF中具有高概率的相鄰性，因此可以考慮對BF的這些相鄰位進行合并，完成索引的優化。

分層LSH中數據的查找流程：查找數據時首先對查詢點進行哈希函數族的局部敏感哈希，將其映射到各哈希表的不同桶中形成其散列桶的桶編號，然后將這個桶編號對應的桶中數據作為候選近似查詢目標，如果目標的數目達到了預期的查詢數，就鎖定這些數據作為候選查詢點；如果沒有達到，那么在查詢點所對應的哈希桶編號再散列的BF位的相鄰位所對的哈希桶編號的數據點也作為候選近鄰成員。

4 小結

本文針對已有的結合BF和LSH在近似近鄰檢索算法進行了總結，基于已有技術的內存消耗過大和時空效率不高（頻繁進行I/O處理）問題，提出了分層LSH索引算法設計分層LSH索引算法模型，既能避免假陽性和假陰性過高的問題，也能提升算法的時空效率。

參考文獻：

[1] 王珊，王會舉，覃雄派，等. 架構大數據：挑戰、現狀與展望[J]. 計算機學報，2011， 34（10）：1741-1752.

[2] 李建中，劉顯敏. 大數據的一個重要方面：數據可用性[J]. 計算機研究與發展，2013， 50（06）：1147-1162.

[3] 孟小峰，慈祥. 大數據管理：概念、技術與挑戰[J]. 計算機研究與發展，2013，50（01）：146-169.

[4] B.H.Bloom. Space/Time Trade-Offs in Hash Coding with Allowable Errors. Comm. ACM， 1970， 13（7）：422-426.

[5] L.Fan， P. Cao， J. Almeida， and A. Z. Broder. Summary Cache： A Scalable Wide-Area Web Cache Sharing Protocol.IEEE/ACM Trans. Networking.2000，8（3）：281-293.

[6] D.Guo， Y. Liu， X. Li， P. Yang.False Negative Problem of Counting Bloom Filter. IEEE Trans.Knowl.Data Eng.2010， 22（5）：651-664.

[7] K.Cheng，L.Xiang， M.Iwaihara， H.Xu， and M.M.Mohania. Timedecaying Bloom filters for Data Streams with Skewed Distributions. in Proc. 15th International Workshop on Research Issues in Data Engineering： Stream Data Mining and Applications. Washington， DC， USA： IEEE Computer Society，2005： 63-69.

[8] F.Deng and D. Rafiei. Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters. in Proc. 2006 ACM SIGMOD International Conference on Management of Data.New York， NY，USA： ACM， 2006： 25-36.

[9] A.Kumar，J.Xu，J.Wang，O.Spatschek， and L.Li.Space-code Bloom Filter for Efficient Per-flow Traffic Measurement. In Proc. IEEE INFOCOM.Hongkong， China， 2004（3）：1762-1773.

[10] Y.Qiao， T.Li， S.Chen.Fast Bloom Filters and Their Generalization.IEEE Transactions on Parallel and Distributed Systems. 2014， 25（1）：93-103.

[11] D.Guo，J. Wu， H.Chen， and X. Luo. Theory and Network Application of Dynamic Bloom Filters.Proc.IEEE INFOCOM， 2006.

[12] B. XIAO， Y HUA. Using Parallel Bloom Filters for Multiattribute Representation on Network Services.IEEE Trans on Parallel and Distributed Systems， 2010， 21（1）：20-32.

[13] 謝鯤， 秦拯， 文吉剛， 等. 聯合多維布魯姆過濾器查詢算法[J]. 通信學報，2008， 29 （1）：56-64.

[14] Indyk Piotr，andMotwani Rajeev， Approximate nearest neighbors： towards removing the curse of dimensionality. In the thirtieth Annual ACM Symposium on Theory of Computing，1998，pp.604-613.

[15] Q.Lv，W.Josephson， and Z. Wang. Multi-Probe LSH： Efficient Indexing for High-Dimensional Similarity Search. In VLDB， pages 950-961， 2007.

[16] J.Gan，J.Feng， and Q. Fang. Locality-sensitive Hashing Scheme Based on Dynamic Collision Counting.In SIGMOD， pages 541-552， 2012.

[17] V.Satuluri， and S. Parthasarathy. Bayesian Locality Sensitive Hashing for Fast Similarity Search. In VLDB， pages 430-441， 2012.endprint