基于區位碼和距離的Chord網絡高維數據范圍檢索

孟憲福， 孟泓汐， 張振強

（1.大連理工大學計算機科學與技術學院，遼寧大連116024；2.大連海事大學信息科學技術學院，遼寧大連116026）

0 引 言

隨著P2P技術的發展，P2P網絡已經在多個領域得到實際應用，比如資源共享等，而在P2P環境下進行范圍檢索已成為用戶的迫切需要.

Chord是由環形組成的結構化P2P網絡，它所具有的良好的數據檢索效率、容錯性和自適應性等，使其已成為具有高可擴展性和高效率的實用結構化P2P模型［1］.但由于Chord是基于DHT（distributed hash table）的，并不能有效地支持范圍檢索等相似性檢索.

在已有的研究中，對高維數據進行范圍查詢所采用的基本方法是降維策略，文獻［2］提出了被稱為M－Chord的網絡結構，其中采用的索引技術是iDistance［3］，即通過將高維數據降至一維，然后采用位置保持哈希技術［4］將其映射到Chord網絡的對應節點上來實現高維數據檢索.然而，由于在查詢時這種結構只對索引值進行一次過濾，將產生大量“誤中點”［5］，增加了對冗余信息進行精簡的時間.

文獻［6］采用了基于代表點空間劃分策略的一種Chord網絡結構，該結構利用事先確定的代表點將整個數據空間劃分為數個子空間，每個代表點僅對應一個子空間，在此基礎上，將代表點映射到一維區間上，并將代表點的一維索引標識作為Chord網絡中節點的哈希值.由于是基于準隨機序列的均勻分布特性來選取代表點的，對于那些不均勻的數據集，在進行范圍檢索時會產生大量的“誤中點”，影響了檢索效率.

文獻［7］利用Hilbert曲線將高維數據映射到Chord環上，文獻［8］則給出了以空間填充曲線為基礎的范圍劃分方法，這幾種方法都能在Chord網絡上實現高維數據的范圍檢索.但是，這些方法對低維度數據可行，對高維度數據會出現“維度災難”問題，不能很好地適應數據維度的增長.

VA－file近似向量索引方法［9］將數據空間劃分為2b個長方形單元格，對每個單元格利用長度為b的字符串序列進行標識，對全部的高維點數據利用所屬單元格標識符進行近似表示，并通過順序掃描近似向量來實現范圍檢索.顯然，VA－file方法的搜索效率在很大程度上受數據分布的影響.與VA－file方法不同，文獻［10］所提出的區位碼近似向量壓縮技術是利用與參考點的相對位置關系將多維向量數據近似表示為位碼字符串，在檢索時通過比較查詢點與某個點之間的不相同位碼的位數，來判斷該點是否為候選數據點.

基于區位碼的優化高維索引結構［11］不僅利用iDistance距離來表示對象點和參考點之間的遠近關系，同時利用區位碼來近似表示它們之間的位置關系，以便將多維向量壓縮為二維向量.

本文在Chord網絡協議和已有的高維數據索引算法的基礎上，提出BM－Chord網絡結構，以解決高維數據的范圍檢索問題.BM－Chord網絡結構采用iDistance和區位碼向量壓縮兩種技術將高維數據降為一維，然后利用位置保持哈希函數將一維索引值映射到Chord網絡環上，環上的每個節點利用B＋樹結構來保存數據索引值.在此基礎上，利用本文提出的檢索算法和過濾技術，實現基于Chord網絡的多維數據的范圍檢索.

1 空間的劃分策略

一般來講，可以事先確定Chord網絡中可容納的最大節點個數M，這樣，為了確保每個節點至少擁有一個子空間，就需要將整個數據空間劃分為不小于M的子空間.因為iDistance索引技術是將數據空間劃分為N個聚類，而N又小于M，因此不能直接利用；前面介紹的基于區位碼的向量壓縮技術是將數據空間劃分為2d′個子分區.如果將這兩種方法結合起來，則可將數據空間劃分為N2d′個子分區，這樣就能滿足每個節點至少有一個子分區索引值的要求.

1.1 iDistance索引技術

iDistance是采用與參考點之間的距離將高維數據點向量轉換為一維數據表示的，為了做到這一點，該技術提供了非常靈活的空間劃分策略和參考點選取方法.

首先，該方法將數據空間劃分為N個聚類，同時確定每個聚類Ci的中心點c i（0≤i＜N）.對于每一個元素x∈D（這里D是［0，1］d空間，d是空間維度），則依據x與聚類中心點的距離為其指定一個一維的距離值，該距離值的計算如下：

其中函數d是歐幾里德距離；C是一個足夠大的數，能夠將屬于聚類Ci內的所有數據點都映射到區間［i＊C，（i＋1）＊C）上，同時保證各個區間之間不相交.

1.2 基于區位碼的向量壓縮方法

區位碼是利用與參考點的相對位置將多維數據空間劃分為2d′（d′＜d）個子分區，每個子分區利用一個位碼字符串來表示，這里，每個高維數據點都可以被近似地表示為所屬分區的位碼字符串，d是多維數據的維度，d′是位碼字符串的長度.

對于任意高維數據點P（p1，p2，…，p d），參考點是O（o1，o2，…，od），那么，P的位碼就可以表示為B P（，…），這里

1.3 基于Code－Distance的索引結構

如果利用iDistance索引方式，將使得不同的高維數據擁有相同的一維索引值，這種現象將隨著維度的增高越來越明顯，導致在查詢過程中產生大量的“誤中點”，從而增加了距離計算的次數，導致較低的檢索效率.因此，利用區位碼向量壓縮技術進行第2次過濾，將能有效地改善范圍檢索的性能.下面對這兩種索引方法進行如下擴展.

首先，假設P（p1，p2，…，p d）所屬聚類Ci的質心為Ci（ci1，ci2，…，cid），這里0≤i＜N.以點Ci為參考點，將聚類Ci在d′維上劃分為2d′個子分區，假設將點P的位碼表示為B P（，，…，），則利用Code－Distance表示的點P的索引值為

由于［0，1］d空間上最大的d（x，y）值（x，y∈D）為，常數C′可用于將位于不同分區的距離值區分開；由于Dec（BP）的最大值為2d′－1，這樣，常數C就可以將不同聚類內的Code－Distance索引值區分開.顯然，這里的一維索引值既包含了前面提到的區位碼的信息，又包含了距離的信息，具有基于近似向量的壓縮和高維向一維轉化兩種方法的優點.

2 BM－Chord網絡

在上面介紹的空間劃分策略基礎上，本章將詳細介紹基于該策略的BM－Chord網絡的建立及其范圍查詢過程.

2.1 基本思想

一般來講，在將高維數據映射到Chord節點上時，需要首先將高維數據映射到一維空間上.下面介紹利用Code－Distance技術，通過聚類、iDistance距離和區位碼，將高維數據空間映射到一維線性空間上的過程.

由于Chord是一種動態網絡，本文利用基于網格的聚類生成方法，來生成N個代表點，同時將每個代表點作為Voronoi圖［12］的“核子”，這樣，就可以將整個數據空間劃分為N個子空間（即聚類）.在Chord環中每個節點上都保存這N個代表點的全局信息，同時將節點上的高維數據對象分配到每個子空間中.

在上面操作的基礎上，利用位置保持哈希函數將所得到的Code－Distance索引值投影到［0，2m）區間上，同時，為每個網絡的每個節點分配一段連續的索引值空間，而且每個節點所負責的索引范圍不相交，整個節點所負責的索引范圍的總和就是整個索引空間.

BM－Chord網絡在邏輯上涵蓋了所有可直接尋址的節點，所有數據也存儲在這些節點上.由這些節點所組成的結構能夠比較容易地將數據元素插入到網絡中，節點間通過消息進行通信，利用范圍檢索來獲取所需的檢索數據.

2.2 節點的結構

BM－Chord網絡的邏輯拓撲完全符合Chord結構，利用位置保持哈希函數和式（3），就可以為每個數據點分配一個屬于BM－Chord范圍（即［0，2m）區間）的標識符.為了能夠在節點間對數據進行劃分，網絡中的任一個節點N i也需要分配一個屬于BM－Chord域的值K i.這樣，下述內容就組成了節點N i的數據結構：

（1）Chord網絡的路由信息K i、節點的前驅和后繼節點信息以及指針表；

（2）利用B＋樹結構存儲的（K i－1，K i］（mod 2m）區間的索引值；

（3）在節點上保存的全局的索引信息.

2.2.1 索引信息的構建 與Chord網絡相似，在BM－Chord網絡中，其索引信息也是采用分布式管理的.為了減少在檢索過程中的消息量，在每個節點上也都存儲著全局的索引信息，而高維數據的Code－Distance索引值將利用BM－Chord網絡中的每個節點進行分散管理.同時，采用主成分分析法來確定在哪些維度上需要進行區間劃分，以應對數據分布的不均勻性問題.

（1）全局索引的構建

以相同的參數為每個節點生成相同的代表點，并以這些代表點作為Voronoi圖的“核子”，每個節點利用這些代表點來構造一棵勢點樹（vantage point tree，VP－tree）［13］，以此作為全局索引.

在每個節點上設置全局索引主要是考慮如下兩種應用：

一是為節點分配索引值.當一個節點加入網絡時，此節點可以根據全局索引查詢到其上每個數據對象所在的單元格，也就是其所在的聚類，然后根據Code－Distance算法為每個數據對象分配索引值，并將其映射到Chord環中的對應節點上.

二是確定在進行相似查詢時需要訪問的代表點.在給定一個范圍查詢的情況下，通過檢索全局索引，查詢請求節點就可以確定哪些聚類與該相似查詢的搜索區域相交.也就是說，凡是與相似查詢的搜索區域相交的聚類都有可能包含所需要的結果，因此，檢索請求必須要訪問這些聚類，以獲取結果.而以代表點為搜索鍵，就可以將查詢請求路由給這些代表點所屬的節點，從而實現范圍檢索.

（2）局部索引的構建

將網絡中已被分配BM－Chord標識符的節點記為active，還沒有被分配標識符的節點記為inactive.

對于任一個數據x∈I（I為高維數據的集合），任一個節點Nins都可以發出插入請求，其基本過程如下：節點Nins利用式（3）計算CD（x）的值，如果Nins是inactive節點，就將請求轉發給它所了解的下一個節點；如果Nins是active節點，就遵照Chord網絡協議，將請求向前轉發給節點N CD（x），這里N CD（x）是管理CD（x）值的節點，由此節點根據CD（x）值將x插入到它所在的B＋樹中.

2.2.2 節點的加入及其退出處理過程 第一個加入網絡的節點將被分配一個索引值2m－1，該索引值涵蓋了整個BM－Chord域［0，2m），同時，這第一個入網的節點狀態被設置為active；除了第一個節點，其他的節點在開始時不被分配BMChord標識符，它們的狀態被設置為inactive.

假如存在一個處于inactive狀態的節點Nnew，則任何一個處于active的節點都可以對索引值發出分裂的請求.一般來講，網絡中的每個節點都可以確定自己的索引分裂準則，這些分裂準則的定義可以考慮存儲容量以及計算負載等因素.假如Ni節點發出分裂請求，同時（Ki－1，K i］為Ni節點所負責的索引值區間，則索引的分裂過程如下：

（1）以K i－1＜Knew＜K i為前提條件來生成索引值Knew，將所生成的Knew分配給節點Nnew；

（2）按照Chord網絡中的節點加入原則，Ni節點將位于（Ki－1，Knew］內的數據遷移到Nnew節點上.

顯然，如何選擇索引值Knew是一個需要考慮的重要問題，下面詳細介紹其選擇方法.

如果（K i－1，K i］覆蓋了z個分區，這里z＞1，則選擇Knew作為分區的邊界值，使 （K i－1，Knew］覆蓋個分區；如果（K i－1，Ki］只覆蓋了一個分區或一個分區的一部分，則選擇Knew＝（K i－1＋K i）／2，也就是將（K i－1，K i］進行平分.

假如有一個處于active狀態的節點離開了網絡，那么它將自動成為inactive節點，在此情況下，依據標準Chord網絡中的節點退出原則，退出節點上所保存的所有標識符范圍，將其轉移給其后繼節點進行管理.

2.3 候選數據的過濾機制以及范圍檢索算法

在給出過濾機制和檢索策略之前，先給出后續使用的相關定義.設I是D的高維數據索引的有限子集，高維數據的維度是d.給定高維數據點Q∈D以及查詢半徑r，范圍查詢Range（Q，r）搜索到的結果集合是S＝｛x∈I｜d（Q，x）≤r｝.2.3.1 數據過濾機制 對于給定范圍檢索請求Range（Q，r），則將與檢索范圍相交的聚類稱為候選數據類.由canCluster［14］可知，如果對由代表點Rep＝（C1，C2，…，CN）所構成的VP－tree按照下述準則進行查詢，則所求得的相交單元格，就是候選數據類集合.

準則1

（1）如果d（Q，R）≤r，則返回R（R為VP－tree最頂層的勢點）；

（2）如果d（Q，R）＋r≥M，遞歸查找右子樹；（3）如果d（Q，R）－r≤M，遞歸查找左子樹.根據上述準則，就可以得到候選數據類canCluster，根據canCluster中的每個聚類就能夠求出與查詢范圍相交的連續區間，該區間就組成了需要搜索的Code－Distance索引范圍的一部分.

僅僅獲得候選數據類還是不夠的，對于每個候選的Cj數據類，還需要求出與檢索范圍相交的候選分區，該候選分區的獲取過程如下.

準則2 對于所給定的范圍查詢請求Range（Q，r），其候選分區的計算過程如下：

假設點Q（q1，q2，…，qd）的區位碼為S（s1，s2，…，sd′），則候選數據類Cj內與該查詢范圍相交的分區T（t1，t2，…，td′）必滿足

接下來確定候選分區內需要搜索的索引值范圍.

對于范圍查詢Range（Q，r），若候選聚類Cj內分區T（t1，t2，…，td′）與該查詢范圍相交，則T內需要搜索的Code－Distance索引值范圍為

2.3.2 范圍檢索策略 在上述過濾機制的基礎上，下面給出完整的高維數據范圍檢索策略.

對于由任一節點A發起的范圍檢索請求Range（q，r），其檢索過程如下：

（1）首先，利用準則1來獲取候選數據類Ci（1≤i≤N），并根據準則2來獲取相交分區p j（0≤j≤（N－1）＊2d′－1），然后，根據上文Code－Distance索引值范圍來確定相交分區的檢索范圍Ij＝［hlow，hhigh］；

（2）j，0≤j≤（N－1）＊2d′－1，節點A發送消息SEARCHINTERVAL（Ij）給節點，其中N Ij＝N h（（hlow＋hhigh）／2），即為管理索引值

（3）節點A等待所有的回復信息，并依據所回復的IP從相關節點獲取高維數據對象，通過消冗處理后，生成最終的檢索結果集合SA，SA＝｛y｜d（y，Q）≤r，CD（y）∈Sl｝.

在節點上執行SEARCHINTERVAL（Ij）范圍檢索請求的處理過程如下：

①如果在節點上沒有保存完整的I j區間，則根據檢索范圍向其前驅節點或后繼節點發送范圍檢索請求SEARCHINTERVAL（Ij）；

② 確認保存在自己節點上的數據信息，并據此生成本地結果集Sl＝｛x｜CD（x）∈I j｝；

③將本地生成的結果集Sl返回給節點A，并通知節點A準備接收從其前驅節點或后繼節點返回的檢索結果.

3 模擬實驗與結果分析

本實驗是在Peersim開源環境下完成的，以確認BM－Chord網絡對高維數據范圍檢索的有效性.所采用的實驗數據包括兩種：一種是人工生成的模擬數據，另一種是真實數據.為了驗證本文策略的有效性，將本實驗與采用代表iDistance索引的M－Chord網絡進行比較.

3.1 中間結果集比較

所謂中間結果集，是指對于給定的范圍檢索，僅采用索引算法所能得到的查詢結果.顯然，在不降低查全率的前提下，中間結果集越小越好.

（1）中間結果集與原始數據集

將網絡節點個數設置為2 000，并分別利用10 000、20 000、30 000和40 000幅圖像的32維顏色直方圖數據進行實驗.設聚類數為30，范圍檢索參數為查詢中心點（0，0，…，0），查詢半徑r＝0.25.

由于M－Chord網絡是采用iDistance索引方法，在查詢過程中僅進行一次數據過濾；而BMChord網絡利用兩種索引技術的特點，在檢索過程中進行兩次數據過濾，這樣，在不降低查全率的前提下能有效減少中間結果集中的數據個數nint，其結果如圖1所示（圖中nori為原始數據集數據個數）.

圖1 中間結果集與原始數據集數據個數Fig.1 Size of intermediate result set and original data set

（2）中間結果集與維度

將網絡中的節點數設置為2 000，利用30 000幅32維圖像顏色直方圖數據和隨機生成的30 000個10、15、20和25維數據進行實驗，并設聚類個數為30.

由圖2可知，由于M－Chord網絡采用一次數據過濾方法，它比采用兩次過濾技術的BMChord網絡所產生的“誤中點”數據更多（圖中d為維度）.這說明本文BM－Chord網絡在不降低查全率的前提下，能有效減少檢索結果中的“誤中點”數據.

圖2 中間結果集數據個數與維度Fig.2 Size of intermediate result set and dimensionality

圖4 查全率與聚類數Fig.4 Recall ratio and number of clusters

3.2 查全率比較

（1）查全率與維度

網絡節點數設置為2 000，利用30 000幅32維圖像的顏色直方圖數據以及隨機生成的30 000個10、15、20和25維數據進行實驗，設聚類數為30.

由圖3知，M－Chord網絡和BM－Chord網絡的查全率r都很高，但M－Chord網絡對真實數據的查全率明顯降低，而BM－Chord網絡對于不同維度的數據其查全率變化不大.

圖3 查全率與維度Fig.3 Recall ratio and dimensionality

（2）查全率與聚類數

將網絡節點數設置為2 000，利用30 000幅32維圖像的顏色直方圖數據進行實驗，并分別將聚類數N設置為10、20、30、40和45.

從圖4可以看出，查全率受聚類數的影響較大，但在索引生成和范圍查詢過程中如何來選擇恰當的聚類數是一個很困難的問題.該問題將在以后的研究過程中進行重點研究.

4 結 語

本文結合一維轉換和近似向量兩種思想，提出了基于iDistance和區位碼索引的BM－Chord系統，實現了Chord環境下的高維數據范圍檢索.利用兩次過濾大大減少了中間結果數據個數，提高了查全率.如何減少消息轉發次數以降低網絡傳輸負載以及在保證查全率的前提下如何進一步減少“誤中點”的個數將是今后的研究重點.

［1］STOICA I，MORRIS R，KARGER D，etal.Chord：A scalable peer－to－peer lookup service for internet applications［C］／／Special Interest Group on Data Communication（ACM SIGCOMM）.San Diego：ACM，2001：149－160

［2］NOVAK D，ZEZULA P.M－Chord：A scalable distributed similarity search structure［C］／／First International Conference on Scalable Information Systems（INFOS－CALE 2006）.Hong Kong：ACM，2006：1－10

［3］JAGADISH H V，OOI B C，TAN K L，etal.iDistance：An adaptive B＋—tree based indexing method for nearest neighbor search［J］.ACM Transactions on Database Systems，2005，30（2）：364－397

［4］INDYK P，MOTWANI P R，RAGHAVAN P，etal.Locality－preserving hashing in multidimensional spaces［C］／／ACM Symposium on Theory of Computing.El Paso：ACM，1997：618－625

［5］梁俊杰，楊新澤，馮玉才.大規模高維向量空間的快速范圍查詢［J］.小型微型計算機系統，2007，28（7）：1225－1229

［6］徐林昊，周傲英.結構化對等計算系統中的高維相似搜索［J］.計算機學報，2006，29（11）：1982－1994

［7］SCHMIDT C，PARASHAR M.Flexible information discovery in decentralized distributed systems［C］／／The 12th IEEE International Symposium on High Performance Distributed Computing.Washington：IEEE Computer Society，2003：226－235

［8］GANESAN P，YANG B，GARCIA－MOLINA H.One torus to rule them all：multi－dimensional queries in P2P systems［C］／／The 7th International Workshop on the Web and Databases.New York：Stanford University，2004：19－24

［9］WEBER R，SCHEK H，BLOTT S.A quantitative analysis and performance study for similarity－search methods in high－dimensional spaces［C］／／The 24th International Conference on Very Large Data Bases.New York：Morgan Kanfmann，1998：194－205

［10］CUI B，SHEN H，SHEN J，etal.Exploring bitdifference for approximate KNN search in highdimensional databases［C］／／The 16th Australasian Database Conference.Australia：Australian Computer Society，2005

［11］梁俊杰，馮玉才.BC－iDistance：基于位碼的優化高維索引［J］.小型微型計算機系統，2007，28（11）：1647－1651

［12］AURENHAMMER F.Voronoi diagrams－A survey of a fundamental geometric data structure［J］.ACM Computing Survey，1991，23（3）：345－405

［13］YIANILOS P N.Data structures and algorithms for nearest neighbor search in general metric spaces［C］／／The 4th Annual ACM－SIAM Symposium on Discrete Algorithms（SODA′1993）.Philadelphia：Association for Computing Machinery，1993：311－321

［14］任曉娛.利用分區和距離實現Chord中高維數據范圍檢索［D］.大連：大連理工大學，2009