基于HBase的路网移动对象时空索引方法
|
摘要
在处理路网移动对象时,由于HBase只能采用key查询,不适用于移动对象的多维查询,导致HBase存在存储索引与查询效率不高的问题。针对此问题,在HBase存储结构的基础上设计并实现了一种高效的路网移动对象HBase索引框架(RM-HBase)。首先,对原生HBase索引框架的上层HMaster和下层HRegion Server进行改进,解决分布式集群数据的热点分布问题,提高空间数据的查询效率;其次,提出路网移动索引——RN-tree,解决空间划分中的"死空间"问题,同时提高空间中路段的查询效率;然后,基于上述对HBase的索引改进,分别设计了时空范围查询、时空K最近邻(KNN)查询和移动对象轨迹查询的查询算法;最后,实验选用了同样是基于HBase分布式数据库而提出的时空HBase索引(STEHIX)框架作为对比对象,分别从索引框架的性能和算法的查询效率两个方面对RM-HBase的性能进行分析。实验结果表明,所提的RM-HBase在数据的均衡分布性能和时空查询算法的查询性能方面都优于STEHIX框架,有助于提升海量路网移动对象数据的时空索引效率。
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 Hregion Server 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 Inde X(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.
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 Hregion Server 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 Inde X(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.
引文
[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 the1987 IEEE Computer Software and Applications Conference.Piscataway,NJ:IEEE,1987:433-438.
[5]de ALMEIDA V T,GUTING 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 KernighanLin partitioning heuristic for application mapping onto Network-onChip[J].Journal of Systems Architecture,2014,60(7):562-578.
[13]DUNTGEN C,BEHR T,GTING R H.Berlin MOD: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.
[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 the1987 IEEE Computer Software and Applications Conference.Piscataway,NJ:IEEE,1987:433-438.
[5]de ALMEIDA V T,GUTING 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 KernighanLin partitioning heuristic for application mapping onto Network-onChip[J].Journal of Systems Architecture,2014,60(7):562-578.
[13]DUNTGEN C,BEHR T,GTING R H.Berlin MOD: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.