一种集成R树、哈希表和B*树的高效轨迹数据索引方法

doi:10.11947/j.AGCS.2015.20130520

测绘学报 ›› 2015, Vol. 44 ›› Issue (5): 570-577.doi: 10.11947/j.AGCS.2015.20130520

一种集成R树、哈希表和B^*树的高效轨迹数据索引方法

龚俊¹, 柯胜男¹, 朱庆², 张叶廷³

1. 江西师范大学软件学院, 江西南昌 330022;
2. 西南交通大学地球科学与环境工程学院, 四川成都 610031;
3. 武汉大学测绘遥感信息工程国家重点实验室, 湖北武汉 430079

收稿日期:2013-12-17 修回日期:2014-10-27 出版日期:2015-05-20 发布日期:2015-05-27
作者简介:龚俊(1978—),男,博士,教授,研究方向为时空数据库。E-mail: gongjunbox@163.com
基金资助:
国家自然科学基金(41261086); 国家863计划(2012AA121401)

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

GONG Jun¹, KE Shengnan¹, ZHU Qing², ZHANG Yeting³

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:2013-12-17 Revised:2014-10-27 Online:2015-05-20 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)

摘要/Abstract

摘要： 为兼顾时空索引方法的空间利用率、时间效率和查询种类,提出了一种新的轨迹数据索引方法——HBSTR树。其基本思想是:轨迹采样点以轨迹节点的形式成组集中管理,哈希表用于维护移动目标的最新轨迹节点,轨迹节点满后作为叶节点插入时空R树,另外采用B^*树对轨迹节点构建一维索引,既有利于提升索引创建效率,又同时满足时空条件搜索和特定目标轨迹搜索等多种查询类型。为提升时空查询效率,提出了新的时空R树评价指标和节点选择子算法改进时空R树插入算法,同时提出了一种时空R树的数据库存储方案。试验结果表明,HBSTR树在创建效率、查询效率和支持查询类型等方面综合性能优于现有方法,支持大规模实时轨迹数据库的动态更新和高效访问。

关键词: 轨迹, 时空索引, R树, B^*树, 存储

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

中图分类号:

P208

龚俊, 柯胜男, 朱庆, 张叶廷. 一种集成R树、哈希表和B^*树的高效轨迹数据索引方法[J]. 测绘学报, 2015, 44(5): 570-577.

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.

参考文献

[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.

一种集成R树、哈希表和B^*树的高效轨迹数据索引方法

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	代维秀, 陈占龙, 谢鹏. 居民出行与轨迹行为交互模式挖掘与关联技术[J]. 测绘学报, 2021, 50(4): 532-543.
[2]	张彩丽, 向隆刚, 李雅丽, 王文龙. 基于出租车轨迹的可导航路网构建[J]. 测绘学报, 2021, 50(12): 1650-1662.
[3]	方孟元, 唐炉亮, 杨雪, 胡淳. 基于低频GNSS轨迹的转向级城市交通信息精细预测[J]. 测绘学报, 2021, 50(11): 1469-1477.
[4]	李雅丽, 向隆刚, 张彩丽, 吴华意, 龚健雅. 车辆轨迹与遥感影像多层次融合的道路交叉口识别[J]. 测绘学报, 2021, 50(11): 1546-1557.
[5]	傅琛, 黄升钶, 汤焱, 吴杭彬, 刘春, 姚连璧, 黄炜. 结合行驶场景语义的轨迹-路网实时匹配方法[J]. 测绘学报, 2021, 50(11): 1617-1627.
[6]	朱庆, 冯斌, 李茂粟, 陈媚特, 徐肇文, 谢潇, 张叶廷, 刘铭崴, 黄志勤, 冯义从. 面向动态关联数据的高效稀疏图索引方法[J]. 测绘学报, 2020, 49(6): 681-691.
[7]	陆川伟, 孙群, 陈冰, 温伯威, 赵云鹏, 徐立. 车辆轨迹数据的道路学习提取法[J]. 测绘学报, 2020, 49(6): 692-702.
[8]	方志祥, 仲浩宇, 邹欣妍. 轨迹延续性与影像特征相似性结合的城市道路提取[J]. 测绘学报, 2020, 49(12): 1554-1563.
[9]	谢鹏, 杨春成, 熊顺, 何列松, 周校东. 基于HBase的空间矢量数据存储模型设计与优化[J]. 测绘学报, 2020, 49(10): 1365-1373.
[10]	唐炉亮, 戴领, 任畅, 张霞. 现实与赛博空间数据相结合的城市活动事件时空建模[J]. 测绘学报, 2019, 48(5): 618-629.
[11]	刘纪平, 张用川, 徐胜华, 钱新林, 仇阿根, 张福浩. 一种顾及道路复杂度的增量路网构建方法[J]. 测绘学报, 2019, 48(4): 480-488.
[12]	邬群勇, 吴祖飞, 张良盼. 出租车GPS轨迹集聚和精细化路网提取[J]. 测绘学报, 2019, 48(4): 502-511.
[13]	吴华意, 黄蕊, 游兰, 向隆刚. 出租车轨迹数据挖掘进展[J]. 测绘学报, 2019, 48(11): 1341-1356.
[14]	吴政, 武鹏达, 李成名. 对等网络下自适应层级的矢量数据时空索引构建方法[J]. 测绘学报, 2019, 48(11): 1369-1379.
[15]	万子健, 李连营, 杨敏, 周校东. 车辆轨迹数据提取道路交叉口特征的决策树模型[J]. 测绘学报, 2019, 48(11): 1391-1403.

一种集成R树、哈希表和B*树的高效轨迹数据索引方法

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

一种集成R树、哈希表和B^*树的高效轨迹数据索引方法

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