Acta Geodaetica et Cartographica Sinica >

2015 , Vol. 44 >Issue 5: 570 - 577

DOI: https://doi.org/10.11947/j.AGCS.2015.20130520

An Efficient Trajectory Data Index Integrating R-tree, Hash and B*-tree

  • GONG Jun ,
  • KE Shengnan ,
  • ZHU Qing ,
  • ZHANG Yeting
Expand
  • 1. School of Software, Jiangxi Normal University, Nanchang 330022, China;
    2. Faculty of Geosciences and Environmental Engineering, Southwest Jiaotong University, Chengdu 610031, China;
    3. State Key Laboratory of Information Engineering in Surveying Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China

Received date: 2013-12-17

  Revised date: 2014-10-27

  Online published: 2015-05-27

Supported by

The National Natural Science Foundation of China(No.41261086);The National High-tech Research and Development Program of China(863 Program)(No.2012AA121401)

Fold

Abstract

To take into account all of efficiency and query capability, this paper presents a new trajectory data index named HBSTR-tree. In HBSTR-tree, trajectory sample points are collectively stored into trajectory nodes sequentially. Hash table is adopted to index the most recent trajectory nodes of mobile targets, and trajectory nodes will not be inserted into spatio-temporal R-tree until full, which can enhance generation performance in this way. Meantime, one-dimensional index of trajectory nodes in the form of B*-tree is built. Therefore, HBSTR-tree can satisfy both spatio-temporal query and target trajectory query. In order to improve search efficiency, a new criterion for spatio-temporal R-tree and one new node-selection sub-algorithm are put forward, which further optimize insertion algorithm of spatio-temporal R-tree. Furthermore, a database storage scheme for spatio-temporal R-tree is also brought up. Experimental results prove that HBSTR-tree outperforms current methods in several aspects such as generation efficiency, query performance and supported query types, and then supports real-time updates and efficient accesses of huge trajectory database.

Key words： trajectory; spatio-temporal index; R-tree; B*-tree; storage

Cite this article

GONG Jun , KE Shengnan , ZHU Qing , ZHANG Yeting . An Efficient Trajectory Data Index Integrating R-tree, Hash and B*-tree[J]. Acta Geodaetica et Cartographica Sinica, 2015 , 44(5) : 570 -577 . DOI: 10.11947/j.AGCS.2015.20130520

References

[1] YE Li. Research on Data Queries and Processing Techniques in Moving Objects Databases[D]. Chengdu: University of Electronic Science and Technology of China, 2011. (叶李. 移动对象数据库查询及处理技术研究[D]. 成都: 电子科技大学, 2011.)
[2] YIN Zhangcai, LI Lin. Research of Spatiotemporal Indexing Mechanism Based on Snapshot-increment[J]. Acta Geodaetica et Cartographica Sinica, 2005, 34(3):257-261,282.(尹章才,李霖. 基于快照-增量的时空索引机制研究[J]. 测绘学报,2005,34(3):257-261,282.)
[3] LIAO Wei. Indexing and Query Processing on Moving Objects in Location-based Services[D]. Changsha: National University of Defense Technology, 2007. (廖巍. 面向位置服务的移动对象索引与查询处理技术研究[D]. 长沙: 国防科学技术大学, 2007.)
[4] HAO Zhongxiao. New Theories of Spatio-temporal Database[M]. Beijing:Science Press, 2011.(郝忠孝. 时空数据库新理论[M]. 北京: 科学出版社, 2011.)
[5] LI Qingquan, HUANG Lian. A Map Matching Algorithm for GPS Tracking Data[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(2):207-212. (李清泉,黄练. 基于GPS轨迹数据的地图匹配算法[J]. 测绘学报,2010,39(2):207-212.)
[6] XU Lin, LI Qingquan, YANG Bisheng. A Moving Object Index Structure and Near Neighbor Query Method Based on Road Network[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(3):316-321,327. (许林, 李清泉, 杨必胜. 一种基于道路网的移动对象的位置索引与邻近查询方法[J]. 测绘学报,2010,39(3):316-321,327.)
[7] PARENT C, SPACCAPIETRA S, RENSO C.Semantic Trajectories Modeling and Analysis[J]. ACM Computing Surveys, 2013, 45(4):42:1-42:32.
[8] ZHENG Y, ZHOU X. Computing with Spatial Trajectories[M]. New York: Springer-Verlag, 2011.
[9] FRENTZOS E. Trajectory Data Management in Moving Object Databases[D]. Piraeus: University of Piraeus, 2008.
[10] MOKBEL M, GHANEM T, AREF W. Spatio-temporal Access Methods[J]. IEEE Data Engineering Bulletin, 2003, 26: 40-49.
[11] NGUYEN-DINH L, AREF W, MOKBEL M. Spatio-temporal Access Methods:Part2(2003-2010)[J]. IEEE Data Engineering Bulletin, 2010, 33:46-55.
[12] CHAKKA V, EVERSPAUGH A, PATEL J. Indexing Large Trajectory Data Sets with SETI[C]//Proceedings of the 2003 CIDR Conference. Asilomar:[s.n.],2003.
[13] MA Linbing, ZHANG Xinchang. Research on Full-period Query Oriented Moving Objects Spatio-temporal Data Model[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(2):207-211,222. (马林兵,张新长.面向全时段查询的移动对象时空数据模型研究[J].测绘学报,2008,37(2):207-211,222.)
[14] GUO Jing, LIU Guangjun, GUO Lei, et al. A Whole-time Index Design Based on 3D+-TPR-tree for Moving Point Targets[J]. Acta Geodaetica et Cartographica Sinica, 2006, 35(3):267-272. (郭晶,刘广军,郭磊,等.基于3D+-TPR-tree的点目标全时段移动索引设计[J]. 测绘学报,2006,35(3):267-272.)
[15] GONG Jun,KE Shengnan, ZHU Qing, et al. An Efficient Management Method for Point Cloud Data Based on Octree and 3D R-tree[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(4):597-604.(龚俊,柯胜男,朱庆,等.一种八叉树和三维R树集成的激光点云数据管理方法[J].测绘学报,2012,41(4):597-604.)
[16] PFOSER D, JENSEN C, THEODORIDIS Y. Novel Approaches to the Indexing of Moving Object Trajectories[C]//Proceedings of the International Conference on Very Large Data Bases.Cairo:[s.n.],2000.
[17] AGGARWAL C. Managing and Mining Sensor Data[M]. New York: Springer Publishing, 2013.
[18] GONG Jun, ZHU Qing, ZHANG Yeting, et al. An Efficient 3D R-tree Extension Method Concerned with Levels of Detail[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(2):249-255.(龚俊,朱庆,张叶廷,等.顾及多细节层次的三维R树索引扩展方法[J].测绘学报,2011,40(2):249-255.)
[19] LEE D, LIANG S. Geopot: A Cloud-based Geolocation Data Service for Mobile Applications[J]. International Journal of Geographical Information Science, 2011, 25(8):1283-1301.
[20] KE S, GONG J, LI S, et al. A Hybrid Spatio-temporal Data Indexing Method for Trajectory Databases[J].Sensors, 2014, 14(7):12990-13005.
[21] BRINKHOFF T. A Framework for Generating Network-based Moving Objects[J]. GeoInformatica, 2002, 6(2):153-180.
Options
Outlines

/

〈 〉