SLSB-forest：高維數據的近似k近鄰查詢

錢途，錢江波，董一鴻，陳華輝

（寧波大學信息科學與工程學院，浙江 寧波 315211）

SLSB-forest：高維數據的近似k近鄰查詢

錢途，錢江波，董一鴻，陳華輝

（寧波大學信息科學與工程學院，浙江 寧波 315211）

近似 k近鄰查詢的研究一直受到廣泛關注，局部敏感散列（LSH）是解決此問題的主流方法之一。LSH及目前大部分改進版本都會面臨以下問題：數據散列以后在桶里分布不均勻；無法準確計算對應參數 k的查詢范圍建立索引。基于此，將支持動態數據索引的LSH和B-tree結合，構建新的SLSB-forest索引結構，使散列桶里的數據維持在一個合理的區間。針對SLSB-forest提出了兩種查詢算法：快速查找和準確率優先查找，并通過理論和實驗證明查找過程中查詢范圍的動態變化。

近似k近鄰；局部敏感散列；高維數據

1 引言

最近鄰（nearest neighbor）查詢問題在模式識別、數據挖掘等領域應用非常廣泛，其目標是找出與查詢點距離最近的點。高維空間下的最近鄰問題一直受到廣泛關注，特別是在音頻、圖像等領域。線性查找是處理近鄰查詢最直觀的方法，但是開銷會隨著數據集的增大呈線性增長。傳統基于空間劃分法的樹索引結構，如 R-tree[1]、SR-tree[2]、K-D tree[3]，在低維空間下可以高效地返回準確的近鄰查找結果，但是這些索引的數據維度一旦超過10，就會產生維度災難問題，其查詢效率甚至不如線性查找[4]。

高維空間下的近鄰查詢很難提高效率，為此提出了近似近鄰查詢（c-approximate nearest neighbor search）。近似近鄰查詢返回的不是精確解，而是允許一定誤差范圍內的近似解。局部敏感散列（locality sensitive hash，LSH）[5]是目前高維空間下解決近似近鄰查詢問題最主流的方法。LSH基本思想是通過一系列具有位置敏感性質的散列函數，將高維空間下距離相近的數據點散列到相同的桶中。查詢時，LSH將查詢點散列到目標桶中，將此桶中的數據作為最終結果的候選集。為了提高查找準確率，通常會構建多個LSH索引，將各個索引的候選集合并，用線性搜索的方法查找候選集找出最近鄰。

1998年，Indyk等人[5]第一次提出LSH理論，用以解決海明空間下的近似成員查詢，經過近30年的發展，衍生了許多LSH變體。2004年，Datar等人[6]將 LSH擴展到歐氏空間，提出滿足p-stable分布的散列函數E2LSH，E2LSH在歐氏空間下具有很好的位置敏感性，可以使空間中兩個距離相近的點以較高的概率散列到同一個桶中。E2LSH在實際使用中需要大量的散列表才能達到較高的準確率，因此Lv等人[7]提出multi-probe LSH減小索引數量。multi-probe LSH通過衍生一個探測序列，在查詢時不僅查詢目標桶，同時也會根據探測序列查詢鄰近桶。基于熵（entroy-based）的LSH[8]通過基于熵的概念產生一些與查詢點滿足一定條件的虛擬點，將虛擬點所在桶號的點作為查詢結果的候選集。為了減小LSH查詢時龐大的I/O開銷，SK-LSH[9]定義了一種新的衡量桶之間的距離，使得桶號像自然數一樣有序。為了同時保證查詢質量和查詢效率，LSB-forest[10]將散列后的桶號處理成Z-order編碼，對編碼構建B-tree索引，LSB-forest查詢時會優先尋找具有最長公共前綴長度（LLCP）的桶。MLBF[11]成功地將 LSH[12]和布隆濾波器（Bloom filter）[13]結合，并提出多粒度查詢的概念。

將高維數據散列到低維的桶中，即使數據在原始空間均勻分布，數據散列后也會存在分布不均勻的問題，不同桶里的數據相差比例可高達幾十倍。圖1、圖2分別是均勻數據集和真實數據集（ANN_SIFT1M）散列以后在桶里的分布情況。桶里數據分布不均勻會極大影響查詢效率，因此胡海苗等人[14]提出了一種可擴展的索引SLSH解決桶里數據分布不均勻問題。SLSH主要針對（r,c）-近鄰查詢問題，對于近似最近鄰問題，若查詢近鄰個數為k，無法計算出有效的查詢范圍r。本文將SLSH和B-tree相結合，提出了一種局部有序的SLSB樹索引結構，通過建立多棵樹構建SLSB森林（SLSB-forest）結構。針對近似最近鄰問題給出了兩種查詢算法：適用于 k較小的快速查詢和適用于 k較大的準確率優先查詢，并且通過理論和實驗證明這兩種查詢方法都可以動態地擴大查詢半徑，同時滿足效率和準確率需求。

圖1 均勻數據集分布情況

圖2 ANN_SIFT1M數據集分布情況

2 基礎知識

2.1 LSH

嚴格來說，LSH并不能直接解決近似k近鄰查詢（c-AkNN）問題。LSH最初設計是為了解決（r,c）-近鄰查詢問題。

定義1 （（r,c）-近鄰查詢）D是d維空間下的數據集，B(q,r)是以q為中心、r為半徑的超球形范圍。（r,c）-近鄰查詢問題需要返回以下結果。

· 如果超球空間B(q,r)至少包含D中的任意一點，則返回與查詢點q距離小于cr的一個點。

· 如果B(q,cr)未覆蓋D中的任意一點，則返回空。

定義2 （c-ANN查詢與c-AkNN）D是d維空間下的數據集，對于查詢點 q， o?是數據集 D中距離q最近的點。c-ANN查詢返回的結果o需要滿足，其中c＞ 1。更一般化的 c-AkNN查詢，如果需要查詢的近似近鄰個數k＞1時，近似k近鄰的結果集，需要滿足是查詢點的真實k近鄰。

圖3是3個不同情況的（r,c）-近鄰查詢，如果現在需要支持c-AkNN查詢，設k=10。可以看出，圖3（a）設置的查詢半徑r剛好可以返回合適數量的查詢結果；圖3（b）查詢范圍內的數據只有2個，不能夠返回足夠數量的結果；圖3（c）由于數據分布比較密集，在查詢范圍內的數據遠遠大于10，需要消耗更多額外的時間對候選集進行篩選。在實際的 c-AkNN查詢時，由于數據分布不均勻且查詢近鄰 k不斷變化，很難找到合適的r值。

定義3 （LSH[5]）給定查詢范圍r，比例參數 c( c＞0)，概率值p1、p2(p1＞p2)，o、q代表兩個數據點，dist(?)是歐氏空間的距離度量函數。如果散列函數 h(?)能夠滿足以下條件：

則h(?)函數被認為是距離敏感的。本文采用參考文獻[11]中適用于歐氏距離的局部敏感散列函數：

其中，a的每一維都是服從標準正態分布的，w是桶的寬度，b是區間(0,w)中的隨機數。數據集中的任意兩點o、q之間的距離是歐氏距離下的局部敏感散列函數。o、q通過散列以后發生碰撞的概率計算如下：

圖3 （r,c）-近鄰查詢

為了更有效地解決歐氏空間下的（r,c）-近鄰查詢問題，會通過與（AND）和或（OR）操作增強LSH的查詢準確率。與操作是隨機生成t個LSH函數h1,…,ht，將這t個LSH函數組合構造成一個組合散列函數g(?)，對于任意數據o，其散列值為；或操作是通過構建多個索引，查詢時分別查找各個索引并對結果進行整合，以提高查詢的準確率。

2.2 高維動態數據索引SLSH

SLSH是一種動態可擴展的散列算法，主要針對分布不均勻的數據集設計的散列表結構。單個散列表的散列函數為w是每個 h(?)函數對應的桶寬且滿足構建散列表的過程中并不是同時計算的，先由對數據第一次散列，如果桶里的數據個數大于給定閾值 N，對桶里的數據用下一個更細區分度的散列函數進行散列，依次類推，直到桶里的數據個數小于 N或者計算到第t個為止。

SLSH是用來解決不均勻數據集上（r,c）-近鄰查詢問題，對于c-AkNN查詢問題，SLSH會遇到和傳統LSH相似的問題。如果將查詢半徑r設置為查詢點和最近鄰的距離，SLSH的效率會很高，但是找到相應的查詢半徑十分困難。即使找到對應的r，不同查詢任務的r也會發生變化。

3 SLSB-forest

SLSH通過逐層散列的方法對數據集進行散列，數據分布稀疏的區域用較大的桶切分，數據分布密集的區域用更細的桶進行劃分。若要使SLSH支持多種近鄰查詢，必要的方法是對數據進行較細的劃分，在查詢時如果候選點個數小于k，通過合并相鄰桶里的點直到候選點個數大于k。

定義4（桶距度量）桶號由多個散列函數的散列值組合而成，單個散列表的散列函數為查詢點q的桶號為，定義桶號之間的距離。本文后半部分還需要比較每一層散列函數的桶距，表示為，第i層的桶距

與q桶號距離小于或等于Δ的桶，滿足條件

SLSH無法快速地查找相鄰桶，因為其算法未保存空間位置信息。常見的空間索引如R-tree因插入等操作較為繁瑣，效率也不高，因此提出了將SLSH和B-tree相結合的索引結構，使索引結構局部有序，在查找時可同時在不同層次的索引檢索，可以加速查找相鄰桶。

3.1 SLSB-tree構建

SLSB-tree使用歐氏空間下的E2LSH函數，單個散列表的散列函數為，單個散列桶最多存放N個數據。SLSB-tree是逐層構建的，首先將數據集D中的數據通過 h1(?)進行第一層散列，散列后的第一層桶號是一維的，可以快速地對第一層桶號構建B-tree索引使桶號按順序依次排列。在散列過程中，如果某一桶里的數據個數大于閾值 N，將這個桶標記為超桶，并對超桶里的數據用下一級散列函數即 h2(?)進行第二次散列。超桶里數據散列以后的桶號需要構建一個新的次級B-tree索引，超桶存放的不再是數據，而是一個新的小型B-tree索引。如果第二層中仍有數據個數大于N的桶，將這個桶標記為超桶并重復上述處理超桶的步驟直到無超桶出現或散列到第t層為止。SLSB-tree構建完成后除第一層的桶號是全局有序外，其他層只在相應的超桶下是有序的，相同層次不同超桶之間不存在順序關系。SLSB-tree查找查詢點對應的目標桶時，先計算第一層散列值，如果對應的第一層桶是超桶，計算下一層散列值并查找超桶下的索引，直到查詢到非超桶為止。

算法1 創建SLSB-tree

輸入：D (數據集), q (查詢點), t (Hash函數個數), N(單個桶最大存儲數據個數)

單個SLSB-tree會伴隨很高的假陰性，假陰性指相近的數據沒有落入同一個桶中，所以通過構造多個SLSB-tree形成SLSB-forest，查詢時同時在所有樹上進行查詢并對候選集合并，可以顯著地提高準確率。

SLSB-forest結構如圖4所示，tree 1和tree L是兩棵已經建好的SLSB-tree，第一層為 h1(?)散列后的桶號按順序相鄰。tree 1和tree L中超桶分別是5、9和6、7，用深色桶標記，超桶下對應的是一個新的B-tree索引。以tree 1為例進行查詢目標桶{5,7}，在第一層時找到桶{5}時遇到超桶，需要在{5}對應的索引下尋找第二層索引桶{7}。

SLSB-tree的關鍵是快速尋找相鄰桶，如果桶號是一維的，即散列函數，可以由查詢點向外側依次查找相鄰桶，但是沒有與操作的LSH假陽性會很高。SLSB-tree除第一層之外的其他桶只是局部有序，每次尋找最近桶會在查找過程中消耗一些額外時間，考慮到近似近鄰查找只需滿足一定的近似比例，所以提出了兩種查詢方法：快速查找和準確率優先查找。

3.2 快速查找

快速查找的思想是每次向兩側尋找的桶不必是最近桶，只需要桶距小于給定的閾值。SLSB-tree每一層的桶號都是局部有序，即在同一個超桶下的所有桶是順序排列。快速查找算法如下：查詢桶號為，位于第i層索引。查詢時如果需要查找鄰近桶，只需從q桶號向左右兩側順序選擇距離最近的桶查詢，向兩側查找有3個終止條件：①候選點個數大于k；②同一超桶下的桶都已查詢；③當前索引中沒有滿足的桶，Δi是當前索引層允許向兩側尋找的最大距離，每一層對應一個Δi，計算方式在第4節給出。遇到終止條件①，直接跳出查詢；遇到終止條件②和③，需要返回第（i-1）層索引，從向外側查找最近桶。如果在第（i-1）層遇到其他超桶，需要在超桶對應的下一層索引中查找，查找相鄰桶的方法和上述一致。

圖4 SLSB-forest結構

3.3 準確率優先查找

快速查找是不斷地向兩側查找滿足一定條件的桶，如果向外查詢每次都能查詢最近的桶，準確率會更高。準確率優先查找算法如下。

遍歷候選桶隊列時，按順序計算候選桶與查詢桶的距離是否等于1，若不等于，跳過；若等于，需要分兩種情況。如果該桶是非超桶，則加入結果集并在隊列中將其刪除，并加入未遍歷的相鄰桶至候選隊列中；如果是超桶，超桶對應的索引按照 SLSB-tree查詢Δ=0的方法查詢，刪除此桶并加入未遍歷的相鄰桶。當候選隊列遍歷結束，仍需查找更多相鄰桶，從頭開始再次遍歷候選隊列查找桶距為Δ+1的桶。

以圖4 tree L為例，圖5展示了準確率優先查詢的過程。查詢點q的桶號{6,6}，查詢Δ=0時經過桶{6}、{6,6}，將候選桶{5}、{7}和{6,5}、{6, 7}加入候選桶隊列中。當需要查找Δ=1的相鄰桶時，僅需計算隊列中的桶號和查詢桶號的距離，滿足Δ=1的桶為{5}、{7}、{6,5}、{6, 7}，將其中的非超桶直接加入結果集中，并將它們未查詢過的相鄰桶{4}、{8 }、{6, 3}加入候選隊列。對于超桶{7}，在其對應的索引中查找與查詢桶在第二層索引相同的桶號即{7,6}加入結果集，查詢路徑過程中的鄰近且未查詢過的桶{7,8 }加入候選隊列中。若繼續查詢Δ=2，隊列中只有{4}、{8}兩個桶滿足，重復Δ=1時的查詢操作直到找到足夠的近鄰。

圖5 準確率優先查詢的過程

4 理論證明

本節將對SLSB-forest進行理論分析，主要針對以下兩個問題：兩種查找方法在查詢過程中查詢范圍的變化和快速查找過程中每一層Δi的計算。

本文采用的是歐氏空間下的局部敏感散列，設桶寬為w，查詢半徑為r，近似比例為c。根據式（1）可以得出碰撞概率的計算式為：

其中，norm()是標準正態分布的累積分布函數，可以分別求出散列函數為，則在單個散列表中距離r的碰撞概率為。

4.1 準確率優先查詢范圍變化

準確率優先查詢的原理是增大桶寬擴大查詢范圍，在尋找桶距為0、1、2…時，對應的桶寬為w、3w、5w…，若桶距為Δ，對應的散列函數桶寬為（ 2Δ+1)w。此處的桶寬（ 2Δ+1)w和直接設置散列函數的桶寬有明顯區別，因為目標桶一直在寬為（ 2Δ+1)w桶的中央，碰撞概率的計算方式會有所改變。其計算方式如下：

查找相鄰桶的概率計算如圖6所示，通過隨機生成距離為[1,180]的點，每一個整數距離生成1 000對數據，設置桶寬w=50，通過實驗來模擬解碰撞概率。圖6中平滑的曲線表示通過計算式計算的概率，波動的曲線表示實驗計算的概率。從圖6可以看出，實驗計算的不同Δ的碰撞概率和通過公式計算的概率吻合，由此驗證了理論推導的正確性。

圖6 查找相鄰桶的概率計算

準確率優先查詢范圍變化如圖7所示，設近似比例 c=2，根據式（5）計算不同距離r在 Δ= 1、 2、 3時查詢范圍的變化情況。由于向兩側查找會使距離較近的桶碰撞概率顯著升高，但是隨著r的增大，范圍擴大比例逐漸趨于平緩，并且α= β≈2Δ+ 1。

圖7 準確率優先查詢范圍變化

4.2 快速查詢范圍變化

快速查詢的本質是通過減小g(?)中散列函數的個數t達到擴大查詢范圍的目的。查詢桶在第i層查詢，若需要返回上一層（i-1）層查詢時，在第i層查詢的桶可以合并為一個大桶。若g(?)散列函數個數由t變為，假設查詢范圍擴大為α，需滿足通過求解方程：

可以求出t發生變化后對應的查詢范圍。圖8是不同距離下快速查詢范圍的變化情況，原始查詢t=6，近似比例c=2，從圖8可以看出，α、 β隨著查詢范圍 r的增大在一開始會有一小段下降，隨后一直上升，當 t=4時更加明顯，且β的上升速度明顯要高于α。

圖8 快速查詢范圍變化

4.3 范圍變化對效率的影響

查詢范圍(r, c)的變化會直接影響查詢效率。設通過查詢相鄰桶查詢范圍擴大為(αr ,βc)，最理想的情況是α= β=1，但是此過程必定會使查詢范圍變大，所以希望α、 β盡可能小。不考慮r特別小的極端情況，快速查詢和準確率優先查詢相比，查詢同樣多的相鄰桶，α快速＜α準確，但是，尤其當r較大時，β快速將遠遠大于α快速。

α較小可以使查詢質量更高，但是若β遠大于α，會使假陽性增大，所以快速查詢在查詢近鄰個數較少或數據較密集時準確率較高，因為其對應的查詢范圍 r較小。當數據稀疏或者查詢近鄰個數較大時，適合使用準確率優先查詢，因為當r越大時，α、 β不會隨著r發生明顯變化。

4.4 快速查找{Δ1,…, Δ2}的計算

設置每一層Δi的意義在于在當前子索引中繼續向外側尋找相鄰桶不會使準確率發生明顯變化，停止當前索引查找，返回上一層索引查詢相鄰桶。根據式（4）可以求出查詢到第i層索引對應的查詢范圍(αir ,βic)。在第i層查詢桶號滿足到查詢桶號滿足的桶，距離為αir 的點碰撞概率變化為：

圖9 快速查詢碰撞概率變化

5 實驗分析

本文實驗環境的CPU為Intel Core i7-6500U、8 GB DDR3內存，分別在3個真實數據集上進行測試，利用Java實現了SLSB-forest算法，并和傳統LSH、LSB-forest、C2LSH進行對比。

5.1 實驗數據集

Mnist[10]：包含60 000個手寫數字圖像的訓練集，每一圖像由28 dpi×28 dpi個像素點構成，相當于一個784維的高維數據。Mnist還包含一個大小為10 000的測試集，從中抽取1 000個作為查詢對象。

Color[10]：包含68 040個32維的數據，其中每一個點都來自 Color數據集中的圖片顏色直方圖。從數據集中隨機抽取1 000個點作為查詢集，并從Color中刪除，查詢集大小為1 000，數據集大小為67 040。

ANN_SIFT1M[12]：包含 100萬條 128維的SIFT特征集以及大小為1萬條的查詢特征集。

5.2 性能評估

通過對比算法的查詢結果質量和查詢時間開銷來評估SLSB-forest的好壞。

準確率（Ratio）：評估近似近鄰查詢結果的準確性。查詢點q的k近鄰真實結果為…，近似近鄰查詢結果為 o1,…,ok。對于任意i∈[1,k]，定義rank- i近似比例為rank-i是衡量第i個查詢結果的近似比例，對于整個結果的近似比例計算方式為Ratio=，Ratio越接近1代表查詢結果越接近準確結果。

平均查詢時間（ART）：查詢時間主要分為桶查詢和候選集篩選兩部分。桶查詢包括目標桶查找和相鄰桶查找，若查詢的近鄰數量 k較小，桶查詢對平均查詢時間的影響較大；若 k較大，候選集篩選占平均查詢時間的比重很大。

5.3 實驗比較

通過查詢近鄰個數k的變化來對比5種查詢方法的性能。k的增加意味著查詢范圍需不斷擴大，實現傳統LSH算法時，通過實驗尋找較合適的參數以適應多種k查詢。圖10和圖11分別是Mnist和 Color數據集上的準確率比較，由圖 10和圖11可以看出，SLSB-forest的準確率相對于其他 3種算法都有很大的提升。Color數據集上，C2LSH在k比較小時準確率較高，接近SLSB快速查詢的效率，但是隨著k的增大，SLSB的兩種查詢算法準確率呈下降趨勢，C2LSH呈上升趨勢且一直高于SLSB算法。快速查找的準確率在k較小時，比準確率優先查找要低。隨著k的增大，準確率優先查詢的結果相比快速查詢更接近真實結果。

圖12和圖13是查詢時間的比較，可以看出4種查詢方法中最快的還是直接用LSH。本文實驗中使用的 LSH是經過多次調試尋找的較高效的參數，所以查詢速度較高。LSB-forest在 Color數據集上的查詢速度較快，但是LSB-forest要達到較高的準確率一般需要建立20棵以上的樹，所以在相同準確率的前提下SLSB-forest更具有優勢。C2LSH在兩個數據集上的查詢速度均快于SLSB，但是和SLSB的快速查找算法相比優勢并不明顯。快速查詢相比準確率優先查詢速度更快，尤其在 Color數據集中。

圖10 Mnist數據集上的準確率比較

圖11 Color數據集上的準確率比較

圖12 Mnist數據集上的查詢時間比較

圖13 Color數據集上的查詢時間比較

快速查詢和準確率優先因為其動態擴展查詢范圍的方式不一樣，在合并多個索引時候選集的數量也會有明顯區別。圖14是未合并前多個索引候選集的數量和，未合并是指沒有去除重復的候選集。圖15是合并之后的候選集數量，在未合并之前兩種查詢方法的候選集數量幾乎相同，但是合并之后準確率優先的候選集數量有一個明顯的下降，并且隨著k的增大下降得越明顯。其主要原因是快速查詢的β會隨著k的增大而遠遠大于α，假陽性明顯增高，而準確率優先α =β。如果查詢近鄰個數較多時，則優先采用準確率優先查找，因為其可以減少篩選候選集所消耗的時間。

圖14 未合并前多個索引候選集的數量和

6 結束語

針對LSH桶里數據分布不均勻的問題[15]，提出SLSB-forest算法和兩種能夠動態擴大查詢范圍的查詢方法：速度優先和準確率優先。速度優先通過減小與操作的散列函數個數動態擴大查詢范圍，而準確率優先則通過擴大桶寬動態擴大查詢范圍，理論和實驗證明了兩種查詢方法的范圍動態變化，并分析了兩種查詢方法的利弊。速度優先適合近鄰個數 k較小或數據較密集的情況，此時查詢范圍較小；準確率優選適用于數據稀疏或者k較大的情況，此時查詢范圍會較大。

圖15 合并之后的候選集數量

[1] GUTTMAN A. R-trees: a dynamic index structure for spatial searching[J]. ACM SIGMOD Record, 1984, 14(2): 47-57.

[2] KATAYAMA N, SATOH S. The SR-tree: an index structure for high-dimensional nearest neighbor queries[C]//ACM SIGMOD International Conference on Management of Data, May 11-15, 1997, Tucson, Arizona, USA. New York: ACM Press, 1997: 369-380.

[3] 過潔, 徐曉旸, 潘金貴. 虛擬場景的一種快速優化 Kd-Tree構造方法[J]. 電子學報, 2011, 39(8): 1811-1817. GUO J, XU X Y, PAN J G. Build Kd-Tree for virtual scenes in a fast and optimal way[J]. Chinese Journal of Electronics, 2011, 39(8): 1811-1817.

[4] WEBER R, SCHEK H J, BLOTT S. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces[C]//International Conference on Very Large Data Bases, August 24-27, 1998, San Francisco, CA, USA. New York: ACM Press, 1998: 194-205.

[5] INDYK P, MOTWANI R. Approximate nearest neighbors: towards removing the curse of dimensionality[J]. Theory of Computing, 2000, 604-613(11): 604-613.

[6] DATAR M, IMMORLICA N, INDYK P, et al. Locality-sensitive hashing scheme based on p-stable distributions[C]//Twentieth Symposium on Computational Geometry, June 8-11, 2004, Brooklyn, New York, USA. New York: ACM Press, 2004: 253-262.

[7] LV Q, JOSEPHSON W, WANG Z, et al. Multi-probe LSH: efficient indexing for high-dimensional similarity search[C]// International Conference on Very Large Data Bases, September 23-27, 2007, Vienna, Austria. New York: ACM Press, 2007: 950-961.

[8] PANIGRAHY R. Entropy based nearest neighbor search in high dimensions[C]//The Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, November 4, 2005, Miami, Florida, USA. [S.l.:s.n.], 2005: 1186-1195.

[9] LIU Y F, CUI J T, HUANG Z, et al. SK-LSH: an efficient index structure for approximate nearest neighbor search[J]. Proceedings of the VLDB, 2014, 7(9): 745-756.

[10] TAO Y F, YI K, SHENG C, et al. Quality and efficiency in high dimensional nearest neighbor search[C]// ACM Sigmod International Conference on Management of Data, June 29-July 2, 2009, Providence, Rhode Island, USA. New York: ACM Press, 2009: 563-576.

[11] QIAN J, ZHU Q, CHEN H. Multi-granularity locality-sensitive bloom filter[J]. IEEE Transactions on Computers, 2015, 64(12): 3500-3514.

[12] PAULEV L, GOU H, AMSALEG L. Locality sensitive hashing: a comparison of hash function types and querying mechanisms[J]. Pattern Recognition Letters, 2010, 31(11): 1348-1358.

[13] QIAN J, ZHU Q, WANG Y. Bloom filter based associative deletion[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 24(8): 1986-1998.

[14] 胡海苗, 姜帆. 基于可擴展LSH的高維動態數據索引[J]. 軟件學報, 2015, 26(2): 228-238. HU H M, JIANG F. Scalable locality sensitive hashing scheme for dynamic high-dimension data indexing[J]. Journal of Software, 2015, 26(2): 228-238.

[15] 吳軍. 大數據和機器智能對未來社會的影響[J]. 電信科學, 2015, 31(2): 7-16. WU J. Big data, machine intelligence and their impacts to the future world[J]. Telecommunications Science, 2015, 31(2): 7-16.

SLSB-forest: approximate k nearest neighbors searching on high dimensional data

QIAN Tu, QIAN Jiangbo, DONG Yihong, CHEN Huahui
College of Information Science and Engineering, Ningbo University, Ningbo 315211, China

The study of approximate k nearest neighbors query has attracted broad attention. Local sensitive hash is one of the mainstream ways to solve this problem. Local sensitive hash and its varients have noted the following problems: the uneven distribution of hashed data in the buckets, it cannot calculate the appropriate query range (for the parameter k) to build index. To tackle the above problem, a new data struct which called SLSB-forest was presented. The SLSB-forest combined the LSH and the B-tree to maintain the amount of bucket’s data in reasonable range. Two query algorithms were proposed: fast and accurate priority search. Theory and experimental results prove that query range can dynamic change during searching approximate k nearest neighbors.

approximate k nearest neighbor, locality sensitive hash, high dimensionality

TP311

：A

10.11959/j.issn.1000-0801.2017193

錢途（1992-），男，寧波大學信息科學與工程學院碩士生，主要研究方向為大數據、數據挖掘。

錢江波（1974-），男，博士，寧波大學信息科學與工程學院教授，主要研究方向為數據處理與挖掘、邏輯電路設計、多維索引與查詢優化。

董一鴻（1969-），男，博士，寧波大學信息科學與工程學院教授，主要研究方向為大數據、數據挖掘和人工智能。

陳華輝（1964-），男，博士，寧波大學信息科學與工程學院教授，主要研究方向為數據處理與挖掘、云計算。

2017-03-22；

：2017-06-07

國家自然科學基金資助項目（No.61472194，No.61572266）；浙江省自然科學基金資助項目（No.LY16F020003）

Foundations Items: The National Natural Science Foundation of China (No.61472194, No.61572266), Zhejiang Provincial Natural Science Foundation of China (No. LY16F020003)