障礙空間數(shù)據(jù)庫(kù)的反k近鄰查詢技術(shù)的研究.pdf

1、近年來，隨著基于位置的服務(wù)(LBS)和物聯(lián)網(wǎng)的快速發(fā)展，空間查詢技術(shù)作為重要的支撐技術(shù)進(jìn)而越來越重要，而空間查詢中的最近鄰查詢及其各種變體有著廣泛的應(yīng)用，如范圍查詢、k近鄰查詢、skyline查詢、反k近鄰查詢等。在這些查詢中，反k近鄰查詢用來獲取那些k最近鄰里包含查詢q的空間數(shù)據(jù)點(diǎn)，在空間決策支持、資源分配和數(shù)據(jù)挖掘方面有著廣泛的應(yīng)用。近幾年已有較多對(duì)于查詢前k個(gè)反最近鄰對(duì)象的研究，其中大部分針對(duì)的都是理想歐式空間和路網(wǎng)空間。而在真實(shí)

2、情況下，反k最近鄰查詢通常受到障礙物的影響，例如建筑物、湖泊等。
　　針對(duì)上面提出的問題，本文對(duì)障礙空間內(nèi)的反近鄰查詢技術(shù)進(jìn)行了研究。
　　首先，針對(duì)障礙空間中障礙物的不可見性和查詢點(diǎn)的快照性及固定性，本文形式化定義了在障礙空間中的反k最近鄰固定點(diǎn)查詢，并針對(duì)此問題提出了一種基于障礙Voronoi圖的高效的剪枝方法。實(shí)驗(yàn)驗(yàn)證了本文所提出的ORkNN算法在高效性和準(zhǔn)確性上的優(yōu)越性。
　　其次，本文針對(duì)查詢點(diǎn)為用戶動(dòng)態(tài)給定

3、的情況下，對(duì)上面提出的問題進(jìn)行改進(jìn)，定義了障礙空間中的反k近鄰動(dòng)態(tài)點(diǎn)查詢問題，由此提出了ORkNND算法，即使用網(wǎng)格索引及有效剪枝方法將動(dòng)態(tài)給出的查詢點(diǎn)定位，然后在定位后的查詢點(diǎn)處局部構(gòu)造新的障礙Voronoi圖單元，最后使用上面提出的固定點(diǎn)查詢算法的剪枝和更新策略進(jìn)行障礙反k近鄰查詢。大量實(shí)驗(yàn)證明了該算法的有效性和高效性。
　　最后，本文考慮到用戶發(fā)出查詢時(shí)的移動(dòng)連續(xù)性，針對(duì)上面研究查詢點(diǎn)的問題，這里提出了將查詢點(diǎn)增至查詢線段上

4、的障礙空間的連續(xù)反k近鄰查詢問題。本文研究了查詢點(diǎn)變成線段后，解決求控制點(diǎn)和分割點(diǎn)的問題，然后對(duì)結(jié)果集進(jìn)行更新。實(shí)驗(yàn)評(píng)估了本文所提出的CORkNN算法的有效性和準(zhǔn)確性。
　　總之，本文從越來越接近實(shí)際應(yīng)用的障礙空間中的反k近鄰查詢的典型特征和挑戰(zhàn)出發(fā)，針對(duì)障礙空間中的反k近鄰的關(guān)鍵技術(shù)展開研究，如基于障礙Voronoi圖、網(wǎng)格的數(shù)據(jù)結(jié)構(gòu)進(jìn)行點(diǎn)查詢技術(shù)，預(yù)處理技術(shù)、控制點(diǎn)和分割點(diǎn)劃分技術(shù)等，從而提供高效健壯的障礙空間中反k近鄰查詢處