基于Voronoi圖的空間數(shù)據(jù)k-最近鄰查詢技術(shù)的研究.pdf

1、空間數(shù)據(jù)查詢方法是在空間數(shù)據(jù)庫、空間數(shù)據(jù)挖掘、空間拓?fù)潢P(guān)系分析、智能交通和地理信息系統(tǒng)等領(lǐng)域扮演著非常重要的角色。最近鄰查詢方法作為空間數(shù)據(jù)查詢中的一個(gè)分支，在日常生活中同樣扮演著極其重要的角色。最近鄰查詢方法可以從數(shù)據(jù)環(huán)境上被劃分為以下兩類：第一類是基于歐氏空間的查詢，歐氏空間又可以分為有障礙環(huán)境查詢與無障礙環(huán)境查詢；另一類是基于路網(wǎng)環(huán)境(道路網(wǎng)絡(luò))上的查詢。在日常生活中主要的最近鄰查詢都是在有障礙的環(huán)境下或者是路網(wǎng)環(huán)境下進(jìn)行的。Vo

2、ronoi圖是一種關(guān)于空間劃分的基本數(shù)據(jù)結(jié)構(gòu)。它在解決空間查詢方面有很大的潛力，不僅可以應(yīng)用在地理信息系統(tǒng)和在線地圖領(lǐng)域，而且還可以應(yīng)用到其他的一些領(lǐng)域。所以本文研究的重點(diǎn)是將Voronoi圖應(yīng)用于障礙環(huán)境下的最近鄰查詢與路網(wǎng)環(huán)境下的最近鄰查詢及其變體查詢，主要研究內(nèi)容包括以下幾個(gè)方面：
　　首先，從傳統(tǒng)的障礙空間下的k-最近鄰查詢?nèi)胧郑治隽藗鹘y(tǒng)方法的不足，提出了障礙空間中基于Voronoi圖的k-最近鄰查詢方法。首先是利用Vo

3、ronoi圖的過濾功能，較大程度地減少了被查詢點(diǎn)個(gè)數(shù)。然后根據(jù)障礙距離和鄰接生成點(diǎn)對(duì)候選集中的對(duì)象進(jìn)行第二次篩選，最后通過計(jì)算候選集合中的點(diǎn)得到最終的結(jié)果。
　　其次，針對(duì)已有的在路網(wǎng)中的反向最近鄰查詢方法存在的不足，提出了利用網(wǎng)格Voronoi圖的算法，該算法具有較好的效果。該算法是把路網(wǎng)劃分成小的網(wǎng)格Voronoi圖區(qū)域，然后利用網(wǎng)格Voronoi圖的過濾功能過濾掉一些不可能成為最終結(jié)果的點(diǎn)。最后從可能的結(jié)果集合中找到最終的查