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

doi:10.11947/j.AGCS.2015.20130520

Abstract

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

CLC Number:

P208

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.

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.

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	ZHANG Lin, SHEN Yunzhong, CHEN Qiujie, WANG Fengwei. Analysis of terrestrial water storage change and its driving factors of Hongliu River region [J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(4): 622-630.
[2]	DAI Weixiu, CHEN Zhanlong, XIE Peng. Research on the interactive mode of residents’ behavior based on trajectory data mining [J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(4): 532-543.
[3]	ZHANG Caili, XIANG Longgang, LI Yali, WANG Wenlong. Construction of navigable road network based on taxi trajectories [J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(12): 1650-1662.
[4]	FANG Mengyuan, TANG Luliang, YANG Xue, HU Chun. Fine-grained traffic information prediction at the turning-level based on low-frequency GNSS trajectory data [J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(11): 1469-1477.
[5]	LI Yali, XIANG Longgang, ZHANG Caili, WU Huayi, GONG Jianya. Road intersection recognition based on a multi-level fusion of vehicle trajectory and remote sensing image [J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(11): 1546-1557.
[6]	FU Chen, HUANG Shengke, TANG Yan, WU Hangbin, LIU Chun, YAO Lianbi, HUANG Wei. A real-time map matching method for road network using driving scenario classification [J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(11): 1617-1627.
[7]	LU Chuanwei, SUN Qun, CHEN Bing, WEN Bowei, ZHAO Yunpeng, XU Li. Road learning extraction method based on vehicle trajectory data [J]. Acta Geodaetica et Cartographica Sinica, 2020, 49(6): 692-702.
[8]	FANG Zhixiang, ZHONG Haoyu, ZOU Xinyan. Extracting urban road area based on combination of trajectory continuity and image feature similarity [J]. Acta Geodaetica et Cartographica Sinica, 2020, 49(12): 1554-1563.
[9]	XIE Peng, YANG Chuncheng, XIONG Shun, HE Liesong, ZHOU Xiaodong. Design and optimization of spatial vector data storage model based on HBase [J]. Acta Geodaetica et Cartographica Sinica, 2020, 49(10): 1365-1373.
[10]	YAO Chaolong, LUO Zhicai, HU Yueming, WANG Changwei, ZHANG Rui, LI Jinming. Detecting droughts in Southwest China from GPS vertical position displacements [J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(5): 547-554.
[11]	TANG Luliang, DAI Ling, REN Chang, ZHANG Xia. Spatio-temporal modeling of city events combining datasets in cyberspace and real space [J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(5): 618-629.
[12]	LIU Jiping, ZHANG Yongchuan, XU Shenghua, QIAN Xinlin, QIU Agen, ZHANG Fuhao. An incremental construction method of road network considering road complexity [J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(4): 480-488.
[13]	WU Qunyong, WU Zufei, ZHANG Liangpan. GPS trajectory agglomeration and refined road network extraction [J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(4): 502-511.
[14]	WU Huayi, HUANG Rui, YOU Lan, XIANG Longgang. Recent progress in taxi trajectory data mining [J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(11): 1341-1356.
[15]	WU Zheng, WU Pengda, LI Chengming. Adaptive hierarchical spatio-temporal index construction method for vector data under peer-to-peer networks [J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(11): 1369-1379.