[發明專利]一種基于海明距離的近似成員查詢方法

在審

• 申請號: 201810647790.0
• 申請日: 2018-06-22
• 公開（公告）號: CN109034197A
• 公開（公告）日: 2018-12-18
• 發明（設計）人: 錢江波;黃志鵬;陳葉芳;陳華輝
• 申請（專利權）人: 寧波大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 寧波奧圣專利代理事務所(普通合伙) 33226
• 代理人: 程曉明

本發明公開了一種基于海明距離的近似成員查詢方法，特點是使用適用在海明距離度量下的局部敏感哈希函數(LSH)——比特采樣LSH，結合標準布隆過濾器(BF)中的隨機哈希函數，來構建布隆過濾器HLBF，而對于給定的查詢數據Q，通過隨機翻轉Q上s個比特生成c個虛擬數據，對于每一個虛擬數據生成L個位串，若一個位串在布隆過濾器HLBF中的b個地址的比特位都為1，則稱該位串通過，若c個虛擬數據，每個虛擬數據有L個位串，即c*L個位串中任意一個通過，則判定查詢數據Q是集合Ω的近似成員，優點在于能夠在海明空間下完成近似成員的查詢，同時通過創建虛擬對象，在不重建布隆過濾器的條件下，可以支持不同粒度的查詢。

技術領域

本發明涉及一種近似成員查詢方法，尤其是涉及一種基于海明距離的近似成員查詢方法。

背景技術

現實生活中存在大量集合成員查詢問題，即判斷一個查詢對象是否是一個數據集的成員。例如，安全官員想要檢查某未知的物質(具有某些可檢測的高維特征)是否屬于清單所列的危險化學品；網絡管理員想要知道某用戶的行為特征是否有害；攝影比賽裁判想檢查提交的照片是從與某一張大型數據庫中的照片類似，以上的問題可以統稱為近似成員查詢。這些查詢都需要判斷查詢數據與集合中數據的距離。查詢數據與目標數據的距離越近，數據的價值就越高。如果是低維的小數據集，可通過線性查找解決，但是對一個海量的高維數據集采用線性查找匹配的話，會非常耗時，很多情況下無法滿足實時的需要。為提高處理的速度，可以設置一個高維數據過濾器代表目標數據集合，根據距離過濾掉大部分查詢數據，少量剩下的數據可以再通過常規方法進一步處理，可顯著提高系統的整體性能。

對于近似成員查詢問題的學術研究還剛剛起步，目前對于該問題的主要研究的方向是基于局部敏感哈希函數構建的布隆過濾器。布隆過濾器支持快速集合成員查詢，是一種高效率的數據結構。一般處理近似成員查詢問題(AMQ)使用布隆過濾器和局部敏感哈希結合的技術，包括DSBF(Distance-Sensitive Bloom Filters)[1]、LSBF(Locality-Sensitive Bloom Filter)[2]以及MLBF(Multi-granularity Locality-sensitive BloomFilter)[3]等。它們分別從理論上、適用度量上以及實際需求的變化上補充和完善了局部敏感哈希函數構建的布隆過濾器這一嶄新的近似數據過濾技術。

但是以上技術沒有考慮在海明空間下的近似成員查詢問題。海明距離指二進制編碼對應比特取值不同的總數。在我們生活工作中，海明距離是一個非常重要的距離度量，被廣泛應用在深度學習、圖像文檔比較、基因分析等領域。

此外，在許多現實場景下，在建立布隆過濾器結構之前近似距離參數是不容易給出的，而且對于過濾粒度的需求在實際中經常是變換的。就好比雖然一個查詢點在某個距離參數下，它是遠離數據集的，然而，其他應用程序需求參數下，則可能成為數據集的近似成員。不幸的是，一旦布隆過濾器結構構建好之后，它的過濾距離就已經確定下來了，無法再改變。

上述提到的文獻如下：

[1]A.Kirsch and M.Mitzenmacher,“Distance-Sensitive Bloom Filters,”InALENEX,pp.41-50,2006.

[2]Y.Hua and B.Xiao,“Locality-Sensitive Bloom Filter for ApproximateMembership Query,”IEEE Trans.on Computers,vol.61,no.1,pp.817-830,June2012.

[3]J.Qian,Q.Zhu and H.Chen,“Multi-granularity Locality-sensitiveBloom Filter,”IEEE Trans.on Computers,vol.64,no.12,pp.3500-3514,2015.

發明內容