基于HBase的交通数据区域查询方法

李 冬 房 俊

(北方工业大学大规模流数据集成与分析技术北京市重点实验室 北京 100041)

基于HBase的交通数据区域查询方法

李 冬 房 俊

(北方工业大学大规模流数据集成与分析技术北京市重点实验室 北京 100041)

随着智能交通的发展,交通数据呈现出指数性增长。为了提升时空区域查询性能,论文提出了一种基于HBase的交通数据区域查询方法HRQ。该方法利用交通数据的三维时空特性,采用Geohash算法将交通数据的经纬度信息转为Geohash编码,然后与时间组合作为HBase行键,并设计了相应的查询算法。实验结果表明,与直接组合经纬度和时间作为行键的方法相比,在基于时间范围的区域查询上HRQ方法的性能要高30%以上,在基于区域范围的区域查询上HRQ的性能优势随着查询区域的增大而增加。

HBase; Geohash算法; 区域查询; 海量交通数据; 时空特性

Class Number TP311

1 引言

随着智能交通的发展,交通数据呈现出指数性增长。传统的关系型数据库无法应对海量交通数据的高效存储和处理需求,以HBase为代表的NoSQL数据库[1]具有扩展性强、并发性能好、数据模型灵活等优点,在海量数据存储和查询方面具有先天的优势,国内外很多大型互联网公司都用它来存储和管理海量数据[2～3]。

车辆数据的区域查询[4]是智能交通应用的一种基础数据服务,像Uber和滴滴等打车软件的叫车服务和公安机关的刑侦过程一般都需要对车辆GPS数据等交通数据进行区域查询。交通数据具有三维时空特征,对交通数据的区域查询其实就是一种时空查询,这对于只能在行键上构建字典序索引的HBase是一个挑战,即如何实现在HBase中对交通数据进行快速有效的区域查询是一大难点。

针对上述问题,本文提出了一种基于HBase的交通数据区域查询方法——HRQ(HBase based Regional Query)时空区域查询方法。该方法是通过Geohash算法[5]的降维思想将交通数据的位置信息(经度、纬度)转为一维字符串,然后加上记录的时间作为HBase行键,实现对交通数据的快速区域查询。它不仅能有效提升交通数据区域查询的性能,而且也不需要更改原有系统的架构,具有很高的实用性。

2 相关工作

为了更好地实现对时空数据的区域查询,近年来很多研究者采用将R-树与其他索引结构组合的方式[6～11]实现空间索引和时空索引。其中文献[9]提出了一种利用R-树对区域进行划分的区域查询方法,它是由区域索引、对象位置索引和对象索引三部分组成,采用了R-树、网格和Hash三种数据结构,该方法在查询对象分布不均匀时具有比R-树和网格有更优的查询性能。文献[10]提出了一种基于R-树和四叉树的空间索引结构,它的节点构造是按空间数据的分布来进行的,使得树的高度尽可能降低,有利于提升区域查询的性能。文献[11]提出了一种基于KD树和R-树的多维索引结构,是一种双层索引模型,与R-树索引相比具有一定优势。上述三种方法采用混合索引结构实现空间索引,占用大量的冗余空间,实现复杂,并且树形结构使索引维护变得困难,在海量数据环境下,树的索引性能可能会退化为线性检索从而导致查询性能大大降低。

针对时空数据的多维特性进行降维处理,在降维得到的信息上构建索引来提升空间区域查询性能,是近年来的一个新的研究热点。文献[12]提出了一种在Mysql数据库中实现的基于Geohash的面数据区域查询方法,即将数据的经纬度信息转为Geohash编码,存到一个列中,并在该列上建索引,这种方法在关系型数据库中相对于基于经纬度、R树的查询有一定的优势。文献[13]提出了一种在HBase数据库中实现的基于Geohash的车辆数据邻近查询方法,该方法将车辆信息的经纬得到Geohash编码与车牌ID组合作为HBase行键,来实现车辆数据的空间区域查询。上述两种研究工作只利用了数据的空间信息,仅对只有空间特征的数据查询具有较好的性能。

3 基于HBase的交通数据区域查询

3.1 相关定义

定义1 交通数据集C={ci|i∈(1,n)},其中ci表示一条车辆信息记录,包括车辆检测设备(如GPS设备)的ID、车辆ID、时间、经度、纬度和车辆其他信息等。

定义2 两点距离是指对于点A、B,令(Lona,Lata)表示A点经纬度,(Lonb,Latb)表示B点经纬度,由谷歌地图计算方法可得A,B两点的距离d(A,B)=S*R,其中R为地球半径。S值由如下公式求得:

其中,a=Lata-Lotb为两点纬度之差,b=Lona-Lonb为两点经度之差。

下面给出交通数据区域查询的定义,本文目前仅考虑矩形区域查询及圆形区域查询。

定义3 矩形查询区域是指由点p1(Lat1,Lon1)、p2(Lat2,Lon2)、p3(Lat3,Lon3)、p4(Lat4,Lon4)(其中p1、p2、p3、p4分别为查询区域的左下角点,右下角点,左上角点和右上角点)所构成的空间区域。

图1 最小外接矩形

定义5 区域时空查询是指在对某一选中区域,在此区域内查询在时间段(Ts,Te)内的交通数据。即求Csub⊆C,使得:

∀∈Csub,c.lat∈(Lat1,Lat3)&

c.lon∈(Lon1,Lon2)&c.t∈(Ts,Te),

其结果集记为Cn。如果是矩形区域查询,则Cn为最终结果;如果是圆形区域查询,还需满足:

∀c∈Cn,d(p,c)≤D

3.2 基于HBase区域查询的一般方法

图2 经纬度加时间的行键组合示例图

由于交通数据具有时空三维特性,结合HBase行键的特征,想要能够有效检索出具有时空特性的交通数据,就需要将交通数据中时空的三个维度属性全都放在HBase行键中。HBase传统的区域时空查询方法是直接用经纬度加时间作为行键实现的,其组合过程如图2所示。采用该方法时,数据存储到HBase中的逻辑数据模型如表1所示。

表1 基于经纬度的HBase数据模型

基于该方法的时空区域查询步骤如下:

第一步,确定查询区域;

第二步,通过查询区域的左下角和右上角两个顶点的经纬度和查询起止时间,确定需要扫描HBase的行键范围;

第三步,设置行键过滤器和值过滤器;

第四步,对HBase进行扫描,输出结果集。

采用该方法的行键设计,由于数据的时空属性全在行键之中,在检索数据时,可以通过行键减少数据扫描的范围。但是,该方法的数据在HBase中的存储顺序是先按照纬度排序,再按照经度排序,最后按照时间排序的,即在行键中时空的三个维度权重都不一样。由于HBase基于行键扫描数据时,只有首字段会有很好的索引效果,所以这种区域时空查询方法在扫描数据时,会先扫描在查询区域的纬度范围内的所有数据,造成很多经度不在查询范围内的冗余数据扫描,大大增加了数据查询时间,降低了查询性能。

3.3 HRQ区域时空查询方法

为了使交通数据的经纬度和时间三个维度在HBase行键中起到更好的索引效果,本文提出一种HRQ区域时空查询方法。它将交通数据的经纬度信息通过Geohash算法转为一维字符串,再与时间组合成一个新的字符串,作为HBase记录的行键,其组合过程如图3所示,数据在HBase表中的逻辑数据如表2所示。

图3 Geohash编码加时间的行键组合示例图

RowkeyDATAcarIDlatlontimeOtherswx494q937nbt2012021112122京A666639.5867386N116.1163483E2012-02-1112:12:291,5000,m

基于该方法的时空区域查询算法如下所示。

第一步,确定查询区域;

第二步,将查询区域的左下和右上两个顶点的经纬度转为Geohash编码;

第三步,将两个Geohash编码分别与查询的起止时间组合得到起止行键;

第四步,设置行键过滤器和值过滤器;

第五步,扫描HBase数据库,如果是矩形区域查询,输出最终结果值;如果是圆形区域查询,执行第六步;

第六步,从扫描出来的结果集中找出所有到查询点的距离小于查询半径的结果,并输出。

以Geohash编码和时间组合作为的行键相对于经纬度加时间组合作为的行键更短,减少了冗余存储空间,最重要的是Geohash编码使得经纬度在行键中具有了同等权重,并且Geohash编码本身代表的就是一个区域范围,在查询时通过行键匹配即可直接找到对应的查询区域或其最小外接矩形。在查询扫描时,先通过居于行键首字段的Geohash编码找到整个查询区域的最小外接矩形内的车辆信息,然后通过居于行键末端的时间来进行行键过滤,找出查询区域的最小外接矩形内属于查询时间范围内的车辆信息,最后再通过值过滤器得到最终的结果值。即扫描的是由查询条件的纬度范围和经度范围组成的区域内的数据,而不是所有属于查询纬度范围内的数据,大量减少了冗余扫描,减少了查询时间,从而提升了区域查询的性能。为保证查找出符合条件的所有数据,实际查询时扫描的区域总是会比需要查询的区域要大一些,即总是会有冗余扫描,HBase的值过滤器会过滤掉所有不符合查询条件的数据,保证最终结果都在查询的时空区域内,从而保证了结果的准确性。

在实际查询时,基于Geohash编码的特性,可以将查询区域的最小外包矩形与Geohash编码表示的空间区域对应起来,这样查询时直接找到查询区域所在的最小外接Geohash网格即可,如图4所示,当它们处于1关系时可以直接查询包含查询区域Q的G网格来获取查询结果。但是由于Geohash网格代表的是固定区域,而实际查询时,选择的区域很有可能会刚好位于几个Geohash网格的边界上,如图4中的关系2所示,所以在实际查询时,需要对查询区域进行一定处理,以与Geohash网格对应。

图4 Q与G的关系

对于图4中的关系2的情况,传统的Geohash区域处理方法是将G和它邻近的8个区域一起来作为查询区域,如图5(a)所示。这种处理方法会造成大量的冗余数据扫描,像图5(b)中所示,如果Q处于实线框的情况,只需要扫描4格Geohash网格,实际却扫描了9格,处于虚线框的情况,由于Q包含了整个G,则需要按图4中的1情况处理,这样实际扫描的Geohash网格是32格,而实际只需要扫描12格。为了尽量减少冗余数据扫描,本文的HRQ方法采用了一种新的区域处理方法,对图4中的两种情况都适用,其算法如下所示。

算法:查询区域处理算法

输入:查询区域的顶点经纬度p1(Lat1,Lon1)、p2(Lat2,Lon2)、p3(Lat3,Lon3)、p4(Lat4,Lon4)或查询点p(Latp,Lonp)和半径D。

输出:Geohash网格集G

算法步骤:

1) 判断查询类型,如果是矩形区域查询,执行步骤3;如果是圆形区域查询,执行步骤2)。

3) 分别将p1、p2、p3、p4的经纬度值转为Geohash编码g1、g2、g3、g4。

4) 获取g1、g2、g3、g4的相同前缀g,即找到包含g1、g2、g3、g4的最小外接Geohash网格。

5) 分别取g1、g2、g3、g4中除去前缀g之后的第一位Geohash码b1、b2、b3、b4。

6) 将32个base32标示码依次加入到链表listb中。

7) 遍历listb,找出在b1～b4围成的区域内的base32标识码(含b1～b4),并加上Geohash前缀g之后依次添加到Geohash网格集G中。

8) 返回Geohash网格集G。

该算法得到的Geohash网格集G中的元素是查询区域在其最小外接的Geohash网格内跨越的所有Geohash子网格,即需要扫描的整个Geohash区域。查询算法只需依次查询G中各个Geohash子网格内的数据,最后合并结果值就可以得到最终的结果值。该算法通过第五步过滤掉了包含查询区域的最小外接Geohash网格内所有与查询区域无交集的Geohash子网格,大大减少了冗余区域的查询,使得查询的冗余数据明显减少,例如对于表4中的关系1的情况,只需要扫描G中的12个子网格即可,减少了20格子网格的扫描,对表4中的关系2的情况只需扫描4个Geohash子网格,减少了5个Geohash子网格。可见该方法大大减小了冗余数据的扫描。

图5(a) 邻近单元a

图5(b) 邻近单元b

4 实验对比及分析

本文从时空区域的区域范围和时间范围以及数据集的量级三个方面来对本文提出的HRQ区域查询方法和传统的经纬度加时间的区域查询方法进行交通数据的区域查询性能对比实验。

实验环境:

1) 软件环境:Hadoop-1.2.1、Zookeeper-3.4.6、HBase-0.94.8、jdk7、centos7操作系统。

2) 硬件环境:2颗四核处理器,32G内存,10T硬盘的测试服务器两台;2颗四核处理器,8G内存,10T硬盘的测试服务器三台;2颗四核处理器,4G内存,500G硬盘的测试客户机一台。

实验数据:本文的实验数据来自实验室购买的的实际车辆GPS数据,其中千万级数据集为2012年10月03日的数据,约3000万条记录,亿级数据集为2012年10月03日到2012年10月06日的数据,约1.1亿条记录。数据未存入到HBase数据库之前的结构如表3所示,主要由GPS唯一标识符(ID)、数据采集时间点(TIME)、经度(LON)、纬度(LAT)以及其他一些信息组成。经过处理后存到HBase中的数据的结构如表4所示,只存储了GPS唯一标识符(ID)、数据采集时间点(TIME)、经度(LON)和纬度(LAT)四个信息。

表3 原始数据的结构

表4 HBase中数据的结构

实验一在千万级数据集下分别对两种方法进行查询区域点为东经116.3265305、北纬39.8885880,半径分别为0.5km、1km、1.5km,时间点为(2012-10-0301:51:23)的交通数据区域查询实验。

实验结果如图6所示,在查询范围较小的时候,HRQ方法相对于经纬度加时间方法的性能优势不是很明显,但是随着查询区域范围的扩大性能优势也随之变得明显,即HRQ在相同时间点的区域时空查询上性能要优于传统的HBase交通数据区域查询方法,并且查询区域越大,性能优势越明显。

图6 时间点的车辆数据区域查询

实验二分别对两种查询方法在千万级数据集和亿级数据集下进行时间范围在(2012-10-03 01:51:23,2012-10-03 01:51:33)、(2012-10-03 01:51:23,2012-10-03 01:52:23)、(2012-10-03 01:51:23,2012-10-03 02:51:23)、(2012-10-03 01:51:23,2012-10-03 06:51:23)、(2012-10-03 01:51:23,2012-10-0311:51:23)、(2012-10-03 01:51:23,2012-10-0316:51:23)、(2012-10-03 01:51:23,2012-10-04 01:51:23)内、查询区域中心点为东经116.3265305,北纬39.8885880、查询半径为1km的区域进行车辆数据时空查询实验。实验结果如图7和8所示,可以看出,HRQ在时间范围的交通数据区域查询上,性能要明显优于经纬度加时间的HBase交通数据区域查询方法,其中千万级数据集下查询性能要高40%以上,亿级数据集下查询性能高30%以上。

综合图7和图8的结果可以看出随着数据集的增大,HRQ方法相对于经纬度加时间的方法的优势会降低。主要原因是在HRQ方法中时间信息处于行键的最后位置,时间的索引作用最低,它几乎只能靠行键过滤器来起作用。这使得同一查询条件下的区域查询,HBase中存储记录跨越的时间区间越大扫描到的冗余数据就越多,从而造成查询性能降低,即HRQ的查询性能会随着HBase中存储记录所跨越的时间区间变大而降低,这是今后的研究工作中需要解决的一个问题。

图7 千万级数据集时间范围车辆数据区域查询

图8 亿级数据集时间范围车辆数据区域查询

综合实验结果分析可知,本文提出的HRQ交通数据区域查询方法相较直接由经纬度加时间实现的传统交通数据区域查询方法有着明显的查询性能优势。但是该方法还有不足之处,由于在方法中时间在行键中处于靠后位置,所以时间起到的索引能力要远远小于Geohash起到的索引能力,使得查询性能随着HBase存储记录跨越的时间区间的变大而降低,所以该方法适合用在HBase中存储的记录的时间区间跨度不是很大的场景。本文也考虑过将时间放在前面,但是那样Geohash的索引效果就会降低,只在查询时间范围较小的交通数据区域查询上会有很好的效果。

5 结语

本文利用了Geohash算法降维和HBase行键的特点,提出的基于HBase的交通数据区域查询方法(HRQ)。为了提高对HBase中交通数据的区域查询,该方法将车辆GPS数据的经纬度通过Geohash算法转为一维字符串,再和时间信息一起组合作为HBase的行键,可以在检索数据时大大减少数据的扫描范围,一定程度上提升了区域查询的性能,具有一定实际应用价值。未来的工作方向是研究如何使时间、经度和纬度这三个属性的值在行键中尽可能的具有相等的权值,以更好地提升交通数据区域查询性能。

[1] 申德荣,于戈,王习,等.支持大数据管理的NoSQL系统研究综述[J].软件学报,2013(8):1786-1803. SHEN Derong, YU Ge, WANG Xi, et al. Survey on NoSQL for management of big data. RuanJianXueBao/Journal of Software[J]. 2013,24(8):1786-1803.

[2] 葛微,罗圣美,周文辉,等.HiBase:一种基于分层式索引的高效HBase查询技术与系统[J].计算机学报,2016,39(1):140-153. GE Wei, LUO Shengmei, ZHOU Wenhui, et al. HiBase: A Hierarchical Indexing Mechanism and System for Efficient HBase Query[J]. Chinese Journal of Computers,2016,39(1):140-153.

[3] Nick Dimiduk, Amandeep Khurana. HBase实战[M].谢磊,译.北京:人民邮电出版社,2013:197-228. Nick Dimiduk, AmandeepKhurana. HBase In ACTION[M]. XIE Lei, translate. Beijing: Posts & Telecom Press,2013:197-228.

[4]David Taniar, Wenny Rahayu. A taxonomy for region queries in spatial databases[J]. Journal of Computer and System Sciences,2015,81:1508-1531.

[5] Geohash[Z]. https://en.wikipedia.org/wiki/Geohash.

[6] Shoji Nishimura, Sudipto Das, Divyakant Agrawal, et al. MD-HBase:design and implem-entation of an elastic data infrastructure for cloud-scallocaltion services[J]. Distrib Parallel Databases,2013,31:289-319.

[7] Anthony Fox, Chris Eichelberger, James Hughes, et al. Spatio-temporal Indexing in Non-relational Distrbuted Databases[C]//IEEE International Conference on Big Data. Santa Clara, CA, USA,2013.

[8] GONG Jun, KE Shengnan, ZHU Qing, et al. An Efficient Trajectory Data Index Inegrating R-tree, Hash and B*-tree[J]. Acta Geodaetcaet Cartographica Sinica,2015,44(5):570-577.

[9] 郭超,李坤,王永炎,等.面向实时定位系统的位置区域索引[J].计算机研究与发展,2011,48(10):1908-1917. GUO Chao, LI Kun, Wang Yongyan, et al. A location Index for Range Query in Real-Time Locating System[J]. Journal of Computer Research and Development,2011,48(10):1908-1917.

[10] 刘润涛,郝忠孝.R-树和四叉树的空间索引结构:RQOP_树[J].哈尔滨工业大学学报,2010,42(2):324-327. LIU Runtao, HAO Zhongxiao. Spatial index structure based on R-tree and quadtree: RQOP_tree[J]. Journal of Harbin Institute of Technology,2010,42(2):324-327.

[11] 何婧,吴跃,杨帆,等.基于KD树和R树的多维云数据索引[J].计算机应用,2014,34(11):3218-3221,3278. HE Jing, WU Yue, YANG Fan, et al. Multi-dimensional cloud index based on KD-tree and R-tree[J]. Journal of Computer Applications,2014,34(11):3218-3221,3278.

[12] 金安,程承旗,宋树华,等.基于Geohash的面数据区域查询[J].地理与地理信息科学,2013,29(5):31-33. JIN An, CHENG Chengqi. SONG Shuhua, et al. Regional Query of Area Data Based on Geohash[J]. Geography and Geo-Information Science,2013,29(5):31-33.

[13] Shen D, Fang J, Han Y. A Nearby Vehicle Search Algorithm Based on HBase Spatial Index[C]//Web Information System and Application Conference. IEEE,2015:71-74.

A Regional Query Method of Traffic Data Based on HBase

LI Dong FANG Jun

(Beijing Key Laboratory on Integration and Analysis of Large-scale Stream Data, North China University of Technology, Beijing 100041)

With the development of intelligent traffic, traffic data has exponential growth. To improve the query’s performance of spatial and temporal region, this article proposes HRQ region query methods of traffic data based on HBase. The method uses the Geohash algorithm to make traffic data’s latitude and longitude information become a Geohash code, and combines time to form HBase’s keys. This article designs the corresponding query algorithms too. Experimental results show that, compared to the direct combination of latitude, longitude and time as HBase’s keys, the performance of HRQ method is 30% higher in time-based region query, and HRQ’s performance advantage increases as query area increases in region’s query based on regional.

HBase, Geohash algorithm, regional query, massive traffic, spatial and tempal feature

2016年8月11日,

2016年9月27日

北京市自然科学基金重点资助项目“面向大规模流式数据处理的数据空间理论与关键技术研究”(编号:4131001)资助。

李冬,男,硕士研究生,研究方向:云数据管理。房俊,男,博士,副研究员,研究方向:服务计算和云计算。

TP311

10.3969/j.issn.1672-9722.2017.02.008