基于小世界模型的高維索引算法

桂舒婷，鄭 烇，周樂樂，劉 欣，王 嵩

GUI Shuting,ZHENG Quan,ZHOU Lele,LIU Xin,WANG Song

中國科學(xué)技術(shù)大學(xué) 信息科學(xué)技術(shù)學(xué)院 自動(dòng)化系，合肥230027

School of Information and Technology,University of Science and Technology of China,Heifei 230027,China

1 引言

隨著計(jì)算機(jī)和互聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展，人們可以訪問到的數(shù)據(jù)量急劇膨脹，大數(shù)據(jù)時(shí)代已經(jīng)來臨，而如何有效地管理和檢索這些海量數(shù)據(jù)變得至關(guān)重要。與此同時(shí)，由于檢索精度要求的提高而引起查詢所依據(jù)的特征向量維度的不斷變高也給管理及檢索帶來了一系列的挑戰(zhàn)[1]。高維索引（High-dimensional Indexing）作為其中的一項(xiàng)重要技術(shù)已成為當(dāng)今的研究熱點(diǎn)。

高維索引技術(shù)是研究通過建立索引結(jié)構(gòu)來提高高維數(shù)據(jù)庫檢索效率的一門關(guān)鍵技術(shù)。作為基于內(nèi)容檢索和模式識別領(lǐng)域的一項(xiàng)關(guān)鍵技術(shù)，國內(nèi)外很多研究機(jī)構(gòu)自20 世紀(jì)70 年代便對其進(jìn)行了研究。它涉及計(jì)算幾何、數(shù)據(jù)庫技術(shù)和模式識別等學(xué)科，并且已被推廣到GIS，生物信息數(shù)據(jù)庫，遙感光譜數(shù)據(jù)集等諸多研究領(lǐng)域[2]。在這些領(lǐng)域中，數(shù)據(jù)的維度普遍較高，且具有高度稀疏性，傳統(tǒng)的索引結(jié)構(gòu)如R 樹系列[3]、近似向量算法[4]、降維檢索和聚類檢索等[5]面臨嚴(yán)重的“維數(shù)災(zāi)難”問題。到目前為止，還沒有出現(xiàn)一種獲得公認(rèn)并被大量推廣運(yùn)用的算法或解決方案。

本文提出一種新的高維索引算法，稱之為逐跳逼近索引。該算法參考社交網(wǎng)絡(luò)中的六度分隔理論，將高維向量空間建模為小世界模型網(wǎng)絡(luò)，相似查詢過程轉(zhuǎn)換為從隨機(jī)起始節(jié)點(diǎn)到目標(biāo)相似區(qū)域的逐跳逼近，使得僅需訪問少量節(jié)點(diǎn)即可快速準(zhǔn)確地找到目標(biāo)，從而在處理高維度和海量數(shù)據(jù)庫檢索中能達(dá)到良好的檢索效果。

2 相關(guān)知識背景

2.1 主流高維索引技術(shù)

自20 世紀(jì)70 年代起，國內(nèi)外研究者對高維索引技術(shù)進(jìn)行了大量研究，主要方法集中在構(gòu)建良好的索引結(jié)構(gòu)和降低索引維度上。現(xiàn)有的高維索引技術(shù)主要分為兩大類：樹型結(jié)構(gòu)和非樹型結(jié)構(gòu)。

基于樹型結(jié)構(gòu)的索引是研究最多的高維索引技術(shù)，主要分為向量空間和度量空間兩大類。在向量空間高維索引中，樹型索引結(jié)構(gòu)按照節(jié)點(diǎn)的建立方式不同，又可以劃分為數(shù)據(jù)點(diǎn)劃分和空間劃分。數(shù)據(jù)點(diǎn)劃分的索引結(jié)構(gòu)根據(jù)數(shù)據(jù)分布來分隔空間，其代表性算法有R 樹及其變種R+樹、R*樹、X 樹、SS 樹及SR 樹等[3]。空間劃分則是對多維空間進(jìn)行重復(fù)分割，分割成的不相連的子空間中的數(shù)據(jù)用節(jié)點(diǎn)來表示，如K-D 樹、K-D-B 樹以及四叉樹等[6]。度量空間中樹型結(jié)構(gòu)也有很多經(jīng)典算法，如M樹及其變種[7]、VP 樹及其變種、FQ 樹等。除此之外，研究者對一些經(jīng)典算法進(jìn)行改進(jìn)并提出了許多新型索引結(jié)構(gòu)。比如孫勁光提出一種新的索引結(jié)構(gòu)CKDB-Tree，采用一種新的分裂策略，在進(jìn)行分裂時(shí)，引入插入安全點(diǎn)和刪除安全點(diǎn)的概念，不僅考慮到將來的數(shù)據(jù)，而且對已經(jīng)進(jìn)行索引的數(shù)據(jù)也進(jìn)行考慮[8]。總體來說，樹型結(jié)構(gòu)索引在低維度情況下性能優(yōu)秀，但隨著維度的增加，受空間重疊及過度劃分影響使得索引性能呈指數(shù)性下降，最終甚至劣于順序查找，產(chǎn)生“維數(shù)災(zāi)難”現(xiàn)象。

與此同時(shí)，許多研究者也對非樹型結(jié)構(gòu)進(jìn)行了許多研究。其中包括不受維度限制且理想情況擁有O(1)時(shí)間復(fù)雜度的Hash 算法，比如早期的網(wǎng)格文件算法和目前研究較多的位置敏感哈希函數(shù)；以及利用降維的思想將高維數(shù)據(jù)映射到更低維空間，在低維空間繼續(xù)處理的金字塔技術(shù)、一維轉(zhuǎn)換降維、主成分分析降維以及聚類降維[5]等。

2.2 小世界理論及其應(yīng)用

小世界理論（Small World Theory）由美國哈佛大學(xué)社會心理學(xué)家Stanley Milgram 在1967 年提出[9]，起初用于描述社會人際網(wǎng)絡(luò)關(guān)系，后來發(fā)展運(yùn)用至生物學(xué)、物理學(xué)、計(jì)算機(jī)科學(xué)等領(lǐng)域。其理論核心是：盡管現(xiàn)實(shí)世界網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量龐大，看似連接松散，但從一個(gè)節(jié)點(diǎn)只需經(jīng)過有限的幾步跳躍就能到達(dá)任意其他節(jié)點(diǎn)。小世界理論的提出引發(fā)了研究者對網(wǎng)絡(luò)的進(jìn)一步描述和建模。

通常情況，網(wǎng)絡(luò)可以分為兩類：規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)[10]。對于規(guī)則網(wǎng)絡(luò)，研究較多的網(wǎng)絡(luò)模型是最近鄰耦合網(wǎng)絡(luò)（如圖1（a）），即每一個(gè)節(jié)點(diǎn)只是和它周邊的左右各k個(gè)鄰居節(jié)點(diǎn)相連。而隨機(jī)網(wǎng)絡(luò)中典型模型是由Erodos和Renyi提出的ER 隨機(jī)網(wǎng)絡(luò)模型，其中的任意頂點(diǎn)以相同的概率相連。小世界網(wǎng)絡(luò)是介于規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)的中間過渡形態(tài)，兼有兩種網(wǎng)絡(luò)的特性。經(jīng)典的小世界模型有兩種：NW 模型[11]在規(guī)則連接模型的基礎(chǔ)上以概率p額外添加一批隨機(jī)連接（如圖1（b））；WS模型[12]則在規(guī)則連接模型的基礎(chǔ)上將部分規(guī)則連接以概率p替換為隨機(jī)連接（如圖1（c））。

圖1 近鄰耦合網(wǎng)絡(luò)、NW 模型網(wǎng)絡(luò)和WS 模型網(wǎng)絡(luò)

由于本文提出的逐跳逼近索引是按NW 模型的方法構(gòu)造的，下面以NW 模型為主闡述小世界模型中近鄰數(shù)量、聚集系數(shù)、特征路徑長度等關(guān)鍵參數(shù)的一些特性。網(wǎng)絡(luò)的近鄰為直接與當(dāng)前節(jié)點(diǎn)相連且距離相近的點(diǎn)；聚集系數(shù)用來反映節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)間相互連接的程度，其定義為鄰居節(jié)點(diǎn)間實(shí)際存在的邊數(shù)與最多能存在的邊數(shù)的比值，即

特征路徑長度指的是一個(gè)網(wǎng)絡(luò)中兩點(diǎn)之間最短路徑長度（或稱距離）的平均值，令N為網(wǎng)絡(luò)中的總節(jié)點(diǎn)數(shù)，dij定義為連接節(jié)點(diǎn)i和j的最短路徑上的跳（邊）數(shù)，則特征路徑長度為：

對于NW 模型，其聚集系數(shù)為：

兩者的特征路徑長度可表示為：

其中的f(u)為一普適標(biāo)度函數(shù)，目前只有近似的估計(jì)值而還沒有精確值的推算結(jié)果。

由上述式子容易驗(yàn)證，在p很小而N很大的實(shí)際情況中，WS 和NW的參數(shù)值極為接近[10]。Kleinberg 在理論上研究了WS 小世界網(wǎng)絡(luò)的跳躍特性，證明了在簡單柵格（Grid）網(wǎng)絡(luò)模型中，從任何一個(gè)節(jié)點(diǎn)跳躍到其他任何一個(gè)節(jié)點(diǎn)，平均跳數(shù)存在一個(gè)對數(shù)級的上界[13]。這給一個(gè)很好的啟示，即：如果把需要索引的數(shù)據(jù)看成空間的點(diǎn)（社交網(wǎng)絡(luò)中的一個(gè)用戶）所構(gòu)成的復(fù)雜網(wǎng)絡(luò)，將被檢索的節(jié)點(diǎn)當(dāng)成是一個(gè)需要在社交網(wǎng)絡(luò)中找到朋友的用戶，從它開始在海量節(jié)點(diǎn)網(wǎng)絡(luò)中逼近跳躍，只需要非常有限的幾跳（如2012 年時(shí)Facebook 中任意兩個(gè)用戶間平均僅需4.7 跳[14]）就能夠到達(dá)目標(biāo)節(jié)點(diǎn)，其檢索效率仍非常高。

3 逐跳逼近索引算法

逐跳逼近索引是一種自組織的索引結(jié)構(gòu)，僅維護(hù)各個(gè)局部區(qū)域點(diǎn)與點(diǎn)的鄰近關(guān)系，具有類似于度量空間索引的性質(zhì)，而未對高維數(shù)據(jù)空間做任何整體劃分。基于逐跳逼近索引的高維向量查詢則依靠局部點(diǎn)與點(diǎn)的關(guān)聯(lián)，將查詢過程的“關(guān)注點(diǎn)”逐步往查詢命中區(qū)域移動(dòng)或逼近，最終實(shí)現(xiàn)查詢。該算法不受維度限制，當(dāng)庫容量增大時(shí)，圖內(nèi)部的連接將更加緊密，使得其上的逼近查詢結(jié)果準(zhǔn)確度和效率上升，尤其適用于大規(guī)模特征庫。圖2 為該算法示意圖，圖中節(jié)點(diǎn)0 為起始節(jié)點(diǎn)，通過四次跳躍到達(dá)了查詢節(jié)點(diǎn)的相似判定范圍內(nèi)。

圖2 逐跳逼近索引算法示意圖

3.1 索引結(jié)構(gòu)與生成

逐跳逼近索引首先要將特征數(shù)據(jù)庫建模成一張圖，圖中的頂點(diǎn)V表示特征數(shù)據(jù)庫中的一個(gè)特征向量；邊E存在于兩個(gè)鄰近的特征向量，或被以一定概率選中的遠(yuǎn)程節(jié)點(diǎn)間。表1 為實(shí)驗(yàn)中逐跳逼近索引數(shù)據(jù)存儲的部分?jǐn)?shù)據(jù)示例，其中近鄰節(jié)點(diǎn)為一定閾值范圍內(nèi)的近鄰連接，在索引建立時(shí)生成，以距離和編號的二元組形式存儲，按距離大小從小到大排列，其中節(jié)點(diǎn)間相似性度量的距離定義需根據(jù)實(shí)際應(yīng)用場景而定，逐跳逼近索引結(jié)構(gòu)僅維護(hù)節(jié)點(diǎn)間的距離關(guān)系，與具體的距離定義關(guān)系不大且具有一定適用面（滿足三角不等式關(guān)系的連續(xù)距離函數(shù)大都適用）；而遠(yuǎn)程節(jié)點(diǎn)則為隨機(jī)遠(yuǎn)程節(jié)點(diǎn)，在運(yùn)行時(shí)動(dòng)態(tài)生成，表中數(shù)據(jù)僅為示例。

實(shí)際上，上述逐跳逼近索引文件所表征的為圖的基本信息，即整個(gè)索引的目的是構(gòu)建當(dāng)前特征庫的圖表示。而對具體的逐跳逼近索引，可以通過調(diào)節(jié)三個(gè)參數(shù)來影響特征庫圖。參數(shù)一是單個(gè)節(jié)點(diǎn)的最大度數(shù)限制，用于統(tǒng)一逐跳逼近索引的形式，便于存儲管理。參數(shù)二是判定節(jié)點(diǎn)鄰近的間距閾值，該閾值影響特征庫圖內(nèi)部的連通性，減小該值將使特征庫圖中節(jié)點(diǎn)分散連通性變差，增大該值使索引的近鄰數(shù)增多，索引變大。參數(shù)三則是隨機(jī)遠(yuǎn)程連接數(shù)，該參數(shù)將改變在前面的規(guī)則圖中引入了隨機(jī)網(wǎng)絡(luò)特征，能有效降低整個(gè)圖的特征路徑長度。

除表1 外，逐跳逼近索引還有另一個(gè)原理相同的改進(jìn)版，該改進(jìn)版中近鄰節(jié)點(diǎn)數(shù)為指定固定數(shù)值，即每個(gè)節(jié)點(diǎn)中的近鄰為與當(dāng)前節(jié)點(diǎn)最近的若干個(gè)節(jié)點(diǎn)信息。這樣改進(jìn)之后的索引能夠處理小庫容量和特征庫內(nèi)數(shù)據(jù)分布不均勻引起的原始索引連通性較差的情況，所需付出的代價(jià)是生成和維護(hù)索引的時(shí)間將會增加，索引數(shù)據(jù)如圖3 所示。

圖3 改進(jìn)逐跳逼近索引數(shù)據(jù)示例

3.2 查詢算法

逐跳逼近過程分為兩個(gè)階段：第一階段為快速逐跳逼近，目的盡可能快地為第二階段提供在目標(biāo)區(qū)域內(nèi)的優(yōu)質(zhì)種子集。第二階段為精確逐跳逼近，目的是找到盡可能多的目標(biāo)匹配節(jié)點(diǎn)。其大致流程如圖4 所示。

圖4 逐跳逼近索引查詢流程圖

第一步，從特征庫中隨機(jī)選擇若干節(jié)點(diǎn)作為初始種子節(jié)點(diǎn)，并根據(jù)其與目標(biāo)節(jié)點(diǎn)的距離由近到遠(yuǎn)插入初始種子節(jié)點(diǎn)隊(duì)列。逐跳逼近時(shí)，每次選擇隊(duì)首節(jié)點(diǎn)作為下一步逐跳逼近步驟的種子節(jié)點(diǎn)，讀取數(shù)據(jù)點(diǎn)的逐跳逼近索引，并計(jì)算其鄰居節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)間的距離關(guān)系，選擇部分節(jié)點(diǎn)更新初始種子節(jié)點(diǎn)隊(duì)列。

表1 實(shí)驗(yàn)逐跳逼近索引局部數(shù)據(jù)

第二步，循環(huán)重復(fù)第一步過程，下一步跳躍逼近總是從目前最接近目標(biāo)的節(jié)點(diǎn)開始，直到跳到目標(biāo)節(jié)點(diǎn)的匹配范圍之內(nèi)，并將此范圍內(nèi)的節(jié)點(diǎn)作為優(yōu)質(zhì)種子插入優(yōu)質(zhì)種子節(jié)點(diǎn)隊(duì)列。這里的匹配范圍，在范圍查詢里為范圍查詢的范圍閾值；在近似kNN 查詢里是預(yù)置范圍閾值，該預(yù)置閾值由累計(jì)檢索統(tǒng)計(jì)數(shù)據(jù)計(jì)算得出，在每次查詢的過程中根據(jù)具體情況做適量調(diào)整。

第三步，當(dāng)跳躍已經(jīng)進(jìn)入目標(biāo)數(shù)據(jù)匹配范圍，對優(yōu)質(zhì)種子計(jì)算其鄰居節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的距離，記錄當(dāng)前搜索到的匹配節(jié)點(diǎn)，同時(shí)用其鄰居節(jié)點(diǎn)更新優(yōu)質(zhì)種子節(jié)點(diǎn)隊(duì)列，循環(huán)重復(fù)該過程。對于范圍查詢，若不設(shè)置提前終止條件，逐跳逼近會進(jìn)行到優(yōu)先隊(duì)列中全部種子節(jié)點(diǎn)處理完為止。對于近似kNN 查詢，可根據(jù)需要設(shè)置終止上限數(shù)，用來控制對查詢速度和結(jié)果準(zhǔn)確性的偏向。

3.3 維護(hù)算法

當(dāng)向特征庫中添加一個(gè)特征向量時(shí)，對于逐跳逼近索引，添加的特征向量只影響其鄰居節(jié)點(diǎn)，包括近鄰節(jié)點(diǎn)和遠(yuǎn)程節(jié)點(diǎn)。對于近鄰節(jié)點(diǎn)，只需要調(diào)用一次對要添加的特征向量的范圍查詢操作，然后讀取并更新查找到的所有鄰近向量的逐跳逼近索引項(xiàng)，并根據(jù)查找操作返回的鄰近向量建立當(dāng)前特征向量的逐跳逼近索引項(xiàng)；對于遠(yuǎn)程節(jié)點(diǎn)，由于其與現(xiàn)有數(shù)據(jù)不直接相關(guān)，故可按照索引生成算法直接生成。

當(dāng)從特征庫中刪除一個(gè)特征向量時(shí)，其操作與添加操作基本對稱。對于近鄰節(jié)點(diǎn)，同樣也是先調(diào)用一次范圍查詢操作，再更新所有找到的鄰近向量和當(dāng)前數(shù)據(jù)的逐跳逼近索引項(xiàng)中的所有鄰近向量的逐跳逼近索引項(xiàng)，最后刪除當(dāng)前特征向量的逐跳逼近索引項(xiàng)；對于遠(yuǎn)程節(jié)點(diǎn)，直接刪除其連接中的當(dāng)前特征向量的逐跳逼近索引項(xiàng)。

對于改進(jìn)的逼近索引算法，添加特征向量過程與上面一致。刪除過程可先用一個(gè)標(biāo)識位表明該節(jié)點(diǎn)已刪除，不能作為結(jié)果返回，但保留此節(jié)點(diǎn)的跳越功能，積累到一定數(shù)量后作索引更換處理。

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)綜述

本文測試所用的高維數(shù)據(jù)向量分為隨機(jī)生成和實(shí)際數(shù)據(jù)兩類：隨機(jī)數(shù)據(jù)維度除對比和性能分析處外默認(rèn)為10，取值均勻分布在0～255 之間，索引庫容量除對比分析處外默認(rèn)為5 000 000；實(shí)際數(shù)據(jù)為Corel 圖像庫的圖像紋理特征描述符CoocTexture，其維度為16，庫容量68 040，元素為有符號浮點(diǎn)數(shù)（數(shù)據(jù)見http：//kdd.ics.uci.edu/database/ CorelFeatures/CorelFeatures.html）。設(shè) 定每個(gè)節(jié)點(diǎn)最多記錄25 個(gè)連接節(jié)點(diǎn)（20 個(gè)近鄰節(jié)點(diǎn)，5 個(gè)遠(yuǎn)程節(jié)點(diǎn)），向量間的距離度量函數(shù)選用常見的L1 距離，測試結(jié)果均為50組隨機(jī)生成目標(biāo)向量實(shí)驗(yàn)結(jié)果的平均值。實(shí)驗(yàn)軟硬件環(huán)境為Intel Core i3-2328M CPU@2.20 GHz，3 GB RAM，開發(fā)環(huán)境為Windows 7下的Visual Studio 2010。

在100 萬及以上容量的均勻特征庫中，由于圖內(nèi)連通性較好，本文兩種索引沒有明顯性能差別，僅給出原始版本測試數(shù)據(jù)。對實(shí)際數(shù)據(jù)庫的對比測試，由于特征庫容量小且數(shù)據(jù)分布不均，原始版本索引不再適用，則給出改進(jìn)版索引測試數(shù)據(jù)。

4.2 庫容量變化對比測試

首先對本算法在各種庫容量中的性能進(jìn)行了整體測試，結(jié)果如圖5 所示。當(dāng)庫容量線性增長時(shí)，相關(guān)kNN 查詢的平均訪問數(shù)據(jù)條數(shù)增長幅度逐步降低，其中5 000 000 庫訪問數(shù)據(jù)條數(shù)僅為1 000 000 庫的兩倍不到；且查詢平均精確度有明顯提升。整體來看，算法在大容量數(shù)據(jù)庫中擁有更好的性能，適合處理海量數(shù)據(jù)庫查詢。

圖5 不同庫容量索引性能對比圖

4.3 鄰居節(jié)點(diǎn)數(shù)與近鄰范圍閾值

通過改變鄰居數(shù)量和鄰居距離閾值，本文測試了5 000 000 庫的范圍查找時(shí)間性能數(shù)據(jù)，如表2 所示。由實(shí)驗(yàn)數(shù)據(jù)可以看出，提高鄰居節(jié)點(diǎn)的距離閾值，可以一定程度提高查全率，且在誤差范圍內(nèi)對數(shù)據(jù)訪問比例和查詢時(shí)間沒有影響。但當(dāng)閾值超過一定值，查全率將與鄰居節(jié)點(diǎn)數(shù)相關(guān)。同時(shí)，增加鄰居數(shù)量，訪問數(shù)據(jù)比例和查詢時(shí)間增加，而平均查全率在一定范圍內(nèi)能顯著提高，當(dāng)增加到25%時(shí)，查全率的提高將變得緩慢，并慢慢趨于100%。

表2 對5 000 000 庫的范圍查找綜合測試

4.4 到達(dá)目標(biāo)區(qū)域跳躍步數(shù)統(tǒng)計(jì)

選擇4.1 節(jié)中闡述的關(guān)鍵實(shí)驗(yàn)參數(shù)進(jìn)行1 000 次范圍查詢測試，統(tǒng)計(jì)第一階段的跳躍步數(shù)，其分布如表3所示。

表3 逐跳逼近索引實(shí)驗(yàn)查詢跳數(shù)分布表

不難看出，以上測試中95%以上的查詢均在6 跳以內(nèi)就達(dá)到目標(biāo)區(qū)域，即在圖上一個(gè)節(jié)點(diǎn)平均只需不到6跳就可到達(dá)任意節(jié)點(diǎn)，這也與小世界理論的特征相符合。

4.5 優(yōu)質(zhì)節(jié)點(diǎn)入隊(duì)閾值與相似判斷閾值

參數(shù)相似判斷閾值為判斷當(dāng)前特征向量是否為相似特征向量的距離閾值，它的大小決定返回結(jié)果的多少；入隊(duì)閾值用于判斷當(dāng)前節(jié)點(diǎn)是否為優(yōu)質(zhì)節(jié)點(diǎn)（第一階段游走中與目標(biāo)足夠接近的點(diǎn)），直接影響第一階段游走結(jié)束時(shí)間，并顯著影響第二階段游走過程中訪問的節(jié)點(diǎn)數(shù)量以及最終的查全率，其設(shè)置不能小于相似性判斷閾值。圖6 和圖7 分別為相似判斷閾值和入隊(duì)閾值對實(shí)驗(yàn)結(jié)果的影響。

圖6 范圍查全率和數(shù)據(jù)訪問比例隨入隊(duì)閾值變化圖

圖7 范圍查全率和數(shù)據(jù)訪問比例隨相似判斷閾值變化圖

由圖6 可以看出，在一定范圍內(nèi)加大入隊(duì)閾值可以提高平均查全率，但會訪問更多的數(shù)據(jù)，由此帶來時(shí)間消耗。而對于每個(gè)特定的查詢，相似性判斷閾值已確定，與之對應(yīng)的入隊(duì)閾值也需進(jìn)行調(diào)整，否則會導(dǎo)致查全率降低。如圖7 所示，此時(shí)入隊(duì)閾值設(shè)為190，當(dāng)相似性判斷閾值越高，平均查全率則降低，故在實(shí)驗(yàn)中，入隊(duì)閾值的選擇需要結(jié)合綜合性能和相似性判斷閾值來確定。

4.6 逐跳逼近轉(zhuǎn)換節(jié)點(diǎn)數(shù)

逐跳逼近轉(zhuǎn)換節(jié)點(diǎn)數(shù)是逐跳逼近從第一階段轉(zhuǎn)換為第二階段的條件。由表4 可知，當(dāng)該值較小時(shí)，第一階段為第二階段提供的優(yōu)質(zhì)種子少，需更多的逐跳逼近才能找到匹配的節(jié)點(diǎn)，而當(dāng)該值較大時(shí)，第一階段已經(jīng)有足夠的優(yōu)質(zhì)種子，第二階段需要訪問的條數(shù)相對就較少。同時(shí)可以看到，該參數(shù)對平均查全率基本沒有影響，主要原因在于對相互連通較好的圖，一般情況只需要一個(gè)優(yōu)質(zhì)種子就可以通過不斷逐跳逼近找到所有匹配節(jié)點(diǎn)。

表4 對5 000 000 庫的范圍查找綜合測試

4.7 性能對比與總結(jié)

分別對實(shí)際數(shù)據(jù)和隨機(jī)生成數(shù)據(jù)比較了逐跳逼近索引算法（固定近鄰數(shù)）與經(jīng)典的iDistance 算法和VA-File 算法的綜合性能，如表5 所示，其中的10 萬容量庫數(shù)據(jù)為自動(dòng)生成的均勻隨機(jī)數(shù)，68 040 容量庫為Corel圖庫的CoocTexture特征描述符數(shù)據(jù)。

表5 本文算法與iDistance，VA-File 性能對比

根據(jù)表5及以上數(shù)據(jù)可以看出，在小庫容量中，本文算法的數(shù)據(jù)訪問比例會有一定增加，其主要原因在于訪問跳數(shù)有一定的下限，對于小庫容量，比例會有所上升。但與其他很多索引結(jié)構(gòu)，比如iDistance 相比，其訪問比例仍然較小。與VA-File 相比，本文算法訪問比例稍有遜色，但近似向量在降低訪問比例的同時(shí)使查詢準(zhǔn)確性損耗太大，故本文索引綜合性能仍明顯優(yōu)于VA-File。

對于實(shí)際特征數(shù)據(jù)對比模塊，數(shù)據(jù)的不均勻分布一定程度上增加了訪問的跳數(shù)及訪問數(shù)據(jù)比例，且對范圍查全率有輕微影響，但整體來說影響不大，本文算法仍能有效處理。

5 結(jié)束語

本文針對高維索引問題，提出一種基于圖的高維索引算法——逐跳逼近索引算法，及其一種改進(jìn)版本，算法以小世界模型理論為基礎(chǔ)，建立自組織索引結(jié)構(gòu)，維護(hù)局部區(qū)域點(diǎn)與點(diǎn)在度量空間上的鄰近關(guān)系，同時(shí)融入圖上的跳躍逼近思想，從圖中任意節(jié)點(diǎn)出發(fā)，每次僅利用當(dāng)前節(jié)點(diǎn)的局部信息，選擇與目標(biāo)節(jié)點(diǎn)最近的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)，從而將查詢過程的“關(guān)注點(diǎn)”逐步往查詢命中區(qū)域逼近。

該算法結(jié)構(gòu)簡單，具有良好的可維護(hù)性和拓展性，同時(shí)基于其查詢訪問數(shù)據(jù)比例極小，且比例會因特征庫容量增大，連通性加強(qiáng)而進(jìn)一步降低，特別適合大特征庫的相似性查詢；此外，算法各部分僅依靠局部信息跳躍查找，特性極為適合應(yīng)用于分布式場合，可進(jìn)一步加強(qiáng)其進(jìn)行大規(guī)模查詢的性能。因而，對該算法的下一步研究工作主要為其在高維度大規(guī)模特征庫中的分布式查詢實(shí)驗(yàn)。

[1] 謝毓湘，吳玲達(dá)，欒悉道.基于內(nèi)容的圖像檢索技術(shù)研究[J].計(jì)算機(jī)工程與應(yīng)用，2002，38（1）：35-38.

[2] 張軍旗.支持最近鄰查找的高維空間索引[D].上海：復(fù)旦大學(xué)，2007.

[3] Li G，Tang J.A new R-tree spatial index based on space grid coordinate division[C]//Proceedings of the 2011，International Conference on Informatics，Cybernetics，and Computer Engineering（ICCE2011）.Berlin Heidelberg：Springer，2012：133-140.

[4] Lv T，Xie F R.HVA-Index：An efficient indexing method for similarity search in high-dimensional vector spaces[C]//2010 International Conference on Information Networking and Automation.IEEE，2010，2：152-157.

[5] Gunnemann S，Kremer H，Lenhard D，et al.Subspace clustering for indexing high dimensional data：a main memory index based on local reductions and individual multi-representations[C]//Proceedings of the 14th International Conference on Extending Database Technology.ACM，2011：237-248.

[6] Bentley J L.Multidimensional binary search trees used for associative searching[J].Communications of the ACM，1975，18（9）：509-517.

[7] Ciaccia P，Patella M.M-tree：An efficient access method for similarity search in metric spaces[C]//Proceedings of theInternational Conference on Very Large Data Bases.Morgan Kaufmann Pub，1997，23：426-435.

[8] 孫勁光，王淑娥.CKDB-Tree：一種有效的高維動(dòng)態(tài)索引結(jié)構(gòu)[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（30）：157-160.

[9] Travers J，Milgram S.An experimental study of the small world problem[J].Sociometry，1969，32（4）：425-443.

[10] 汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：清華大學(xué)出版社，2005.

[11] Newman M E J，Watts D J.Renormalization group analysis of the small-world network model[J].Physics Letters A，1999，263（4）：341-346.

[12] Watts D J，Strogatz S H.Collective dynamics of‘small-world’networks[J].Nature，1998，393（6684）：440-442.

[13] Kleinberg J.The small-world phenomenon：An algorithmic perspective[C]//Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing.ACM，2000：163-170.

[14] Johan U，Brian K，Lars B，et al.The anatomy of the Facebook social graph [J].The Anatomy of Facebook，2011：1-17.

[15] 蔣瀾，朱明.基于DHT的高維數(shù)據(jù)相似性檢索方法研究[J].小型微型計(jì)算機(jī)系統(tǒng)，2010，31（9）：1764-1769.