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

doi:10.11772/j.issn.1001-9081.2017122977

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

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的路网移动对象时空索引方法

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

河海大学计算机与信息学院, 南京 211100

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

Abstract

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:

TP311.13

FENG Jun, LI Dingsheng, LU Jiamin, ZHANG Lixia. Spatio-temporal index method for moving objects in road network based on HBase[J]. Journal of Computer Applications, 2018, 38(6): 1575-1583.

冯钧, 李顶圣, 陆佳民, 张立霞. 基于HBase的路网移动对象时空索引方法[J]. 计算机应用, 2018, 38(6): 1575-1583.

References

[1] NISHIMURA S, DAS S, AGRAWAL D, et al. MD-HBase:a scalable multi-dimensional data infrastructure for location aware services[C]//Proceedings of the 2011 IEEE 12th International Conference on Mobile Data Management. Piscataway, NJ:IEEE, 2011:7-16.
[2] CHEN X Y, ZHANG C, GE B, et al. Spatio-temporal queries in HBase[C]//Proceedings of the 2015 IEEE International Conference on Big Data. Piscataway, NJ:IEEE, 2015:1929-1937.
[3] KOTHURI R K V, RAVADA S, ABUGOV D. Quadtree and R-tree indexes in oracle spatial:a comparison using GIS data[C]//Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2002:546-557.
[4] OOI B C, MCDONELL K J, SACKS-DAVIS R. Spatial kd-tree:an indexing mechanism for spatial databases[C]//Proceedings of the 1987 IEEE Computer Software and Applications Conference. Piscataway, NJ:IEEE, 1987:433-438.
[5] de ALMEIDA V T, GVTING R H. Indexing the trajectories of moving objects in networks[J]. Geoinformatica, 2005, 9(1):33-60.
[6] VORA M N. Hadoop-HBase for large-scale data[C]//Proceedings of the 2011 International Conference on Computer Science and Network Technology. Piscataway, NJ:IEEE, 2011:601-605.
[7] DU N B, ZHAN J F, ZHAO M, et al. Spatio-temporal data index model of moving objects on fixed networks using HBase[C]//Proceedings of the 2015 IEEE International Conference on Computational Intelligence & Communication Technology. Piscataway, NJ:IEEE, 2015:247-251.
[8] van HONG L, TAKASU A. A scalable spatio-temporal data storage for intelligent transportation systems based on HBase[C]//Proceedings of the 2015 IEEE 18th International Conference on Intelligent Transportation Systems. Piscataway, NJ:IEEE, 2015:2733-2738.
[9] 李萍萍.时空数据库中高维数据的降维方法[D]. 哈尔滨: 哈尔滨理工大学,2009:7-18.(LI P P. Dimensionality reduction of higher dimensional data in spatio-temporal databases [D]. Harbin: Harbin University of Science and Technology, 2009: 7-18.)
[10] KARYPIS G, KUMAR V. Analysis of multilevel graph partitioning [C]// Proceedings of the 1995 ACM/IEEE Conference on Supercomputing. New York: ACM, 1995: Article No. 29.
[11] ZHONG R C, LI G L, TAN K-L, et al. G-Tree: an efficient and scalable index for spatial search on road networks [J]. IEEE Transactions on Knowledge & Data Engineering, 2015, 27(8): 2175-2189.
[12] SAHU P K, MANNA K, SHAH N, et al. Extending Kernighan-Lin partitioning heuristic for application mapping onto Network-on-Chip [J]. Journal of Systems Architecture, 2014, 60(7): 562-578.
[13] DVNTGEN C, BEHR T, GVTING R H. BerlinMOD: a benchmark for moving object databases [J]. VLDB Journal, 2009, 18(6): 1335-1368.
[14] KOMAI Y, NGUYEN D H, HARA T, et al. KNN search utilizing index of the minimum road travel time in time-dependent road networks [C]// Proceedings of the 2014 IEEE 33rd International Symposium on Reliable Distributed Systems Workshops. Piscataway, NJ: IEEE, 2014: 131-137.
[15] KE S N, GONG J, LI S N, et al. A hybrid spatio-temporal data indexing method for trajectory databases [J]. Sensors, 2014, 14(7): 12990-13005.

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

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	CUI Shuangshuang, WANG Hongzhi. Implementation method of lightweight distributed index based on log structured merge-tree [J]. Journal of Computer Applications, 2021, 41(3): 630-635.
[2]	Yusheng HU, Bingwei HE, Qingkang DENG. Moving object detection and static map reconstruction with hybrid vision system [J]. Journal of Computer Applications, 2021, 41(11): 3332-3336.
[3]	XU Jiangfeng, TAN Yulong. Optimization of multidimensional index query mechanism based on HBase [J]. Journal of Computer Applications, 2020, 40(2): 571-577.
[4]	FU Yu, WANG Hong. Virtual trajectory filling algorithm for location privacy protection [J]. Journal of Computer Applications, 2019, 39(8): 2318-2325.
[5]	HUO Zheng, ZHANG Kun, HE Ping, WU Yanbin. Crowdsourcing location data collection for local differential privacy [J]. Journal of Computer Applications, 2019, 39(3): 763-768.
[6]	CUI Chen, ZHENG Linjiang, HAN Fengping, HE Mujun. Design of secondary indexes in HBase based on memory [J]. Journal of Computer Applications, 2018, 38(6): 1584-1590.
[7]	WU Renbiao, LIU Chao, QU Jingyi. Storage method for flight delay platform based on HBase and Hive [J]. Journal of Computer Applications, 2018, 38(5): 1339-1345.
[8]	MENG Xuechao, YE Shaozhen. New spatio-temporal index method based on real-time data and query log distribution [J]. Journal of Computer Applications, 2017, 37(3): 860-865.
[9]	FANG Jun, LI Dong, GUO Huiyun, WANG Jiayi. Spatio-temporal index for massive traffic data based on HBase [J]. Journal of Computer Applications, 2017, 37(2): 311-315.
[10]	LYU Shaoqian, MENG Fanrong, YUAN Guan. Trajectory structure-based moving object hotspots discovery [J]. Journal of Computer Applications, 2017, 37(1): 54-59.
[11]	HE Wei, QI Qi, ZHANG Guoyun, WU Jianhui. Moving object detection method based on multi-information dynamic fusion [J]. Journal of Computer Applications, 2016, 36(8): 2306-2310.
[12]	GAO Zhiyong, TANG Wenfeng, HE Liangjie. Moving object detection with moving camera based on motion saliency [J]. Journal of Computer Applications, 2016, 36(6): 1692-1698.
[13]	LIU Qing, FU Yinjin, NI Guiqiang, MEI Jianmin. Distributed deduplication storage system based on Hadoop platform [J]. Journal of Computer Applications, 2016, 36(2): 330-335.
[14]	PI Wenjun, GONG Xiujun. Data driven parallel incremental support vector machine learning algorithm based on Hadoop framework [J]. Journal of Computer Applications, 2016, 36(11): 3044-3049.
[15]	SONG Lujie, MENG Fanrong, YUAN Guan. Moving object location prediction algorithm based on Markov model and trajectory similarity [J]. Journal of Computer Applications, 2016, 36(1): 39-43.