首页 | 本学科首页   官方微博 | 高级检索  
     

道路网中基于RRN-Tree的CKNN查询
引用本文:孙海龙,王霓虹.道路网中基于RRN-Tree的CKNN查询[J].计算机工程,2014(6):306-311.
作者姓名:孙海龙  王霓虹
作者单位:东北林业大学信息与计算机工程学院,哈尔滨150040
基金项目:中央高校基本科研业务费专项基金资助项目(DL12AB02);国家“863”计划基金资助项目(2012AA102003-2);国家林业局公益性行业科研专项基金资助项目(201104037).
摘    要:现有针对基于道路网络的CKNN查询研究,主要是将道路网络以路段和节点的形式进行建模,转化成基于内存的有向/无向图,该模型存在2个问题:一个是道路网络中路段数据量大,导致索引结构分支过多、移动对象更新频繁;另一个是图表示方法不能很好地处理十字路口转向、U型转弯等交通规则。针对此问题,提出道路网中基于RRN-Tree的移动对象CKNN查询算法,包括索引结构设计和移动对象查询算法设计,采用路线对道路网建模,基于网络边扩展方式,实现复杂条件下的道路网络CKNN查询。实验结果表明,在各种网络密度和兴趣点对象分布密度下,与经典的IMA/GMA算法相比,基于RRN-Tree索引方法的查询性能提高1.5倍~2.13倍。

关 键 词:道路网络  连续K最近邻查询  RRN树  扩展网络边  K近邻监测区  兴趣点分布密度

CKNN Query Based on RRN-Tree in Road Network
SUN Hai-long,WANG Ni-hong.CKNN Query Based on RRN-Tree in Road Network[J].Computer Engineering,2014(6):306-311.
Authors:SUN Hai-long  WANG Ni-hong
Affiliation:(College of Information and Computer Engineering, Northeast Forestry University, Harbin ! 50040, China)
Abstract:Most of existing methods for Continuous K Nearest Neighbors(CKNN) query of moving objects in road networks model the road networks as road segments and nodes, and convert them into directional graph or undirectional graph in memory. There are two problems with this model. First, the number of road segments is so huge that there are too many branches in index structure and frequent update of moving objects. Second, traffic regulations like the crossroads turn and U turn cannot be processed in graph model. This paper proposes a CKNN query algorithm of moving objects based on RRN-Tree in road networks, which includes the design of index structure and query algorithm for moving objects, models road network as routes, and implements CKNN query in road networks under complicated road conditions by expanding the road edges. Experimental results show that the method based on RRN-Tree has better query performance than classical IMA/GMA algorithm under various network density and objects distribution density, and the performance is increased by 1.5-2.13 times.
Keywords:road network  Continuous K Nearest Neighbors(CKNN) query  RRN-Tree  expand network edge  K Nearest Neighbors (KNN) monitor area  distribution density of interest point
本文献已被 CNKI 维普 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号