道路网络中移动对象索引研究.pdf

Computer Engineering and Applications 计算机工程与应用 2010 ，46 （22 ） 157 道路网络中移动对象的索引研究 1，2 1，3 2 宋广军 ，郝忠孝 ，王丽杰 SONG Guang-jun1，2 ，HAO Zhong-xiao1，3 ，WANG Li-jie2 1.哈尔滨理工大学 计算机与控制学院，哈尔滨 150080 2.齐齐哈尔大学 计算机与控制工程学院，黑龙江 齐齐哈尔 161006 3.哈尔滨工业大学 计算机科学与技术学院，哈尔滨 150001 1.College of Computer and Control ，Harbin University of Science and Technology ，Harbin 150080，China 2.College of Computer and Control Engineering ，Qiqihar University ，Qiqihar ，Heilongjiang 161006，China 3.College of Computer Science and Technology ，Harbin Institute of Technology ，Harbin 150001，China E-mail ：song_gj@ 126.com SONG Guang-jun ，HAO Zhong-xiao ，WANG Li-jie.Research on indexing of moving objects in road networks.Computer Engineering and Applications ，2010 ，46 （22 ）：157-161. Abstract ：This paper proposes a new index structure to efficiently store and retrieve the past ，present and future positions of moving objects in networks ，L2R-Tree.The index structure consistes of two-level 2D R-tree and a linklist.The two-level R-trees are used to index polyline and objects ’movements along the polylines.The present positions and future prediction tra- jectories of moving objects are stored in linklist.L 2R-Tree can not only support the trajectories query of moving objects in road networks but also is especially easy to query all the moving objects in the same route by lengthways list.Moreover ， point query and range query are implemented based on this index structure.Finally ，experimental studies indicate that the L2R-tree index outperformed TPR-tree in index creation as well as in querying. Key words ：moving object databases ；range query ；L2R-Tree 摘 要：为了能有效地实现网络中移动对象的过去、当前和将来轨迹的查询，提出了一种L2R 索引，它由两层R 树和一个链表结 构组成。两层R 树用以索引道路网络和移动对象过去的运动，对象当前的位置和将来的预测轨迹信息保存在链表中。L2R 索引 不仅可以支持网络中的移动对象的轨迹查询，尤其是可方便的在纵向链表中查询在同条路线上的所有对象。在此索引基础上文 中实施了对移动对象的范围查询和点查询，最后通过实验表明L2R 结构的索引和查询性能均要优越于TPR 树。 关键词：移动对象数据库；范围查询；L2R 树 DOI ：10.3778/j.issn. 1002-