基于道路网络的时空索引方法IMon-tree

doi:10.3724/SP.J.1087.2012.02205

计算机应用 ›› 2012, Vol. 32 ›› Issue (08): 2205-2222.DOI: 10.3724/SP.J.1087.2012.02205

基于道路网络的时空索引方法IMon-tree

李峰,罗磊

江苏大学计算机科学与通信工程学院，江苏镇江 212013

收稿日期:2012-01-16 修回日期:2012-03-15 发布日期:2012-08-28 出版日期:2012-08-01
通讯作者: 罗磊
作者简介:李峰(1968-)，男，江西赣州人，副教授，博士，CCF会员，主要研究方向：地理信息系统、视频图像处理、嵌入式计算
罗磊(1987-)，男，湖南岳阳人，硕士研究生，主要研究方向：地理信息系统。

Spatiotemporal index for moving objects in networks: IMon-tree

LI Feng,LUO Lei

School of Computer Science and Telecommunication Engineering, Jiangsu University, Zhenjiang Jiangsu 212013, China

Received:2012-01-16 Revised:2012-03-15 Online:2012-08-28 Published:2012-08-01
Contact: LUO Lei

摘要/Abstract

摘要： 针对Mon-tree索引的不足提出一种基于道路网络的时空索引方法IMon-tree。索引分三层，顶部用四叉树网格来索引道路网络，底部二维R树用来索引物体的运动信息，中部单链表将上述两层连接起来，完成从道路到运动信息的映射。为了支持轨迹查询，用哈希表将物体的运动信息组织起来。对比实验表明IMon-tree轨迹查询比TMN-tree性能更好，时空查询算法平均响应时间是Mon-tree的65%,是TMN-tree的81%。该方法可应用于各种空间数据库以及地理信息系统。

关键词: 时空索引, Mon-tree索引, TMN-tree, 时空查询, 轨迹查询

Abstract: To overcome the shortcoming of the Mon-tree index, a method called IMon-tree (Improved Mon-tree) index was proposed. It included three layers: the top layer used grids to index roads; the bottom layer was used to index the objects' moving information; the middle, which connected the above two layers, was to complete the mapping from roads to moving information. In order to implement trajectory query, the hash table was used to save the moving information of objects. The experimental results show that the IMon-tree index has a better performance than TMN-tree on trajectory query. As to the average response time of the spatiotemporal query algorithm, the IMon-tree is 65 percent of the Mon-tree, and is 81 percent of the TMN-tree. Therefore, the suggested method can be applied to all kinds of geodatabases and geographic information systems.

Key words: spatiotemporal index, Mon-tree index, TMN-tree, spatiotemporal query, trajectory query

中图分类号:

TP311.13

李峰罗磊. 基于道路网络的时空索引方法IMon-tree[J]. 计算机应用, 2012, 32(08): 2205-2222.

LI Feng LUO Lei. Spatiotemporal index for moving objects in networks: IMon-tree[J]. Journal of Computer Applications, 2012, 32(08): 2205-2222.

参考文献

[1]KIM K-S, KIM S-W, KIM T-W. Fast indexing and updating method for moving objects on road networks[C]// WISEW'03: Proceedings of the 4th International Conference on Web Information Systems Engineering Workshops. Washington, DC: IEEE Computer Society, 2003: 34-42. [2]ALTENIS S, JENSEN C S, LEUTENEGGER S T, et al. Indexing the positions of continuously moving objects[C]// SIGMOD '00: Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2000: 331-342.[3]FRENTZOS E.Indexing objects moving on fixed networks[C]// Proceedings of the 8th International Symposium on Spatial and Temporal Database, LNCS 2750.Berlin:Springer-Verlag,2003:289-305. [4]de ALMEIDA T, GTING R H. Indexing the trajectories of moving objects in networks[C]// SSDBM'04: Proceedings of 16th International Conference on Scientific and Statistical Database Management. Washington, DC: IEEE Computer Society, 2004: 115-118. [5]CHANG J-W, SONG M-S, UM J-H. TMN-tree: new trajectory index structure for moving objects in spatial networks [C]// Proceedings of the 10th International Conference on Computer and Information Technology. Washington, DC: IEEE Computer Society, 2010:1633-1638. [6]GTING R H, de ALMEIDA T, DING Z. Modeling and querying moving objects in networks[J].The International Journal on Very Large Data Bases, 2006,15(2): 165-190. [7]XU J Q, GTING R H. A generic data model for moving objects[EB/OL]. [2012-05-24]. http://dna.fernuni-hagen.de/papers/GenericModel360Revised.pdf. [8]FORLIZZI L, GTING R H, NARDELLI E, et al. A data model and data structures for moving objects databases[C]// Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2000: 319-330. [9] GTING R H, BEHR T, DNTGEN C. SECONDO: a platform for moving objects database research and for publishing and integrating research implementations[J].IEEE Data Engineering Bulletin, 2010, 33(2): 56-63. [10]DNTGEN C, BEHR T, GTING R H. BerlinMOD: a benchmark for moving object databases[J].The International Journal on Very Large Data Bases, 2009, 18(6): 1335-1368. [11]GTING R H. How to build your own moving objects database system[C]// Proceedings of the 8th International Conference on Mobile Data Management. Washington, DC: IEEE Computer Society, 2007: 1-2.

基于道路网络的时空索引方法IMon-tree

Spatiotemporal index for moving objects in networks: IMon-tree

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

[1]	冯钧, 李顶圣, 陆佳民, 张立霞. 基于HBase的路网移动对象时空索引方法[J]. 计算机应用, 2018, 38(6): 1575-1583.
[2]	孟学潮, 叶少珍. 基于实时数据和历史查询分布的时空索引新方法[J]. 计算机应用, 2017, 37(3): 860-865.
[3]	房俊, 李冬, 郭会云, 王嘉怡. 面向海量交通数据的HBase时空索引[J]. 计算机应用, 2017, 37(2): 311-315.
[4]	廖国琼叶小玉蒋剑狄国强刘德喜. 支持位置追溯的射频识别移动对象索引机制[J]. 计算机应用, 2014, 34(1): 58-63.