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

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

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

通常情況，網(wǎng)絡(luò)可以分為兩類：規(guī)則網(wǎng)絡(luò)和隨機網(wǎng)絡(luò)[10]。對于規(guī)則網(wǎng)絡(luò)，研究較多的網(wǎng)絡(luò)模型是最近鄰耦合網(wǎng)絡(luò)（如圖1（a）），即每一個節(jié)點只是和它周邊的左右各k個鄰居節(jié)點相連。而隨機網(wǎng)絡(luò)中典型模型是由Erodos和Renyi提出的ER 隨機網(wǎng)絡(luò)模型，其中的任意頂點以相同的概率相連。小世界網(wǎng)絡(luò)是介于規(guī)則網(wǎng)絡(luò)和隨機網(wǎng)絡(luò)的中間過渡形態(tài)，兼有兩種網(wǎng)絡(luò)的特性。經(jīng)典的小世界模型有兩種：NW 模型[11]在規(guī)則連接模型的基礎(chǔ)上以概率p額外添加一批隨機連接（如圖1（b））；WS模型[12]則在規(guī)則連接模型的基礎(chǔ)上將部分規(guī)則連接以概率p替換為隨機連接（如圖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ò)的近鄰為直接與當前節(jié)點相連且距離相近的點；聚集系數(shù)用來反映節(jié)點與其鄰居節(jié)點間相互連接的程度，其定義為鄰居節(jié)點間實際存在的邊數(shù)與最多能存在的邊數(shù)的比值，即

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

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

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

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

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

3 逐跳逼近索引算法

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

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

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

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

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

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

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

3.2 查詢算法

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

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

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

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

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

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

3.3 維護算法

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

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

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

4 實驗與分析

4.1 實驗數(shù)據(jù)綜述

本文測試所用的高維數(shù)據(jù)向量分為隨機生成和實際數(shù)據(jù)兩類：隨機數(shù)據(jù)維度除對比和性能分析處外默認為10，取值均勻分布在0～255 之間，索引庫容量除對比分析處外默認為5 000 000；實際數(shù)據(jù)為Corel 圖像庫的圖像紋理特征描述符CoocTexture，其維度為16，庫容量68 040，元素為有符號浮點數(shù)（數(shù)據(jù)見http：//kdd.ics.uci.edu/database/ CorelFeatures/CorelFeatures.html）。設(shè) 定每個節(jié)點最多記錄25 個連接節(jié)點（20 個近鄰節(jié)點，5 個遠程節(jié)點），向量間的距離度量函數(shù)選用常見的L1 距離，測試結(jié)果均為50組隨機生成目標向量實驗結(jié)果的平均值。實驗軟硬件環(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ù)據(jù)庫的對比測試，由于特征庫容量小且數(shù)據(jù)分布不均，原始版本索引不再適用，則給出改進版索引測試數(shù)據(jù)。

4.2 庫容量變化對比測試

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

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

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

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

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

4.4 到達目標區(qū)域跳躍步數(shù)統(tǒng)計

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

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

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

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

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

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

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

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

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

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

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

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

分別對實際數(shù)據(jù)和隨機生成數(shù)據(jù)比較了逐跳逼近索引算法（固定近鄰數(shù)）與經(jīng)典的iDistance 算法和VA-File 算法的綜合性能，如表5 所示，其中的10 萬容量庫數(shù)據(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 相比，本文算法訪問比例稍有遜色，但近似向量在降低訪問比例的同時使查詢準確性損耗太大，故本文索引綜合性能仍明顯優(yōu)于VA-File。

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

5 結(jié)束語

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

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

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

[2] 張軍旗.支持最近鄰查找的高維空間索引[D].上海：復(fù)旦大學，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：一種有效的高維動態(tài)索引結(jié)構(gòu)[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].北京：清華大學出版社，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].小型微型計算機系統(tǒng)，2010，31（9）：1764-1769.