駱炎民,陳維斌,廖明宏

(1.華僑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,福建泉州 362021; 2.廈門(mén)大學(xué)信息科學(xué)與技術(shù)學(xué)院,福建廈門(mén) 361005; 3.廈門(mén)大學(xué)軟件學(xué)院,福建廈門(mén) 361005)

無(wú)索引空間數(shù)據(jù)庫(kù)的基于最優(yōu)點(diǎn)的集合最近鄰查找算法

駱炎民1,2,陳維斌1,廖明宏3

(1.華僑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,福建泉州 362021; 2.廈門(mén)大學(xué)信息科學(xué)與技術(shù)學(xué)院,福建廈門(mén) 361005; 3.廈門(mén)大學(xué)軟件學(xué)院,福建廈門(mén) 361005)

針對(duì)度量空間中的無(wú)索引空間數(shù)據(jù)庫(kù),提出一種基于最優(yōu)點(diǎn)的集合最近鄰查找算法及其改進(jìn)算法.采用真實(shí)數(shù)據(jù)集與人工生成的數(shù)據(jù)集對(duì)算法進(jìn)行測(cè)試,評(píng)估所提出算法的效率.實(shí)驗(yàn)結(jié)果表明,所提算法的效率優(yōu)于組最近鄰居查詢算法,并且對(duì)于高維數(shù)據(jù)空間,所提出的算法有較高的穩(wěn)定性.由于查詢區(qū)域中數(shù)據(jù)點(diǎn)的數(shù)量比較少,改進(jìn)的基于最優(yōu)點(diǎn)的集合最近鄰查找算法的效率總體上要比改進(jìn)前高.

空間數(shù)據(jù)庫(kù);最近鄰;集合最近鄰;查詢區(qū)域

集合最近鄰(Aggregate Nearest Neighbor,ANN)是由最近鄰(Nearest Neighbor,NN)演變而來(lái)的.它在許多研究領(lǐng)域中得到廣泛的應(yīng)用,如地理信息系統(tǒng)[1-2]、數(shù)據(jù)挖掘中的分類(lèi)[3]和異常點(diǎn)檢測(cè)[4]等.空間數(shù)據(jù)一般具有高維、海量等特性,如何高效地在空間數(shù)據(jù)庫(kù)中進(jìn)行各種最近鄰查詢,已經(jīng)成為空間數(shù)據(jù)庫(kù)及數(shù)據(jù)挖掘中的一個(gè)重要研究?jī)?nèi)容.目前,大多數(shù)的NN和ANN算法的主要思想是基于空間索引結(jié)構(gòu)的,通過(guò)對(duì)空間數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行裁剪,以提高查詢效率.在眾多的索引結(jié)構(gòu)中,R-樹(shù)[5-7]是最流行的一種.這些算法大部分在低維數(shù)據(jù)空間都能獲得理想的執(zhí)行結(jié)果和效率,而有研究表明,傳統(tǒng)的索引方法在高維數(shù)據(jù)空間中將失去效果.文獻(xiàn)[8]指出,在高維數(shù)據(jù)空間中,由于存在所謂的“維災(zāi)”的問(wèn)題,傳統(tǒng)的NN和ANN查詢可能會(huì)失去意義.在空間數(shù)據(jù)庫(kù)的最近鄰查找中,查找效率是一個(gè)關(guān)鍵問(wèn)題.因此,為了縮小查詢空間范圍,以減少查詢所需要的時(shí)間,人們引進(jìn)了各種各樣的空間索引機(jī)制.在空間數(shù)據(jù)庫(kù)中,數(shù)據(jù)集一般通過(guò)高維空間索引(Spatial Access M ethods,SAM)方法建立相關(guān)索引結(jié)構(gòu),如R-樹(shù)[9],R＊-樹(shù)[10]等.因此,大部分的最近鄰查詢算法都利用這些索引機(jī)制來(lái)實(shí)現(xiàn)高維數(shù)據(jù)空間中的最近鄰及k最近鄰查詢[11-13].此外,一些基于距離空間的索引結(jié)構(gòu),如 MB+-樹(shù)[14], GNA T[15]和MVP-樹(shù)[16]等也用于相似性查詢.本文提出了一種無(wú)索引的集合最近鄰查找算法,并以max函數(shù)為例討論ANN查找算法的實(shí)現(xiàn).

1 基本定義

一般情況下,空間數(shù)據(jù)庫(kù)中的數(shù)據(jù)是均勻分布的.在此前提下,設(shè)定f=sum,并以二維空間中的數(shù)據(jù)為例,分析算法的實(shí)現(xiàn)方法.算法很容易推廣到高維數(shù)據(jù)空間,在高維數(shù)據(jù)空間中也是適用的.

文中一些符號(hào)的含義如下:空間數(shù)據(jù)庫(kù)數(shù)據(jù)集P={p1,p2,…,pN};查詢數(shù)據(jù)集Q={q1,q2,…, qn};N,n分別為空間數(shù)據(jù)庫(kù)數(shù)據(jù)集和查詢數(shù)據(jù)集中數(shù)據(jù)對(duì)象的數(shù)量;M為最小邊界矩形的面積;d(p, q),D(p,q)=|pq|分別為數(shù)據(jù)對(duì)象p,q的距離函數(shù)和歐氏距離;集合距離函數(shù)adist(p,Q)=f(|pq1|,|pq2|,…,|pqn|),C(q,r)={p|p∈M,|pq|?r},S(p)≡S(p,Q)=∪C(qi,|pqi|).

由于空間數(shù)據(jù)的海量性,因此算法是在沒(méi)有空間數(shù)據(jù)索引的情況下,對(duì)空間數(shù)據(jù)進(jìn)行裁剪,獲取一個(gè)足夠小的查詢區(qū)域,然后在查詢區(qū)域中求解ANN.這樣可以裁剪掉查詢區(qū)域以外的數(shù)據(jù)對(duì)象,減少搜索空間,提高效率.如何獲得查詢區(qū)域是算法實(shí)現(xiàn)的關(guān)鍵.

首先引入算法中的兩個(gè)概念:r-近鄰域和數(shù)據(jù)集的最小邊界矩形(MBR).

定義1 給定一個(gè)查詢對(duì)象q∈O和一個(gè)非負(fù)半徑r,查詢對(duì)象q的r-近鄰域定義為包含在以q為圓心,r為半徑的空間數(shù)據(jù)點(diǎn)所組成的集合,如圖1所示.它可表示為

定義2 能夠包含查詢數(shù)據(jù)集Q中所有對(duì)象的最小矩形,稱(chēng)為查詢數(shù)據(jù)集的最小邊界矩形(MBR),如圖2所示.

由于空間數(shù)據(jù)庫(kù)中的對(duì)象是均勻分布的,因此在查詢數(shù)據(jù)集的MBR中總有空間數(shù)據(jù)庫(kù)中的對(duì)象存在.如圖2所示,查詢對(duì)于f=sum,在數(shù)據(jù)集P對(duì)于查詢點(diǎn)集合Q的集合最近鄰點(diǎn)將以極大的概率落在Q的MBR中.一般情況下,只需在Q的MBR中查詢其集合最近鄰點(diǎn),把Q的MBR以外的區(qū)域裁剪掉.這個(gè)區(qū)域稱(chēng)之為查詢區(qū)域.

如果一個(gè)查詢區(qū)域足夠小,并且又能保證ANN查詢結(jié)果一定落在該查詢區(qū)域內(nèi)時(shí),則稱(chēng)這個(gè)查詢區(qū)域是一個(gè)“滿意”的查詢區(qū)域.

2 基于最優(yōu)點(diǎn)的集合最近鄰查找算法

給定一個(gè)點(diǎn)p和半徑r,將數(shù)據(jù)空間分成兩部分,一部分是p點(diǎn)的r-近鄰區(qū)域,如圖1中的陰影部分;另一部分是p的r-近鄰區(qū)域以外的區(qū)域,稱(chēng)為p的r-近鄰?fù)鈪^(qū)域.如果半徑r足夠小,使得p的r-近鄰區(qū)域剛好能包含查詢數(shù)據(jù)集合Q中的所有對(duì)象{q1,q2,…,qn},即p是查詢數(shù)據(jù)集的最小外接圓的圓心,稱(chēng)這個(gè)p點(diǎn)為查詢集合的最優(yōu)點(diǎn),記為vp點(diǎn),如圖1所示.

對(duì)于f=sum,如果p是Q的集合最近鄰點(diǎn),則p使得adist(p,Q)=sum(|pq1|,|pq2|,…,|pqn|)的值最小.很顯然,如果r值合適的話,p一定落在vp的r-近鄰區(qū)域,而不可能落在vp的r-近鄰?fù)鈪^(qū)域,即adist(vp,Q)

圖1 vp點(diǎn)的r近鄰區(qū)域Fig.1 Examp le of the r-neighbor region of vp

圖2 查詢數(shù)據(jù)集Q的最小邊界矩形 Fig.2 M inimum boundary rectangle of query data set Q

圖3 r-近鄰區(qū)域的點(diǎn)集合最近鄰比較 Fig.3 Comparison of ANN between he point of r-neighbor and out-neighbor

在vp確定的前提下,尋找合適r的簡(jiǎn)便方法是,讓r=max(|vp qi|)(i=1,…,n).當(dāng)Q中存在某個(gè)對(duì)象距離vp點(diǎn)比較遠(yuǎn)時(shí),求出的查詢區(qū)域會(huì)很大,影響算法的效率.因此,可以采用另一種方法.由于Q的ANN點(diǎn)p使得adist(p,Q)=sum(|pq1|,|pq2|,…,|pqn|)的值最小,故對(duì)于每個(gè)qi,|pqi|的值應(yīng)盡可能小,由此可以斷定p一定落在每個(gè)qi的r-近鄰區(qū)域.根據(jù)定義可知,vp點(diǎn)的r-近鄰區(qū)域可以表示為C(vp,r)={p|p∈P,|p,vp|≤r}.對(duì)于查詢數(shù)據(jù)集Q中的每個(gè)對(duì)象qi,通過(guò)定理1可以求得vp_ ANN算法的查詢區(qū)域.

定理1 假設(shè)Ri=C(qi,ri)表示qi的r-近鄰區(qū)域,則R=Yi=1,…,n Ri是查詢數(shù)據(jù)集Q中各對(duì)象qi的ri-近鄰區(qū)域的并集.若所選取的每個(gè)ri的值能保證Ii=1,…,n Ri不是空集,則Q的集合最近鄰點(diǎn)一定落在R中.

根據(jù)定理1可知,最優(yōu)點(diǎn)的集合最近鄰查找算法的查詢區(qū)域就是R.要保證R不是空集,同時(shí)又要讓R所覆蓋的區(qū)域盡可能地小,必須合理地計(jì)算每個(gè)ri的值,而獲取合理各個(gè)ri值的關(guān)鍵是vp點(diǎn)的選擇.因此,vp點(diǎn)的選擇是算法的關(guān)鍵.

獲取vp點(diǎn)的最簡(jiǎn)單的方法是隨機(jī)生成一個(gè)vp點(diǎn),然后取ri=|vp qi|.但是這樣做的隨機(jī)性太大,有可能使R覆蓋幾乎整個(gè)數(shù)據(jù)空間,使算法失去意義.考慮到f=sum,合理的vp點(diǎn)應(yīng)該使得adist(vp, Q)=sum(|vp q1|,|vp q2|,…,|vp qn|)的值盡可能地小或者是最小,因此,最佳的vp點(diǎn)應(yīng)該是Q的質(zhì)心,P中距離該質(zhì)心最近的點(diǎn)就是Q的集合最近鄰.但是,對(duì)于不同的函數(shù)f,Q的質(zhì)心是不一樣的.

設(shè)(x,y)是Q的質(zhì)心q的坐標(biāo),(xi,yi)為Q中的查詢點(diǎn)qi的坐標(biāo),為使adist(p,Q)最小,必須滿足adist(p,Q)在q(x,y)上的偏導(dǎo)數(shù)為0[5].由此可以得出計(jì)算q(x,y)的公式,即

然而,上式在n>2的時(shí)候沒(méi)有一個(gè)固定形式的解,故利用上式也很難得到所需要的幾何中心.

為了降低計(jì)算復(fù)雜度及提高效率,在基于最優(yōu)點(diǎn)的集合最近鄰查找算法中使用幾何中心來(lái)代替質(zhì)心.Q的幾何中心q(x,y)的計(jì)算公式為

在低維數(shù)據(jù)空間中,選擇Q的幾何中心q作為vp點(diǎn),基本上能保證查詢區(qū)域R不是空集.但在高維數(shù)據(jù)空間中,由于數(shù)據(jù)點(diǎn)比較稀疏,相互之間的距離比較大,可能會(huì)導(dǎo)致R是空集,如圖4(a)所示.為了避免這種情況發(fā)生,算法取數(shù)據(jù)集P中距離Q的幾何中心最近的點(diǎn)作為vp點(diǎn)(圖4b中的p5),這樣就能保證R中至少有一個(gè)vp點(diǎn),避免了空集的情況,如圖4(b)所示.由于R是Q中各個(gè)對(duì)象qi的ri-近鄰區(qū)域的并,因此查詢區(qū)域R總是能包含Q的MBR,這樣能保證在空間數(shù)據(jù)均勻分布的情況下,Q的集合最近鄰點(diǎn)總能存在于查詢區(qū)域R中.

圖4 最優(yōu)點(diǎn)的集合最近鄰查找算法查詢區(qū)域示例Fig.4 Examples of search region by vantage point-bases region pruning algorithm of ANN

基于最優(yōu)點(diǎn)的集合最近鄰查找算法,主要有如下5個(gè)步驟:

(1)初始化R=Φ;

(2)按式(3)計(jì)算Q的幾何中心,可得到q;

(3)在空間數(shù)據(jù)庫(kù)P中查找q的最近鄰作為最優(yōu)點(diǎn)vp;

(4)查詢數(shù)據(jù)集Q中的每個(gè)點(diǎn)qi,再分別計(jì)算ri=|qi vp|,Ri=C(qi,ri),并更新R=R∪Ri;

(5)在查詢區(qū)域R中搜索集合最近鄰點(diǎn),并返回結(jié)果.

3 基于最優(yōu)點(diǎn)的集合最近鄰查找的改進(jìn)算法

由于空間數(shù)據(jù)庫(kù)P中的對(duì)象數(shù)量要遠(yuǎn)遠(yuǎn)大于查詢點(diǎn)集合Q中對(duì)象的數(shù)量,即N?n.因此在一般情況下,Q中數(shù)據(jù)點(diǎn)的分布比較集中,基于最優(yōu)點(diǎn)的集合最近鄰查找算法找出的查詢區(qū)域也會(huì)比較小,算法的效率比較高.但是,當(dāng)Q中數(shù)據(jù)點(diǎn)的分布比較分散時(shí),對(duì)算法效率的影響就比較大.為了提高算法效率,需要對(duì)基于最優(yōu)點(diǎn)的集合最近鄰查找算法進(jìn)行改進(jìn),以進(jìn)一步縮小查詢區(qū)域,擴(kuò)大裁剪區(qū)域.

當(dāng)空間數(shù)據(jù)庫(kù)中的對(duì)象是均勻分布的,對(duì)于f=sum,數(shù)據(jù)集P對(duì)于查詢點(diǎn)集合Q的集合最近鄰點(diǎn)將以極大的概率落在Q的MBR中.顯然,在基于最優(yōu)點(diǎn)的集合最近鄰查找算法中找出來(lái)的查詢區(qū)域(圖4(c)中的點(diǎn)狀陰影區(qū)域),不僅一定要覆蓋查詢點(diǎn)集合Q的MBR(圖4(c)中的虛線矩形框區(qū)域),而且要比Q的MBR區(qū)域大得多.因此,當(dāng)Q中的數(shù)據(jù)對(duì)象分布比較分散的情況下,可以選取Q的MBR區(qū)域作為查詢區(qū)域.

但是,當(dāng)Q中的數(shù)據(jù)對(duì)象分布比較集中時(shí),有可能存在Q的MBR區(qū)域中沒(méi)有包含空間數(shù)據(jù)庫(kù)P中的對(duì)象.此時(shí),如果以Q的MBR作為查詢區(qū)域,會(huì)導(dǎo)致查詢區(qū)域的數(shù)據(jù)對(duì)象為空集,如圖4(c)所示.即p5是Q的集合最近鄰點(diǎn),但它卻落在Q的MBR外.因此,將查詢區(qū)域擴(kuò)大為Q的MBR的最小外接圓,如圖4(c)所示的矩形陰影背景區(qū)域,該區(qū)域就包含了p5.當(dāng)然,如果Q中的數(shù)據(jù)對(duì)象分布非常集中,以至于其MBR的最小外接圓中也沒(méi)有包含空間數(shù)據(jù)庫(kù)P中的對(duì)象時(shí),可以對(duì)外接圓的半徑再進(jìn)行適當(dāng)?shù)姆糯?讓它足夠包含有適當(dāng)?shù)腜中的數(shù)據(jù)點(diǎn).

在算法的實(shí)現(xiàn)中,查詢數(shù)據(jù)集合Q的最小外接圓的圓心仍然使用Q的幾何中心.設(shè)qi(xi,yi)(i= 1,…,n)為Q中的點(diǎn),令min_x=m in_xi,m in_y=m in_yi,max_x=max_xi,max_y=max_yi,i=1,…, n,且(xi,yi)∈Q,則查詢數(shù)據(jù)集合Q的最小外接圓的半徑rmin的計(jì)算公式為

改進(jìn)的基于最優(yōu)點(diǎn)的集合最近鄰查找算法,有如下7個(gè)主要步驟:

(1)初始化R=Φ;

(2)按式(3)計(jì)算Q的幾何中心,可得到q;

(3)在空間數(shù)據(jù)庫(kù)P中查找q的最近鄰作為最優(yōu)點(diǎn)vp;

(4)求Q的數(shù)據(jù)集的最小邊界矩形(MBR),即m in_x=min_xi,min_y=min_yi,max_x=max_xi,max_y=max_yi;

(5)計(jì)算Q的MBR的最小外接圓,圓心為q,按式(4)計(jì)算半徑rmin;

(6)R=C(q,rmin),當(dāng)vp點(diǎn)不在R中時(shí),按增量比例d放大rmin,即rmin=rmin×d,d>1,更新R;

(7)最后,在查詢區(qū)域R中搜索集合最近鄰點(diǎn),并返回結(jié)果.

4 算法的分析與實(shí)驗(yàn)結(jié)果

在算法的時(shí)間復(fù)雜度方面,求Q的幾何中心的時(shí)間復(fù)雜度為O(n),其中n為Q中包含的點(diǎn)的數(shù)量;求Q的幾何中心在P中的最近鄰的時(shí)間復(fù)雜度為O(N),其中N為P中包含的點(diǎn)的數(shù)量;求最小包圍矩形MBR的左上頂點(diǎn)和右下頂點(diǎn)的時(shí)間復(fù)雜度為O(n+1);計(jì)算MBR的圓心和半徑的時(shí)間復(fù)雜度都為O(1);對(duì)集合P的裁剪的時(shí)間復(fù)雜度為O(N);在裁剪區(qū)域R中求AN N的結(jié)果的時(shí)間復(fù)雜度最大不會(huì)超過(guò)O(N).由于集合P中所包含的數(shù)據(jù)點(diǎn)一般遠(yuǎn)遠(yuǎn)大于Q的中的點(diǎn),即N?n,故最優(yōu)點(diǎn)的集合最近鄰查找算法及其改進(jìn)算法的時(shí)間復(fù)雜度都近似為O(N).

實(shí)驗(yàn)環(huán)境:Linux操作系統(tǒng),Inter(R),Pentium(R),4 CPU,2.66 GHz處理器,512 MB內(nèi)存;采用C++進(jìn)行編程.實(shí)驗(yàn)數(shù)據(jù)采用空間數(shù)據(jù)集P和查詢數(shù)據(jù)集Q,數(shù)據(jù)集中的數(shù)據(jù)都經(jīng)過(guò)規(guī)范化到(0,1]區(qū)間內(nèi).實(shí)驗(yàn)中,空間數(shù)據(jù)集P和查詢數(shù)據(jù)集Q都駐留在內(nèi)存,實(shí)驗(yàn)結(jié)果數(shù)據(jù)取50次查詢的平均值.數(shù)據(jù)來(lái)源:(1)美國(guó)西部地區(qū)一些公共地名數(shù)據(jù)集WUpppoint,包含有10 493個(gè)數(shù)據(jù)點(diǎn),即它們是一些二維坐標(biāo)點(diǎn),數(shù)據(jù)可從www.rtreeportal.org下載獲得;(2)人工隨機(jī)生成的高維數(shù)據(jù),這些數(shù)據(jù)在數(shù)據(jù)空間中是均勻分布的.

對(duì)不同的n,M及數(shù)據(jù)空間的維數(shù)(D)參數(shù)進(jìn)行分析比較,結(jié)果如圖5所示.圖5中:k為查詢區(qū)域中數(shù)據(jù)點(diǎn)的數(shù)量,t為CPU執(zhí)行時(shí)間.從圖5可知,基于最優(yōu)點(diǎn)的集合最近鄰算法查詢區(qū)域中的數(shù)據(jù)點(diǎn)的數(shù)量總是比其改進(jìn)的算法要多,而且隨著M和n的增加,查詢區(qū)域數(shù)據(jù)點(diǎn)的差別就更大.但是,隨著空間數(shù)據(jù)維數(shù)的增加,差別越小.這是因?yàn)榛谧顑?yōu)點(diǎn)的ANN的查詢區(qū)域,總是覆蓋且大于其改進(jìn)算法的查詢區(qū)域,隨著維數(shù)的增加,數(shù)據(jù)空間中的數(shù)據(jù)分布比較稀疏.所以,它們包含的點(diǎn)數(shù)的差別就越小.

實(shí)驗(yàn)結(jié)果表明,所提算法的效率要優(yōu)于組最近鄰居查詢算法(M ultip le Query M ethod,MQM),且對(duì)于不同的M,n和數(shù)據(jù)維數(shù)D,特別是對(duì)于高維數(shù)據(jù)空間,算法有比較高的穩(wěn)定性.由于查詢區(qū)域中數(shù)據(jù)點(diǎn)的數(shù)量比較少,因此,改進(jìn)的ANN算法的效率總體要比基于最優(yōu)點(diǎn)的ANN算法要高一點(diǎn).

圖5 不同的查詢數(shù)據(jù)集的算法比較Fig.5 Comparison on the different data set

5 結(jié)束語(yǔ)

提出一種無(wú)索引的,基于最優(yōu)點(diǎn)集合的最近鄰查找算法及其改進(jìn)的算法.將算法與其他查詢方法進(jìn)行比較,分析算法的基本特性.結(jié)果表明:所提出的算法最大的特點(diǎn)在于不采用任何索引的情況下,也能高效地對(duì)空間數(shù)據(jù)庫(kù)中的數(shù)據(jù)對(duì)象進(jìn)行裁剪,縮小查詢區(qū)域、提高集合最近鄰查詢的效率.在下一步,將繼續(xù)研究其他函數(shù)的集合最近鄰算法,并且將算法擴(kuò)展到向量空間中.

[1]YIU Man-lung,MAMOUL IS N,PAPAD IAS D.Aggregate nearest neighbor queries in road netwo rks[J].IEEE Trans Know l Data Eng,2005,17(6):820-833.

[2]JENSEN C S,KOLáRVR J,PEDERSEN T B,et al.Nearest neighbor queries in road networks[C]∥Proc of the 11th ACM International Symposium on Advances in Geographic Info rmation System s.New Yo rk:ACM,2003:1-8.

[3]JA IN A K,M.MURTY N M,FL YNN PJ.Data clustering:A review[J].ACM Comput Surv,1999,31(3):264-323.

[4]AGGARWAL CC,YU PS.Outlier detection for high dimensional data[C]∥Proc of the 2001 ACM SIGMOD International Conference on Management of Data.New Yo rk:ACM,2001:37-46.

[5]PAPAD IASD,TAO Yu-fei,MOURA TID IA K,et al:Aggregate nearest neighbor queries in spatial databases[J]. ACM Trans on Database Syst,2005,30(2):529-576.

[6]PAPAD IASD,SHEN Qiong-mao,TAO Yu-fei,et al.Group nearest neighbor queries[C]∥Proc of the 20th International Conference on Data Engineering.Washington D C:IEEEComputer Society,2004:301-312.

[7]L IHong-ga,LU Hua,HUANGBo,et al.Two ellipse-based pruning methods for group nearest neighbor queries [C]∥Proc of the 13th Aannual ACM International Wo rkshop on Geographic Information Systems.Washington D C:IEEEComputer Society,2005:192-199.

[8]BEYER K,GOLDSTEIN J,RAMAKRISHNAN R,et al.When is“nearest neighbors”meaningful?[C]∥Proc of the 7th International Conference on Database Theo ry.London:Sp ringer-Verlag,1999:217-235.

[9]GU TTMAN A.R-trees:A dynamic index structure for spatial searching[C]∥Proc of the 1984 ACM SIGMOD International Conference on Management of Data.San Francisco:Morgan Kaufmann Publishers Inc,1984:47-57.

[10]BECKMANN N,KRIEGEL H P,SCHNEIDER R,et al.The R＊-tree:An efficient and robust access method for points and rectangles[C]∥Proc of the 1990 ACM SIGMOD International Conference on Management of Data.New York:ACM,1990:322-331.

[11]PAPADOPOULOS A,MANOLOPOULOS Y.Perfo rmance of nearest neighbor queries in R-trees[C]∥Proc of the 6th International Conference on Database Theory.London:Sp ringer-Verlag,1997:394-408.

[12]UHLMANN J K.Satisfying general proximity/similary queries with metric trees[J].Information Processing Letters,1991,40(4):175-179.

[13]ROUSSOPOULOSN,KELLEY S,V INCENT F.Nearest neighbor queries[C]∥Proc of the 1995 ACM SIGMOD International Conference on Management of Data.New Yo rk:ACM,1995:71-79.

[14]ISH IKAWA M,CHEN Han-xiong,FURUSE K,et al.MB+tree:A dynamically updatablemetric index for similarity searches[C]∥Web-Age Info rmation Management.Berlin:Sp ringer,2000:356-373.

[15]BRIN S.Near neighbor search in largemetric spaces[C]∥Proc of the 21th International Conference on Very Large Data Bases.San Francisco:Morgan Kaufmann Publishers Inc,1995:574-584.

[16]BOZKAYA T,OZSOYOGLU M.Distance-based indexing for high-dimensional metric spaces[C]∥Proc of the 1997 ACM SIGMOD Conference on Management of Data.New Yo rk:ACM,1997:357-368.

(責(zé)任編輯:陳志賢英文審校:蔡燦輝)

An Algorithm of Aggregate Nearest Neighbor Query for Non-Index Spatial Database

Luo Yan-min1,2,CHEN Wei-bin1,L IAO M in-hong3
(1.College of Computer Science and Technology,Huaqiao University,Quanzhou 362021,China; 2.School of Information Science and Technology,Xiamen University,Xiamen 361005,China; 3.School of Software,Xiamen University,Xiamen 361005,China)

The vantage point-based aggregate nearest neighbor query algorithm and it′s imp roved algorithm are proposed for non-index spatial database in metric space.The algorithms are tested by using both real datasets and synthetic datasets to evaluate efficiencies of the proposed algorithms.The experimental results show that the efficiencies of proposed algorithmsare better than thatofmultiple querymethod.Furthermore,the proposed algorithms have higher stabilization in high-dimensional data space.Since there are less data points in it′s search region,efficiency of the imp roved vantage point-based aggregate nearest neighbor query algorithm is generally higher than the vantage point-based aggregate nearest neighbor query algo rithm.

spatial database;nearest neighbor;aggregate nearest neighbor;search region

TP 311.131;TP 301.6

A

1000-5013(2011)02-0169-06

2009-08-10

駱炎民(1974-),男,副教授,主要從事圖形圖像與人工智能的研究.E-mail:lym@hqu.edu.cn.

福建省自然科學(xué)基金資助項(xiàng)目(2009J01288)