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

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

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

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

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