孟憲福， 孟泓汐， 張振強(qiáng)

（1.大連理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，遼寧大連116024；2.大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院，遼寧大連116026）

0 引 言

隨著P2P技術(shù)的發(fā)展，P2P網(wǎng)絡(luò)已經(jīng)在多個(gè)領(lǐng)域得到實(shí)際應(yīng)用，比如資源共享等，而在P2P環(huán)境下進(jìn)行范圍檢索已成為用戶的迫切需要.

Chord是由環(huán)形組成的結(jié)構(gòu)化P2P網(wǎng)絡(luò)，它所具有的良好的數(shù)據(jù)檢索效率、容錯(cuò)性和自適應(yīng)性等，使其已成為具有高可擴(kuò)展性和高效率的實(shí)用結(jié)構(gòu)化P2P模型［1］.但由于Chord是基于DHT（distributed hash table）的，并不能有效地支持范圍檢索等相似性檢索.

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

文獻(xiàn)［6］采用了基于代表點(diǎn)空間劃分策略的一種Chord網(wǎng)絡(luò)結(jié)構(gòu)，該結(jié)構(gòu)利用事先確定的代表點(diǎn)將整個(gè)數(shù)據(jù)空間劃分為數(shù)個(gè)子空間，每個(gè)代表點(diǎn)僅對(duì)應(yīng)一個(gè)子空間，在此基礎(chǔ)上，將代表點(diǎn)映射到一維區(qū)間上，并將代表點(diǎn)的一維索引標(biāo)識(shí)作為Chord網(wǎng)絡(luò)中節(jié)點(diǎn)的哈希值.由于是基于準(zhǔn)隨機(jī)序列的均勻分布特性來選取代表點(diǎn)的，對(duì)于那些不均勻的數(shù)據(jù)集，在進(jìn)行范圍檢索時(shí)會(huì)產(chǎn)生大量的“誤中點(diǎn)”，影響了檢索效率.

文獻(xiàn)［7］利用Hilbert曲線將高維數(shù)據(jù)映射到Chord環(huán)上，文獻(xiàn)［8］則給出了以空間填充曲線為基礎(chǔ)的范圍劃分方法，這幾種方法都能在Chord網(wǎng)絡(luò)上實(shí)現(xiàn)高維數(shù)據(jù)的范圍檢索.但是，這些方法對(duì)低維度數(shù)據(jù)可行，對(duì)高維度數(shù)據(jù)會(huì)出現(xiàn)“維度災(zāi)難”問題，不能很好地適應(yīng)數(shù)據(jù)維度的增長(zhǎng).

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

基于區(qū)位碼的優(yōu)化高維索引結(jié)構(gòu)［11］不僅利用iDistance距離來表示對(duì)象點(diǎn)和參考點(diǎn)之間的遠(yuǎn)近關(guān)系，同時(shí)利用區(qū)位碼來近似表示它們之間的位置關(guān)系，以便將多維向量壓縮為二維向量.

本文在Chord網(wǎng)絡(luò)協(xié)議和已有的高維數(shù)據(jù)索引算法的基礎(chǔ)上，提出BM－Chord網(wǎng)絡(luò)結(jié)構(gòu)，以解決高維數(shù)據(jù)的范圍檢索問題.BM－Chord網(wǎng)絡(luò)結(jié)構(gòu)采用iDistance和區(qū)位碼向量壓縮兩種技術(shù)將高維數(shù)據(jù)降為一維，然后利用位置保持哈希函數(shù)將一維索引值映射到Chord網(wǎng)絡(luò)環(huán)上，環(huán)上的每個(gè)節(jié)點(diǎn)利用B＋樹結(jié)構(gòu)來保存數(shù)據(jù)索引值.在此基礎(chǔ)上，利用本文提出的檢索算法和過濾技術(shù)，實(shí)現(xiàn)基于Chord網(wǎng)絡(luò)的多維數(shù)據(jù)的范圍檢索.

1 空間的劃分策略

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

1.1 iDistance索引技術(shù)

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

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

其中函數(shù)d是歐幾里德距離；C是一個(gè)足夠大的數(shù)，能夠?qū)儆诰垲怌i內(nèi)的所有數(shù)據(jù)點(diǎn)都映射到區(qū)間［i＊C，（i＋1）＊C）上，同時(shí)保證各個(gè)區(qū)間之間不相交.

1.2 基于區(qū)位碼的向量壓縮方法

區(qū)位碼是利用與參考點(diǎn)的相對(duì)位置將多維數(shù)據(jù)空間劃分為2d′（d′＜d）個(gè)子分區(qū)，每個(gè)子分區(qū)利用一個(gè)位碼字符串來表示，這里，每個(gè)高維數(shù)據(jù)點(diǎn)都可以被近似地表示為所屬分區(qū)的位碼字符串，d是多維數(shù)據(jù)的維度，d′是位碼字符串的長(zhǎng)度.

對(duì)于任意高維數(shù)據(jù)點(diǎn)P（p1，p2，…，p d），參考點(diǎn)是O（o1，o2，…，od），那么，P的位碼就可以表示為B P（，…），這里

1.3 基于Code－Distance的索引結(jié)構(gòu)

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

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

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

2 BM－Chord網(wǎng)絡(luò)

在上面介紹的空間劃分策略基礎(chǔ)上，本章將詳細(xì)介紹基于該策略的BM－Chord網(wǎng)絡(luò)的建立及其范圍查詢過程.

2.1 基本思想

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

由于Chord是一種動(dòng)態(tài)網(wǎng)絡(luò)，本文利用基于網(wǎng)格的聚類生成方法，來生成N個(gè)代表點(diǎn)，同時(shí)將每個(gè)代表點(diǎn)作為Voronoi圖［12］的“核子”，這樣，就可以將整個(gè)數(shù)據(jù)空間劃分為N個(gè)子空間（即聚類）.在Chord環(huán)中每個(gè)節(jié)點(diǎn)上都保存這N個(gè)代表點(diǎn)的全局信息，同時(shí)將節(jié)點(diǎn)上的高維數(shù)據(jù)對(duì)象分配到每個(gè)子空間中.

在上面操作的基礎(chǔ)上，利用位置保持哈希函數(shù)將所得到的Code－Distance索引值投影到［0，2m）區(qū)間上，同時(shí)，為每個(gè)網(wǎng)絡(luò)的每個(gè)節(jié)點(diǎn)分配一段連續(xù)的索引值空間，而且每個(gè)節(jié)點(diǎn)所負(fù)責(zé)的索引范圍不相交，整個(gè)節(jié)點(diǎn)所負(fù)責(zé)的索引范圍的總和就是整個(gè)索引空間.

BM－Chord網(wǎng)絡(luò)在邏輯上涵蓋了所有可直接尋址的節(jié)點(diǎn)，所有數(shù)據(jù)也存儲(chǔ)在這些節(jié)點(diǎn)上.由這些節(jié)點(diǎn)所組成的結(jié)構(gòu)能夠比較容易地將數(shù)據(jù)元素插入到網(wǎng)絡(luò)中，節(jié)點(diǎn)間通過消息進(jìn)行通信，利用范圍檢索來獲取所需的檢索數(shù)據(jù).

2.2 節(jié)點(diǎn)的結(jié)構(gòu)

BM－Chord網(wǎng)絡(luò)的邏輯拓?fù)渫耆螩hord結(jié)構(gòu)，利用位置保持哈希函數(shù)和式（3），就可以為每個(gè)數(shù)據(jù)點(diǎn)分配一個(gè)屬于BM－Chord范圍（即［0，2m）區(qū)間）的標(biāo)識(shí)符.為了能夠在節(jié)點(diǎn)間對(duì)數(shù)據(jù)進(jìn)行劃分，網(wǎng)絡(luò)中的任一個(gè)節(jié)點(diǎn)N i也需要分配一個(gè)屬于BM－Chord域的值K i.這樣，下述內(nèi)容就組成了節(jié)點(diǎn)N i的數(shù)據(jù)結(jié)構(gòu)：

（1）Chord網(wǎng)絡(luò)的路由信息K i、節(jié)點(diǎn)的前驅(qū)和后繼節(jié)點(diǎn)信息以及指針表；

（2）利用B＋樹結(jié)構(gòu)存儲(chǔ)的（K i－1，K i］（mod 2m）區(qū)間的索引值；

（3）在節(jié)點(diǎn)上保存的全局的索引信息.

2.2.1 索引信息的構(gòu)建 與Chord網(wǎng)絡(luò)相似，在BM－Chord網(wǎng)絡(luò)中，其索引信息也是采用分布式管理的.為了減少在檢索過程中的消息量，在每個(gè)節(jié)點(diǎn)上也都存儲(chǔ)著全局的索引信息，而高維數(shù)據(jù)的Code－Distance索引值將利用BM－Chord網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)進(jìn)行分散管理.同時(shí)，采用主成分分析法來確定在哪些維度上需要進(jìn)行區(qū)間劃分，以應(yīng)對(duì)數(shù)據(jù)分布的不均勻性問題.

（1）全局索引的構(gòu)建

以相同的參數(shù)為每個(gè)節(jié)點(diǎn)生成相同的代表點(diǎn)，并以這些代表點(diǎn)作為Voronoi圖的“核子”，每個(gè)節(jié)點(diǎn)利用這些代表點(diǎn)來構(gòu)造一棵勢(shì)點(diǎn)樹（vantage point tree，VP－tree）［13］，以此作為全局索引.

在每個(gè)節(jié)點(diǎn)上設(shè)置全局索引主要是考慮如下兩種應(yīng)用：

一是為節(jié)點(diǎn)分配索引值.當(dāng)一個(gè)節(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí)，此節(jié)點(diǎn)可以根據(jù)全局索引查詢到其上每個(gè)數(shù)據(jù)對(duì)象所在的單元格，也就是其所在的聚類，然后根據(jù)Code－Distance算法為每個(gè)數(shù)據(jù)對(duì)象分配索引值，并將其映射到Chord環(huán)中的對(duì)應(yīng)節(jié)點(diǎn)上.

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

（2）局部索引的構(gòu)建

將網(wǎng)絡(luò)中已被分配BM－Chord標(biāo)識(shí)符的節(jié)點(diǎn)記為active，還沒有被分配標(biāo)識(shí)符的節(jié)點(diǎn)記為inactive.

對(duì)于任一個(gè)數(shù)據(jù)x∈I（I為高維數(shù)據(jù)的集合），任一個(gè)節(jié)點(diǎn)Nins都可以發(fā)出插入請(qǐng)求，其基本過程如下：節(jié)點(diǎn)Nins利用式（3）計(jì)算CD（x）的值，如果Nins是inactive節(jié)點(diǎn)，就將請(qǐng)求轉(zhuǎn)發(fā)給它所了解的下一個(gè)節(jié)點(diǎn)；如果Nins是active節(jié)點(diǎn)，就遵照Chord網(wǎng)絡(luò)協(xié)議，將請(qǐng)求向前轉(zhuǎn)發(fā)給節(jié)點(diǎn)N CD（x），這里N CD（x）是管理CD（x）值的節(jié)點(diǎn)，由此節(jié)點(diǎn)根據(jù)CD（x）值將x插入到它所在的B＋樹中.

2.2.2 節(jié)點(diǎn)的加入及其退出處理過程 第一個(gè)加入網(wǎng)絡(luò)的節(jié)點(diǎn)將被分配一個(gè)索引值2m－1，該索引值涵蓋了整個(gè)BM－Chord域［0，2m），同時(shí)，這第一個(gè)入網(wǎng)的節(jié)點(diǎn)狀態(tài)被設(shè)置為active；除了第一個(gè)節(jié)點(diǎn)，其他的節(jié)點(diǎn)在開始時(shí)不被分配BMChord標(biāo)識(shí)符，它們的狀態(tài)被設(shè)置為inactive.

假如存在一個(gè)處于inactive狀態(tài)的節(jié)點(diǎn)Nnew，則任何一個(gè)處于active的節(jié)點(diǎn)都可以對(duì)索引值發(fā)出分裂的請(qǐng)求.一般來講，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都可以確定自己的索引分裂準(zhǔn)則，這些分裂準(zhǔn)則的定義可以考慮存儲(chǔ)容量以及計(jì)算負(fù)載等因素.假如Ni節(jié)點(diǎn)發(fā)出分裂請(qǐng)求，同時(shí)（Ki－1，K i］為Ni節(jié)點(diǎn)所負(fù)責(zé)的索引值區(qū)間，則索引的分裂過程如下：

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

（2）按照Chord網(wǎng)絡(luò)中的節(jié)點(diǎn)加入原則，Ni節(jié)點(diǎn)將位于（Ki－1，Knew］內(nèi)的數(shù)據(jù)遷移到Nnew節(jié)點(diǎn)上.

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

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

假如有一個(gè)處于active狀態(tài)的節(jié)點(diǎn)離開了網(wǎng)絡(luò)，那么它將自動(dòng)成為inactive節(jié)點(diǎn)，在此情況下，依據(jù)標(biāo)準(zhǔn)Chord網(wǎng)絡(luò)中的節(jié)點(diǎn)退出原則，退出節(jié)點(diǎn)上所保存的所有標(biāo)識(shí)符范圍，將其轉(zhuǎn)移給其后繼節(jié)點(diǎn)進(jìn)行管理.

2.3 候選數(shù)據(jù)的過濾機(jī)制以及范圍檢索算法

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

準(zhǔn)則1

（1）如果d（Q，R）≤r，則返回R（R為VP－tree最頂層的勢(shì)點(diǎn)）；

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

僅僅獲得候選數(shù)據(jù)類還是不夠的，對(duì)于每個(gè)候選的Cj數(shù)據(jù)類，還需要求出與檢索范圍相交的候選分區(qū)，該候選分區(qū)的獲取過程如下.

準(zhǔn)則2 對(duì)于所給定的范圍查詢請(qǐng)求Range（Q，r），其候選分區(qū)的計(jì)算過程如下：

假設(shè)點(diǎn)Q（q1，q2，…，qd）的區(qū)位碼為S（s1，s2，…，sd′），則候選數(shù)據(jù)類Cj內(nèi)與該查詢范圍相交的分區(qū)T（t1，t2，…，td′）必滿足

接下來確定候選分區(qū)內(nèi)需要搜索的索引值范圍.

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

2.3.2 范圍檢索策略 在上述過濾機(jī)制的基礎(chǔ)上，下面給出完整的高維數(shù)據(jù)范圍檢索策略.

對(duì)于由任一節(jié)點(diǎn)A發(fā)起的范圍檢索請(qǐng)求Range（q，r），其檢索過程如下：

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

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

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

在節(jié)點(diǎn)上執(zhí)行SEARCHINTERVAL（Ij）范圍檢索請(qǐng)求的處理過程如下：

①如果在節(jié)點(diǎn)上沒有保存完整的I j區(qū)間，則根據(jù)檢索范圍向其前驅(qū)節(jié)點(diǎn)或后繼節(jié)點(diǎn)發(fā)送范圍檢索請(qǐng)求SEARCHINTERVAL（Ij）；

② 確認(rèn)保存在自己節(jié)點(diǎn)上的數(shù)據(jù)信息，并據(jù)此生成本地結(jié)果集Sl＝｛x｜CD（x）∈I j｝；

③將本地生成的結(jié)果集Sl返回給節(jié)點(diǎn)A，并通知節(jié)點(diǎn)A準(zhǔn)備接收從其前驅(qū)節(jié)點(diǎn)或后繼節(jié)點(diǎn)返回的檢索結(jié)果.

3 模擬實(shí)驗(yàn)與結(jié)果分析

本實(shí)驗(yàn)是在Peersim開源環(huán)境下完成的，以確認(rèn)BM－Chord網(wǎng)絡(luò)對(duì)高維數(shù)據(jù)范圍檢索的有效性.所采用的實(shí)驗(yàn)數(shù)據(jù)包括兩種：一種是人工生成的模擬數(shù)據(jù)，另一種是真實(shí)數(shù)據(jù).為了驗(yàn)證本文策略的有效性，將本實(shí)驗(yàn)與采用代表iDistance索引的M－Chord網(wǎng)絡(luò)進(jìn)行比較.

3.1 中間結(jié)果集比較

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

（1）中間結(jié)果集與原始數(shù)據(jù)集

將網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)設(shè)置為2 000，并分別利用10 000、20 000、30 000和40 000幅圖像的32維顏色直方圖數(shù)據(jù)進(jìn)行實(shí)驗(yàn).設(shè)聚類數(shù)為30，范圍檢索參數(shù)為查詢中心點(diǎn)（0，0，…，0），查詢半徑r＝0.25.

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

圖1 中間結(jié)果集與原始數(shù)據(jù)集數(shù)據(jù)個(gè)數(shù)Fig.1 Size of intermediate result set and original data set

（2）中間結(jié)果集與維度

將網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)設(shè)置為2 000，利用30 000幅32維圖像顏色直方圖數(shù)據(jù)和隨機(jī)生成的30 000個(gè)10、15、20和25維數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，并設(shè)聚類個(gè)數(shù)為30.

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

圖2 中間結(jié)果集數(shù)據(jù)個(gè)數(shù)與維度Fig.2 Size of intermediate result set and dimensionality

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

3.2 查全率比較

（1）查全率與維度

網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)設(shè)置為2 000，利用30 000幅32維圖像的顏色直方圖數(shù)據(jù)以及隨機(jī)生成的30 000個(gè)10、15、20和25維數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，設(shè)聚類數(shù)為30.

由圖3知，M－Chord網(wǎng)絡(luò)和BM－Chord網(wǎng)絡(luò)的查全率r都很高，但M－Chord網(wǎng)絡(luò)對(duì)真實(shí)數(shù)據(jù)的查全率明顯降低，而BM－Chord網(wǎng)絡(luò)對(duì)于不同維度的數(shù)據(jù)其查全率變化不大.

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

（2）查全率與聚類數(shù)

將網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)設(shè)置為2 000，利用30 000幅32維圖像的顏色直方圖數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，并分別將聚類數(shù)N設(shè)置為10、20、30、40和45.

從圖4可以看出，查全率受聚類數(shù)的影響較大，但在索引生成和范圍查詢過程中如何來選擇恰當(dāng)?shù)木垲悢?shù)是一個(gè)很困難的問題.該問題將在以后的研究過程中進(jìn)行重點(diǎn)研究.

4 結(jié) 語(yǔ)

本文結(jié)合一維轉(zhuǎn)換和近似向量?jī)煞N思想，提出了基于iDistance和區(qū)位碼索引的BM－Chord系統(tǒng)，實(shí)現(xiàn)了Chord環(huán)境下的高維數(shù)據(jù)范圍檢索.利用兩次過濾大大減少了中間結(jié)果數(shù)據(jù)個(gè)數(shù)，提高了查全率.如何減少消息轉(zhuǎn)發(fā)次數(shù)以降低網(wǎng)絡(luò)傳輸負(fù)載以及在保證查全率的前提下如何進(jìn)一步減少“誤中點(diǎn)”的個(gè)數(shù)將是今后的研究重點(diǎn).

［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］梁俊杰，楊新澤，馮玉才.大規(guī)模高維向量空間的快速范圍查詢［J］.小型微型計(jì)算機(jī)系統(tǒng)，2007，28（7）：1225－1229

［6］徐林昊，周傲英.結(jié)構(gòu)化對(duì)等計(jì)算系統(tǒng)中的高維相似搜索［J］.計(jì)算機(jī)學(xué)報(bào)，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：基于位碼的優(yōu)化高維索引［J］.小型微型計(jì)算機(jī)系統(tǒng)，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］任曉?shī)?利用分區(qū)和距離實(shí)現(xiàn)Chord中高維數(shù)據(jù)范圍檢索［D］.大連：大連理工大學(xué)，2009