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

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

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

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