[發(fā)明專(zhuān)利]一種在空間網(wǎng)絡(luò)數(shù)據(jù)庫(kù)中查找最近k個(gè)點(diǎn)對(duì)的廣度優(yōu)先方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201010175152.7
• 申請(qǐng)日: 2010-05-13
• 公開(kāi)（公告）號(hào): CN101840434A
• 公開(kāi)（公告）日: 2010-09-22
• 發(fā)明（設(shè)計(jì)）人: 孫未未;陳楚南;劉未末;荊一楠;何震瀛
• 申請(qǐng)（專(zhuān)利權(quán)）人: 復(fù)旦大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 上海正旦專(zhuān)利代理有限公司 31200
• 代理人: 陸飛;盛志范

技術(shù)領(lǐng)域

本發(fā)明屬于空間數(shù)據(jù)庫(kù)技術(shù)領(lǐng)域，具體涉及一種在空間網(wǎng)絡(luò)數(shù)據(jù)庫(kù)中查找最近k個(gè)點(diǎn)對(duì)的廣度優(yōu)先方法。

背景技術(shù)

近年來(lái)，隨著無(wú)線通訊技術(shù)、地理信息系統(tǒng)特別是定位技術(shù)的發(fā)展，以及計(jì)算機(jī)信息處理能力的提高，空間數(shù)據(jù)庫(kù)在現(xiàn)實(shí)中得到了很好的應(yīng)用，成為了當(dāng)今的研究熱點(diǎn)之一，其發(fā)展前景被廣泛看好。

在空間數(shù)據(jù)庫(kù)中，數(shù)據(jù)的存儲(chǔ)是基于存儲(chǔ)對(duì)象的空間地理位置信息而進(jìn)行組織的，所進(jìn)行的查詢(xún)也是與查詢(xún)對(duì)象的空間地理位置信息有關(guān)的空間查詢(xún)。作為空間數(shù)據(jù)庫(kù)中最常見(jiàn)的空間查詢(xún)之一，最近k個(gè)點(diǎn)對(duì)查詢(xún)是，對(duì)輸入兩個(gè)數(shù)據(jù)集合S和T，S的每個(gè)元素與T的每個(gè)元素構(gòu)成點(diǎn)對(duì)，計(jì)算這些點(diǎn)對(duì)的距離，選取最小的k個(gè)返回。

在現(xiàn)有的最近k個(gè)點(diǎn)對(duì)的查詢(xún)方法中，大多數(shù)方法都是針對(duì)歐氏幾何空間環(huán)境下的空間數(shù)據(jù)庫(kù)而提出的。在歐氏幾何空間環(huán)境下，點(diǎn)與點(diǎn)之間的距離是直線距離，而在空間網(wǎng)絡(luò)環(huán)境下，點(diǎn)與點(diǎn)之間的距離是由兩點(diǎn)在網(wǎng)絡(luò)中的最短路徑距離決定的，因此針對(duì)歐氏幾何空間環(huán)境下的查詢(xún)方法無(wú)法直接應(yīng)用到空間網(wǎng)絡(luò)環(huán)境下。在空間網(wǎng)絡(luò)環(huán)境下，現(xiàn)有的最近k個(gè)點(diǎn)對(duì)查找方法是以深度優(yōu)先方法進(jìn)行查找的，由于該方法在查找過(guò)程中會(huì)找出很多冗余的點(diǎn)對(duì)，因此對(duì)空間網(wǎng)絡(luò)的頂點(diǎn)和邊的訪問(wèn)量很大，導(dǎo)致查找速度很慢。因此亟需要對(duì)此方法進(jìn)行改進(jìn)，以提高查找速度。

發(fā)明內(nèi)容

本發(fā)明的目的是針對(duì)空間網(wǎng)絡(luò)數(shù)據(jù)庫(kù)中最近k個(gè)點(diǎn)對(duì)的問(wèn)題，提出一種廣度優(yōu)先的方法，以提高查找速度。

本發(fā)明提出的查找方法，通過(guò)以廣度優(yōu)先的查找順序，既保證了最終查找的點(diǎn)對(duì)是最近的k個(gè)，又減少了查找過(guò)程中對(duì)空間網(wǎng)絡(luò)的頂點(diǎn)和邊的訪問(wèn)次數(shù)，加快了查找速度。

首先對(duì)一些基本概念進(jìn)行定義：

定義1.網(wǎng)絡(luò)(G)：表示頂點(diǎn)(vertex)之間鄰接關(guān)系的拓?fù)浣Y(jié)構(gòu)，由頂點(diǎn)集合(V)以及頂點(diǎn)之間的邊的集合(E)構(gòu)成。

定義2.兩點(diǎn)間距離(distance)：兩點(diǎn)之間最短路徑的長(zhǎng)度。

定義3.最近鄰居(NN)：對(duì)輸入的查詢(xún)點(diǎn)(或中心點(diǎn))q和查詢(xún)目標(biāo)集合S＝{S1，S2，…，Sn}，在S中找出與q之間距離最小的頂點(diǎn)Si，Si即為q的最近鄰居(q.NN)。

定義4.點(diǎn)對(duì)及點(diǎn)對(duì)距離：對(duì)頂點(diǎn)集合S和T，S中的頂點(diǎn)Si與T中的頂點(diǎn)Tj構(gòu)成點(diǎn)對(duì)(Si，Tj)，Si與Tj之間的距離為點(diǎn)對(duì)(Si，Tj)的距離。

定義5.最近k個(gè)點(diǎn)對(duì)：對(duì)頂點(diǎn)集合S和T，在所有點(diǎn)對(duì)中取距離最小的k個(gè)，稱(chēng)這k個(gè)點(diǎn)對(duì)為S和T的最近k個(gè)點(diǎn)對(duì)。

定義6.集合大小|S|：集合S所包含元素的個(gè)數(shù)。

根據(jù)以上定義，對(duì)于輸入的頂點(diǎn)集合S和T，S＝{S1，S2，…，Sm}，T＝{T1，T2，…，Tn}，本發(fā)明提出的最近k個(gè)點(diǎn)對(duì)查找方法是基于以下性質(zhì)的：

(1)以T為查詢(xún)目標(biāo)集合，假設(shè)已經(jīng)找到了S中的每個(gè)頂點(diǎn)Si的第一個(gè)最近鄰居Si.1NN，這m個(gè)由中心點(diǎn)Si和Si.1NN構(gòu)成點(diǎn)對(duì)(Si，Si.1NN)，i＝1，2，…，m，在這m個(gè)點(diǎn)對(duì)中，設(shè)距離最小的點(diǎn)對(duì)為(Sj，Sj.1NN)，則(Sj，Sj.1NN)一定是S和T的第一個(gè)最近點(diǎn)對(duì)。

(2)假設(shè)當(dāng)前已找出第i個(gè)最近點(diǎn)對(duì)(Sx，Sx.tNN)，其中，i＝2、3、…、k-1，Sx.tNN表示Sx的第t個(gè)最近鄰居，則查找Sx的第t+1個(gè)最近鄰居，構(gòu)成新的點(diǎn)對(duì)，那么找出的所有點(diǎn)對(duì)中距離第i+1小的點(diǎn)對(duì)一定是S和T的第i+1個(gè)最近點(diǎn)對(duì)。

基于以上性質(zhì)，本發(fā)明方法以廣度優(yōu)先的順序查找兩個(gè)集合的最近k個(gè)點(diǎn)對(duì)，具體步驟是：

(1)對(duì)于輸入的頂點(diǎn)集合S和T，設(shè)m＝|S?|，n＝|T|，S＝{S1，S2，…，Sm}，T＝{T1，T2，…，Tn}，不失一般性，假設(shè)m＜n。

(2)以T為查詢(xún)目標(biāo)集合，查找S中的每個(gè)頂點(diǎn)Si的第1個(gè)最近鄰居Si.1NN，這m個(gè)由中心點(diǎn)Si和Si.1NN構(gòu)成點(diǎn)對(duì)(Si，Si.1NN)，i＝1，2，…，m，在這m個(gè)點(diǎn)對(duì)中取距離最小的點(diǎn)對(duì)，設(shè)為(p1，q1)，p1∈S，q1∈T，則(p1，q1)為S和T的第一個(gè)最近點(diǎn)對(duì)。

(3)對(duì)(2)中求出的第1個(gè)最近點(diǎn)對(duì)的中心點(diǎn)p1，查找p1的第2個(gè)最近鄰居p1.2NN，p1與p1.2NN構(gòu)成第m+1個(gè)點(diǎn)對(duì)(Sj，Sj.2NN)，在(2)、(3)中求出的m+1個(gè)點(diǎn)對(duì)中取距離第2小的，設(shè)為(p2，q2)，則(p2，q2)是S和T的第二個(gè)最近點(diǎn)對(duì)。

(4)對(duì)已求出的S和T的第t(0＜t＜k)個(gè)最近點(diǎn)，對(duì)重復(fù)步驟(3)，計(jì)算下一個(gè)最近點(diǎn)對(duì)，直至t＝k為止。