[發明專利]一種基于多層局部敏感哈希的k最近鄰近似查詢方法

在審

• 申請號: 201910728763.0
• 申請日: 2019-08-08
• 公開（公告）號: CN110489419A
• 公開（公告）日: 2019-11-22
• 發明（設計）人: 張巖峰
• 申請（專利權）人: 東北大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/2458
• 代理公司: 21200 大連理工大學專利中心
• 代理人: 戴風友;梅洪玉<國際申請>=<國際公布>

1.一種基于多層局部敏感哈希的k最近鄰近似查詢方法，其特征在于，步驟如下：

步驟一：采用傳統方法構建LSH索引結構；

采用l組局部敏感哈希函數構建l個哈希表，其中每組包含m個哈希函數，即哈希表中哈希桶的標簽長度為m；此為第0層哈希表；

步驟二：根據用戶期望的召回率α和精確率β確定過載桶和欠載桶；

根據用戶期望的召回率α和精確率β可知哈希桶大小S的上限和下限如公式(5)所示：

當桶的大小低于時，將該桶確定為欠載桶，而當桶的大小超過k/(β·l)時，將該桶確定為過載桶；

步驟三：對過載桶進一步用新的LSH參數進行遞歸的哈希劃分；

將過載桶的數據點根據多個哈希函數映射到多個哈希表中，而不是在一個哈希表中重新劃分；

設一個某過載桶的大小為S，為了保證用戶設定的精確率β，那么重新LSH哈希的子桶哈希簽名長度m_c和哈希表個數l_c計算方法如公式(6)：

公式(6)中的p＝p(r^*,w)的計算方法如公式(2)，r*是查詢點的kNN的距離，β是用戶設定的精確率，是所有子哈希表中最大的子桶；

概率p(s,w)的計算方法如公式(2)所示：

其中f₂(x)是高斯分布的概率密度函數，且norm(·)表示高斯分布的密度累積函數；

然后在kNN查詢時，落入過載桶的查詢點也會被多次哈希到多個子桶中，被映射到這些子桶中的所有數據點也將被作為候選kNN返回；當新建哈希表中仍有大桶，則會繼續對過載桶進行LSH劃分得到第2層哈希表；該過程遞歸進行，直到整個哈希索引中不存在過載桶為止；

步驟四：標記欠載桶；

對于欠載桶，進行標記；

步驟五：查詢處理，確定候選集合；

用戶給定查詢點q，定位其對應的在每個哈希表中的哈希桶；

當定位的哈希桶是指向桶，則將查詢點q重新哈希，重哈希的參數與構建該大桶的子表時的參數相同，同時定位q到子表中的各個哈希桶；

當定位的哈希桶是數據桶，則將桶中的數據點加入到候選點集合；

當子表中的哈希桶仍然為指向桶，那么重復該過程直到定位到一個數據桶；

當定位的哈希桶是欠載的數據桶，此時哈希桶中的數據將會全部并入候選集，并同時把臨近桶的數據點也加入候選集；

步驟六：根據候選集確定近似kNN結果；

步驟五得到的結果是近似kNN搜索的候選集，計算候選集中的點與查詢點q之間的距離，挑選出距離q最近的k個點作為最終的近似kNN查詢結果。

2.如權利要求1所述的一種基于多層局部敏感哈希的k最近鄰近似查詢方法，其特征在于，步驟一中，所述的局部敏感哈希函數如公式(1)所示：

其中o是數據集中的一個來d維數據點，a是一個隨機生成的d維向量，其分布滿足標準高斯分布N(0,1)，b是一個范圍在[0,w]之間的實數，w則是LSH中表征分片寬度的實數。

3.如權利要求1或2所述的一種基于多層局部敏感哈希的k最近鄰近似查詢方法，其特征在于，步驟五中，所述的臨近桶的確定方法采用Multi-Probe LSH方法。