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

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

作　　者：龚俊[1] 柯胜男[1] 朱庆[2] 张叶廷[3] 

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

出　　处：《测绘学报》2015年第5期570-577,共8页Acta Geodaetica et Cartographica Sinica

基　　金：国家自然科学基金(41261086);国家863计划(2012AA121401)

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

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

分 类 号：P208[天文地球—地图制图学与地理信息工程]