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

1、隨著空間數(shù)據(jù)庫(kù)在實(shí)際應(yīng)用領(lǐng)域的廣泛發(fā)展，空間查詢中的最近鄰查詢及其變體查詢研究成為熱點(diǎn)問(wèn)題。已有的最近鄰查詢已經(jīng)不能滿足廣泛的應(yīng)用需求，為此最近鄰查詢研究的數(shù)據(jù)環(huán)境從理想的歐氏空間轉(zhuǎn)變到復(fù)雜的障礙空間，數(shù)據(jù)對(duì)象也從點(diǎn)對(duì)象轉(zhuǎn)變?yōu)榫€段對(duì)象。作為一類重要的空間數(shù)據(jù)查詢，反k最近鄰查詢有著重要的研究?jī)r(jià)值。由于現(xiàn)有研究并沒有涉及障礙空間中的組反k最近鄰查詢問(wèn)題以及針對(duì)線段對(duì)象的反k最近鄰查詢問(wèn)題，故本文研究的重點(diǎn)是利用Voronoi圖的鄰接特性對(duì)

2、障礙組反k最近鄰查詢及線段反k最近鄰查詢進(jìn)行系統(tǒng)的研究。
　　本研究主要內(nèi)容包括：⑴為了解決已有研究成果不能有效處理障礙空間中的組反k最近鄰查詢問(wèn)題，根據(jù)障礙物集合是否發(fā)生變化提出了兩種情況下的查詢方法，一種是靜態(tài)障礙物環(huán)境下的查詢（簡(jiǎn)稱STA_OGRkNN查詢），另一種是動(dòng)態(tài)障礙物環(huán)境下的查詢（簡(jiǎn)稱DYN_OGRkNN查詢）。其中STA_OGRkNN查詢方法利用剪枝策略可以在剪枝階段快速地縮小查詢范圍，提高整個(gè)算法的查詢效率，在

3、精煉階段又有效地提高了算法的準(zhǔn)確性，進(jìn)一步給出了3種情況下的DYN_OGRkNN查詢算法。⑵針對(duì)現(xiàn)有的基于點(diǎn)對(duì)象的反k最近鄰查詢研究存在的局限性，提，出了基于線段的反k最近鄰查詢方法。該方法獲得的結(jié)果集是將查詢線段作為k最近鄰的線段集合。查詢過(guò)程分別為剪枝過(guò)程和精煉過(guò)程，首先利用5個(gè)剪枝策略篩選出候選者，再根據(jù)定義得到精確的結(jié)果集，該方法通過(guò)剪枝可以大大提高查詢速度，通過(guò)對(duì)候選者進(jìn)行精煉又提高了算法的準(zhǔn)確度。⑶將線段反k最近鄰查詢應(yīng)用到