Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (6): 1575-1583.DOI: 10.11772/j.issn.1001-9081.2017122977

Previous Articles     Next Articles

Spatio-temporal index method for moving objects in road network based on HBase

FENG Jun, LI Dingsheng, LU Jiamin, ZHANG Lixia   

  1. College of Computor and Information, Hohai University, Nanjing Jiangsu 211100, China
  • Received:2017-12-20 Revised:2018-02-07 Online:2018-06-10 Published:2018-06-13
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61602151, 61370091), the National Key Research and Development Program of China (2017YFC0405806), the Key R & D Program of Jiangsu Province (Social Development) Project (BE2015707).

基于HBase的路网移动对象时空索引方法

冯钧, 李顶圣, 陆佳民, 张立霞   

  1. 河海大学 计算机与信息学院, 南京 211100
  • 通讯作者: 陆佳民
  • 作者简介:冯钧(1969-),女,江苏武进人,教授,博士,博士生导师,CCF专业会员,主要研究方向:时空间数据管理、智能数据处理、数据挖掘、水利信息化;李顶圣(1993-),男,安徽安庆人,硕士研究生,主要研究方向:时空数据索引、智能交通系统、大数据Hadoop;陆佳民(1983-),男,江苏南通人,博士,讲师,CCF专业会员,主要研究方向:移动对象数据管理、分布式数据处理、水利信息化;张立霞(1990-),女,山东日照人,硕士研究生,主要研究方向:时空数据索引、智能交通系统、大数据Hadoop。
  • 基金资助:
    国家自然科学基金资助项目(61602151,6137091);国家重点研发计划项目 (2017YFC0405806);江苏省重点研发计划(社会发展)项目(BE2015707)。

Abstract: Hbase can only use key value query, it is not suitable for multidimensional query of mobile objects in road network, which leads to inefficiency in storing index and query. In order to solve this problem, an efficient HBase indexing framework for Road network Moving objects (RM-HBase) was designed and implemented on the basis of HBase storage structure. Firstly, the upper Hmaster and lower HregionServer of the primary HBase index structure were improved to solve the hot distribution problem of distributed cluster data and improve the query efficiency of spatial data. Secondly, the road network moving object index - Road Network tree (RN-tree) was proposed to solve the problem of "dead space" in space division and improve the query efficiency of road sections in the space at the same time. Then, based on the above improvements of HBase index, the query algorithms for spatio-temporal range query, spatial-temporal K Nearest Neighbor (KNN) query and moving object trajectory query were designed respectively. Finally, the Spatial-TEmporal HBase IndeX (STEHIX) framework based on HBase distributed database was selected as the contrast object, the performance of RM-HBase was respectively analyzed from two aspects of the performance of index framework and the efficiency of query algorithm. The experimental results show that, the proposed RM-HBase is superior to the STEHIX framework in both the performance of data equilibrium distribution and the query performance of spatio-temporal query algorithm, and it is helpful to promote the efficiency of spatial-temporal index for the moving object data in mass road network.

Key words: road network environment, moving object, HBase, spatio-temporal index, query algorithm

摘要: 在处理路网移动对象时,由于HBase只能采用key查询,不适用于移动对象的多维查询,导致HBase存在存储索引与查询效率不高的问题。针对此问题,在HBase存储结构的基础上设计并实现了一种高效的路网移动对象HBase索引框架(RM-HBase)。首先,对原生HBase索引框架的上层HMaster和下层HRegionServer进行改进,解决分布式集群数据的热点分布问题,提高空间数据的查询效率;其次,提出路网移动索引——RN-tree,解决空间划分中的"死空间"问题,同时提高空间中路段的查询效率;然后,基于上述对HBase的索引改进,分别设计了时空范围查询、时空K最近邻(KNN)查询和移动对象轨迹查询的查询算法;最后,实验选用了同样是基于HBase分布式数据库而提出的时空HBase索引(STEHIX)框架作为对比对象,分别从索引框架的性能和算法的查询效率两个方面对RM-HBase的性能进行分析。实验结果表明,所提的RM-HBase在数据的均衡分布性能和时空查询算法的查询性能方面都优于STEHIX框架,有助于提升海量路网移动对象数据的时空索引效率。

关键词: 路网环境, 移动对象, HBase, 时空索引, 查询算法

CLC Number: