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

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

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

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