计算机工程与设计
計算機工程與設計
계산궤공정여설계
COMPUTER ENGINEERING AND DESIGN
2014年
7期
2395-2401
,共7页
路网%移动性%连续反向k近邻(RkNN)%安全区%PMR四叉树
路網%移動性%連續反嚮k近鄰(RkNN)%安全區%PMR四扠樹
로망%이동성%련속반향k근린(RkNN)%안전구%PMR사차수
road network%mobility%continuous reverse nearest k neighbors (RkNN)%safe region%PMR quad-tree
现存的反向k近邻查询方案中，比较高效地研究大多集中在欧式空间，对于路网中的反向k近邻查询的研究相对较少。针对这一问题，考虑路网中移动查询点和移动数据对象的移动性，选用PMR四叉树来索引路网，基于安全区的概念提出一种反向k近邻（RkNN）查询算法，通过监控查询点和移动对象的安全区来处理路网更新。基于“初始化-维护更新”框架，采用Dij kstra搜索策略，设置验证监控区域来判定候选对象解的真假性。为了减少网络搜寻的工作量，提出了一系列剪枝规则来削减搜索空间。实验结果表明，该算法适用于路网中k值不固定的连续RkNN查询。
現存的反嚮k近鄰查詢方案中，比較高效地研究大多集中在歐式空間，對于路網中的反嚮k近鄰查詢的研究相對較少。針對這一問題，攷慮路網中移動查詢點和移動數據對象的移動性，選用PMR四扠樹來索引路網，基于安全區的概唸提齣一種反嚮k近鄰（RkNN）查詢算法，通過鑑控查詢點和移動對象的安全區來處理路網更新。基于“初始化-維護更新”框架，採用Dij kstra搜索策略，設置驗證鑑控區域來判定候選對象解的真假性。為瞭減少網絡搜尋的工作量，提齣瞭一繫列剪枝規則來削減搜索空間。實驗結果錶明，該算法適用于路網中k值不固定的連續RkNN查詢。
현존적반향k근린사순방안중，비교고효지연구대다집중재구식공간，대우로망중적반향k근린사순적연구상대교소。침대저일문제，고필로망중이동사순점화이동수거대상적이동성，선용PMR사차수래색인로망，기우안전구적개념제출일충반향k근린（RkNN）사순산법，통과감공사순점화이동대상적안전구래처리로망경신。기우“초시화-유호경신”광가，채용Dij kstra수색책략，설치험증감공구역래판정후선대상해적진가성。위료감소망락수심적공작량，제출료일계렬전지규칙래삭감수색공간。실험결과표명，해산법괄용우로망중k치불고정적련속RkNN사순。
In the field of reverse k nearest neighbor query,many efficient algorithms had been proposed in Euclidean spaces while only a few algorithms on road network.Based on the mobility of the moving query points and the moving obj ects in road net-work,the PMR quad-tree was chosen to build the road network and a novel algorithm was proposed for reverse nearest k neigh-bors (RkNN)query by adopting the concept of the safe region which was used to monitor the update.The algorithm based on the framework of“initial computing-continuous monitoring”adopted the strategy of Dij kstra and verified the candidate obj ects by checking the verifying-regions.To simplify the monitoring,a series of pruning rules were presented.The results of the experi-ment showed that the algorithm was scalable in processing continuous RkNN query in road network for which the value of k was not fixed.
