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

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

SLSB-forest：高維數(shù)據(jù)的近似k近鄰查詢

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

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

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

近似k近鄰；局部敏感散列；高維數(shù)據(jù)

1 引言

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

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

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

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

圖1 均勻數(shù)據(jù)集分布情況

圖2 ANN_SIFT1M數(shù)據(jù)集分布情況

2 基礎(chǔ)知識

2.1 LSH

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

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

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

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

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

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

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

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

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

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

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

2.2 高維動(dòng)態(tài)數(shù)據(jù)索引SLSH

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

SLSH是用來解決不均勻數(shù)據(jù)集上（r,c）-近鄰查詢問題，對于c-AkNN查詢問題，SLSH會遇到和傳統(tǒng)LSH相似的問題。如果將查詢半徑r設(shè)置為查詢點(diǎn)和最近鄰的距離，SLSH的效率會很高，但是找到相應(yīng)的查詢半徑十分困難。即使找到對應(yīng)的r，不同查詢?nèi)蝿?wù)的r也會發(fā)生變化。

3 SLSB-forest

SLSH通過逐層散列的方法對數(shù)據(jù)集進(jìn)行散列，數(shù)據(jù)分布稀疏的區(qū)域用較大的桶切分，數(shù)據(jù)分布密集的區(qū)域用更細(xì)的桶進(jìn)行劃分。若要使SLSH支持多種近鄰查詢，必要的方法是對數(shù)據(jù)進(jìn)行較細(xì)的劃分，在查詢時(shí)如果候選點(diǎn)個(gè)數(shù)小于k，通過合并相鄰?fù)袄锏狞c(diǎn)直到候選點(diǎn)個(gè)數(shù)大于k。

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

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

SLSH無法快速地查找相鄰?fù)埃驗(yàn)槠渌惴ㄎ幢４婵臻g位置信息。常見的空間索引如R-tree因插入等操作較為繁瑣，效率也不高，因此提出了將SLSH和B-tree相結(jié)合的索引結(jié)構(gòu)，使索引結(jié)構(gòu)局部有序，在查找時(shí)可同時(shí)在不同層次的索引檢索，可以加速查找相鄰?fù)啊?/p>

3.1 SLSB-tree構(gòu)建

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

算法1 創(chuàng)建SLSB-tree

輸入：D (數(shù)據(jù)集), q (查詢點(diǎn)), t (Hash函數(shù)個(gè)數(shù)), N(單個(gè)桶最大存儲數(shù)據(jù)個(gè)數(shù))

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

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

SLSB-tree的關(guān)鍵是快速尋找相鄰?fù)?，如果桶號是一維的，即散列函數(shù)，可以由查詢點(diǎn)向外側(cè)依次查找相鄰?fù)埃菦]有與操作的LSH假陽性會很高。SLSB-tree除第一層之外的其他桶只是局部有序，每次尋找最近桶會在查找過程中消耗一些額外時(shí)間，考慮到近似近鄰查找只需滿足一定的近似比例，所以提出了兩種查詢方法：快速查找和準(zhǔn)確率優(yōu)先查找。

3.2 快速查找

快速查找的思想是每次向兩側(cè)尋找的桶不必是最近桶，只需要桶距小于給定的閾值。SLSB-tree每一層的桶號都是局部有序，即在同一個(gè)超桶下的所有桶是順序排列?？焖俨檎宜惴ㄈ缦拢翰樵兺疤枮椋挥诘趇層索引。查詢時(shí)如果需要查找鄰近桶，只需從q桶號向左右兩側(cè)順序選擇距離最近的桶查詢，向兩側(cè)查找有3個(gè)終止條件：①候選點(diǎn)個(gè)數(shù)大于k；②同一超桶下的桶都已查詢；③當(dāng)前索引中沒有滿足的桶，Δi是當(dāng)前索引層允許向兩側(cè)尋找的最大距離，每一層對應(yīng)一個(gè)Δi，計(jì)算方式在第4節(jié)給出。遇到終止條件①，直接跳出查詢；遇到終止條件②和③，需要返回第（i-1）層索引，從向外側(cè)查找最近桶。如果在第（i-1）層遇到其他超桶，需要在超桶對應(yīng)的下一層索引中查找，查找相鄰?fù)暗姆椒ê蜕鲜鲆恢隆?/p>

圖4 SLSB-forest結(jié)構(gòu)

3.3 準(zhǔn)確率優(yōu)先查找

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

遍歷候選桶隊(duì)列時(shí)，按順序計(jì)算候選桶與查詢桶的距離是否等于1，若不等于，跳過；若等于，需要分兩種情況。如果該桶是非超桶，則加入結(jié)果集并在隊(duì)列中將其刪除，并加入未遍歷的相鄰?fù)爸梁蜻x隊(duì)列中；如果是超桶，超桶對應(yīng)的索引按照 SLSB-tree查詢Δ=0的方法查詢，刪除此桶并加入未遍歷的相鄰?fù)?。?dāng)候選隊(duì)列遍歷結(jié)束，仍需查找更多相鄰?fù)?，從頭開始再次遍歷候選隊(duì)列查找桶距為Δ+1的桶。

以圖4 tree L為例，圖5展示了準(zhǔn)確率優(yōu)先查詢的過程。查詢點(diǎn)q的桶號{6,6}，查詢Δ=0時(shí)經(jīng)過桶{6}、{6,6}，將候選桶{5}、{7}和{6,5}、{6, 7}加入候選桶隊(duì)列中。當(dāng)需要查找Δ=1的相鄰?fù)皶r(shí)，僅需計(jì)算隊(duì)列中的桶號和查詢桶號的距離，滿足Δ=1的桶為{5}、{7}、{6,5}、{6, 7}，將其中的非超桶直接加入結(jié)果集中，并將它們未查詢過的相鄰?fù)皗4}、{8 }、{6, 3}加入候選隊(duì)列。對于超桶{7}，在其對應(yīng)的索引中查找與查詢桶在第二層索引相同的桶號即{7,6}加入結(jié)果集，查詢路徑過程中的鄰近且未查詢過的桶{7,8 }加入候選隊(duì)列中。若繼續(xù)查詢Δ=2，隊(duì)列中只有{4}、{8}兩個(gè)桶滿足，重復(fù)Δ=1時(shí)的查詢操作直到找到足夠的近鄰。

圖5 準(zhǔn)確率優(yōu)先查詢的過程

4 理論證明

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

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

其中，norm()是標(biāo)準(zhǔn)正態(tài)分布的累積分布函數(shù)，可以分別求出散列函數(shù)為，則在單個(gè)散列表中距離r的碰撞概率為。

4.1 準(zhǔn)確率優(yōu)先查詢范圍變化

準(zhǔn)確率優(yōu)先查詢的原理是增大桶寬擴(kuò)大查詢范圍，在尋找桶距為0、1、2…時(shí)，對應(yīng)的桶寬為w、3w、5w…，若桶距為Δ，對應(yīng)的散列函數(shù)桶寬為（ 2Δ+1)w。此處的桶寬（ 2Δ+1)w和直接設(shè)置散列函數(shù)的桶寬有明顯區(qū)別，因?yàn)槟繕?biāo)桶一直在寬為（ 2Δ+1)w桶的中央，碰撞概率的計(jì)算方式會有所改變。其計(jì)算方式如下：

查找相鄰?fù)暗母怕视?jì)算如圖6所示，通過隨機(jī)生成距離為[1,180]的點(diǎn)，每一個(gè)整數(shù)距離生成1 000對數(shù)據(jù)，設(shè)置桶寬w=50，通過實(shí)驗(yàn)來模擬解碰撞概率。圖6中平滑的曲線表示通過計(jì)算式計(jì)算的概率，波動(dòng)的曲線表示實(shí)驗(yàn)計(jì)算的概率。從圖6可以看出，實(shí)驗(yàn)計(jì)算的不同Δ的碰撞概率和通過公式計(jì)算的概率吻合，由此驗(yàn)證了理論推導(dǎo)的正確性。

圖6 查找相鄰?fù)暗母怕视?jì)算

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

圖7 準(zhǔn)確率優(yōu)先查詢范圍變化

4.2 快速查詢范圍變化

快速查詢的本質(zhì)是通過減小g(?)中散列函數(shù)的個(gè)數(shù)t達(dá)到擴(kuò)大查詢范圍的目的。查詢桶在第i層查詢，若需要返回上一層（i-1）層查詢時(shí)，在第i層查詢的桶可以合并為一個(gè)大桶。若g(?)散列函數(shù)個(gè)數(shù)由t變?yōu)椋僭O(shè)查詢范圍擴(kuò)大為α，需滿足通過求解方程：

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

圖8 快速查詢范圍變化

4.3 范圍變化對效率的影響

查詢范圍(r, c)的變化會直接影響查詢效率。設(shè)通過查詢相鄰?fù)安樵兎秶鷶U(kuò)大為(αr ,βc)，最理想的情況是α= β=1，但是此過程必定會使查詢范圍變大，所以希望α、 β盡可能小。不考慮r特別小的極端情況，快速查詢和準(zhǔn)確率優(yōu)先查詢相比，查詢同樣多的相鄰?fù)?，α快速＜α?zhǔn)確，但是，尤其當(dāng)r較大時(shí)，β快速將遠(yuǎn)遠(yuǎn)大于α快速。

α較小可以使查詢質(zhì)量更高，但是若β遠(yuǎn)大于α，會使假陽性增大，所以快速查詢在查詢近鄰個(gè)數(shù)較少或數(shù)據(jù)較密集時(shí)準(zhǔn)確率較高，因?yàn)槠鋵?yīng)的查詢范圍 r較小。當(dāng)數(shù)據(jù)稀疏或者查詢近鄰個(gè)數(shù)較大時(shí)，適合使用準(zhǔn)確率優(yōu)先查詢，因?yàn)楫?dāng)r越大時(shí)，α、 β不會隨著r發(fā)生明顯變化。

4.4 快速查找{Δ1,…, Δ2}的計(jì)算

設(shè)置每一層Δi的意義在于在當(dāng)前子索引中繼續(xù)向外側(cè)尋找相鄰?fù)安粫箿?zhǔn)確率發(fā)生明顯變化，停止當(dāng)前索引查找，返回上一層索引查詢相鄰?fù)?。根?jù)式（4）可以求出查詢到第i層索引對應(yīng)的查詢范圍(αir ,βic)。在第i層查詢桶號滿足到查詢桶號滿足的桶，距離為αir 的點(diǎn)碰撞概率變化為：

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

5 實(shí)驗(yàn)分析

本文實(shí)驗(yàn)環(huán)境的CPU為Intel Core i7-6500U、8 GB DDR3內(nèi)存，分別在3個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行測試，利用Java實(shí)現(xiàn)了SLSB-forest算法，并和傳統(tǒng)LSH、LSB-forest、C2LSH進(jìn)行對比。

5.1 實(shí)驗(yàn)數(shù)據(jù)集

Mnist[10]：包含60 000個(gè)手寫數(shù)字圖像的訓(xùn)練集，每一圖像由28 dpi×28 dpi個(gè)像素點(diǎn)構(gòu)成，相當(dāng)于一個(gè)784維的高維數(shù)據(jù)。Mnist還包含一個(gè)大小為10 000的測試集，從中抽取1 000個(gè)作為查詢對象。

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

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

5.2 性能評估

通過對比算法的查詢結(jié)果質(zhì)量和查詢時(shí)間開銷來評估SLSB-forest的好壞。

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

平均查詢時(shí)間（ART）：查詢時(shí)間主要分為桶查詢和候選集篩選兩部分。桶查詢包括目標(biāo)桶查找和相鄰?fù)安檎?，若查詢的近鄰?shù)量 k較小，桶查詢對平均查詢時(shí)間的影響較大；若 k較大，候選集篩選占平均查詢時(shí)間的比重很大。

5.3 實(shí)驗(yàn)比較

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

圖12和圖13是查詢時(shí)間的比較，可以看出4種查詢方法中最快的還是直接用LSH。本文實(shí)驗(yàn)中使用的 LSH是經(jīng)過多次調(diào)試尋找的較高效的參數(shù)，所以查詢速度較高。LSB-forest在 Color數(shù)據(jù)集上的查詢速度較快，但是LSB-forest要達(dá)到較高的準(zhǔn)確率一般需要建立20棵以上的樹，所以在相同準(zhǔn)確率的前提下SLSB-forest更具有優(yōu)勢。C2LSH在兩個(gè)數(shù)據(jù)集上的查詢速度均快于SLSB，但是和SLSB的快速查找算法相比優(yōu)勢并不明顯?？焖俨樵兿啾葴?zhǔn)確率優(yōu)先查詢速度更快，尤其在 Color數(shù)據(jù)集中。

圖10 Mnist數(shù)據(jù)集上的準(zhǔn)確率比較

圖11 Color數(shù)據(jù)集上的準(zhǔn)確率比較

圖12 Mnist數(shù)據(jù)集上的查詢時(shí)間比較

圖13 Color數(shù)據(jù)集上的查詢時(shí)間比較

快速查詢和準(zhǔn)確率優(yōu)先因?yàn)槠鋭?dòng)態(tài)擴(kuò)展查詢范圍的方式不一樣，在合并多個(gè)索引時(shí)候選集的數(shù)量也會有明顯區(qū)別。圖14是未合并前多個(gè)索引候選集的數(shù)量和，未合并是指沒有去除重復(fù)的候選集。圖15是合并之后的候選集數(shù)量，在未合并之前兩種查詢方法的候選集數(shù)量幾乎相同，但是合并之后準(zhǔn)確率優(yōu)先的候選集數(shù)量有一個(gè)明顯的下降，并且隨著k的增大下降得越明顯。其主要原因是快速查詢的β會隨著k的增大而遠(yuǎn)遠(yuǎn)大于α，假陽性明顯增高，而準(zhǔn)確率優(yōu)先α =β。如果查詢近鄰個(gè)數(shù)較多時(shí)，則優(yōu)先采用準(zhǔn)確率優(yōu)先查找，因?yàn)槠淇梢詼p少篩選候選集所消耗的時(shí)間。

圖14 未合并前多個(gè)索引候選集的數(shù)量和

6 結(jié)束語

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

圖15 合并之后的候選集數(shù)量

[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] 過潔, 徐曉旸, 潘金貴. 虛擬場景的一種快速優(yōu)化 Kd-Tree構(gòu)造方法[J]. 電子學(xué)報(bào), 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] 胡海苗, 姜帆. 基于可擴(kuò)展LSH的高維動(dòng)態(tài)數(shù)據(jù)索引[J]. 軟件學(xué)報(bào), 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] 吳軍. 大數(shù)據(jù)和機(jī)器智能對未來社會的影響[J]. 電信科學(xué), 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-），男，寧波大學(xué)信息科學(xué)與工程學(xué)院碩士生，主要研究方向?yàn)榇髷?shù)據(jù)、數(shù)據(jù)挖掘。

錢江波（1974-），男，博士，寧波大學(xué)信息科學(xué)與工程學(xué)院教授，主要研究方向?yàn)閿?shù)據(jù)處理與挖掘、邏輯電路設(shè)計(jì)、多維索引與查詢優(yōu)化。

董一鴻（1969-），男，博士，寧波大學(xué)信息科學(xué)與工程學(xué)院教授，主要研究方向?yàn)榇髷?shù)據(jù)、數(shù)據(jù)挖掘和人工智能。

陳華輝（1964-），男，博士，寧波大學(xué)信息科學(xué)與工程學(xué)院教授，主要研究方向?yàn)閿?shù)據(jù)處理與挖掘、云計(jì)算。

2017-03-22；

：2017-06-07

國家自然科學(xué)基金資助項(xiàng)目（No.61472194，No.61572266）；浙江省自然科學(xué)基金資助項(xiàng)目（No.LY16F020003）

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