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

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

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

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