有障礙物環(huán)境下移動對象的反最近鄰查詢

張學(xué)芹

摘要：最近鄰查詢是地理信息系統(tǒng)領(lǐng)域常遇到的問題，為反向最近鄰查詢是在最近鄰查詢的基礎(chǔ)上提出的一種新的查詢類型。在分析了幾種反向最近鄰查詢的類型和方法的基礎(chǔ)上，提出了基于Voronoi圖的解決障礙物環(huán)境下移動對象的反向最近鄰查詢的方法，大大縮小了在海量空間數(shù)據(jù)庫中進行反向最近鄰查詢的查詢范圍，并提高了查詢的準確度。

關(guān)鍵詞：Voronoi圖；障礙物； 移動對象； 反向最近鄰

中圖分類號：TP3 文獻標識碼：A 文章編號：1009-3044（2014）33-7996-03

Abstract：Nearest neighbor query is very common in geographic information system，and based on it，reverse nearest neighbor query is proposed. On the basis of analyzing several types and methods of reverse nearest neighbor query，method of reverse nearest neighbors queries for moving query point with barriers is proposed. It greatly reduces the query range and improves the accuracy in the massive spatial database.

Key words： Voronoi Diagrams， Barriers， Moving object， Reverse nearest neighbor

1 概述

反向最近鄰查詢是在最近鄰查詢的基礎(chǔ)上提出的一種新的查詢類型，它被廣泛引用于GIS，移動計算和圖像處理等領(lǐng)域，如何及時回答時空移動對象發(fā)出的動態(tài)反向最近鄰查詢請求成為了新的研究熱點和難點。目前已有的幾種解決非移動對象的反向最近鄰方法主要利用R樹及其改進樹建立索引結(jié)構(gòu)進行處理。但對移動對象的反向最近鄰查詢研就較少。所謂移動對象的最近鄰查詢就是在查詢對象為移動點q或點集Q，而被查詢對象集P是靜止狀態(tài)下，查找P集中q或Q作為最近鄰的點集。移動對象的最近鄰查詢具有重要意義，在實施定位，搶險營救等實際應(yīng)用中發(fā)揮著很大作用。國內(nèi)較新的解決移動對象的RNN查詢問題的方法主要有兩種：一種是基于TPR樹的半平面修剪法；另一種是將時空距離函數(shù)和平面六分區(qū)域相結(jié)合的RNN判定法。在障礙物環(huán)境下，文獻[1] 討論的問題是最近鄰查詢，而非反向最近鄰查詢。文獻[2] 研究的是基于R樹的靜態(tài)反向k最近鄰的查詢方法，而不是用來解決移動點的RNN查詢問題。為了處理有障礙物環(huán)境下移動點的RNN查詢問題，本文基于Voronoi圖的概念和性質(zhì)，給出相關(guān)的查詢策略和算法，該方法在定性分析之下，認為是可行的，并有效的。

2 相關(guān)定義及定理

6 結(jié)論

本文利用Voronoi圖的幾何性質(zhì)及其在解決反向最近鄰中獲得的相關(guān)推論解決了在障礙物環(huán)境下移動點的反向最近鄰查詢問題。此方法能有效縮小查找范圍。更重要的是提出了查詢的準確范圍，避免遺漏反向最近鄰點。如何能夠提高實時查詢的效率，成為本文算法改進的方向。

參考文獻：

[1] 李林，張麗平，李松.障礙物環(huán)境中的路網(wǎng)最近鄰查詢方法[J].鐵路計算機應(yīng)用，2009（11）.

[2] Yunjun Gao BZGC.Visible Reverse k-Nearest Neighbor Queries[J].IEEE International Conference on Data Engineering.

[3] Korn F.Muthukrishnan S.Influence sets based on reverse nearest neighbor queries[C]//Chen Wei-dong，Naughton J F，Bernstein P A.Proc of the 2000 ACM SIGMOD Intl Conf on Management of Data，Dallas，Texas，USA，2000.New York，NY，USA：ACM Press，2000：201-212.

[4] 李松，郝忠孝.基于Voronoi圖的反向最近鄰查詢方法研究[J].哈爾濱工程大學(xué)學(xué)報，2008（3）.