0 引言

近年来城市智能交通在云计算和大数据技术的推动下，取得了飞跃式的发展，对其所产生的海量交通数据进行有效处理，既可以为城市管理者提供交通管理决策支持，也可以为公安部门刑侦工作提供支持。

关系型数据库无法实现海量数据的有效存储与处理，而NoSQL^[1]数据库恰恰具有优异的海量数据存储能力，目前在智能交通领域，以HBase为代表的NoSQL数据库逐渐得到了广泛应用。

交通数据是一类典型的时空数据。时空数据的快速查询一般都通过建立时空索引来实现。关系型数据库常采用R树及其变种、四叉树和K-D树(K-Dimension tree)等^[2-5]结构来实现时空索引，但交通时空数据的实时产生使得维护这类索引结构代价非常高，并且应用时需要修改原有程序框架，具有侵入性,并不适用于创建海量交通数据的时空索引。在此情形下，如何设计高效、无侵入的HBase时空索引，实现海量交通数据的快速时空查询成了一大挑战。

基于HBase只能通过行键(Rowkey)实现高效索引的事实，本文主要探讨如何在HBase行键上基于三维(时间、经度、纬度)时空数据实现索引结构。Geohash^[6]是一种有效的空间降维方法，基于Geohash与时间维度的不同组合机制，本文提出了适合不同应用场景的四种HBase时空索引结构，能够有效地通过HBase行键和过滤器来实现对海量交通数据的时空查询。

1 相关工作

HBase不直接支持多维索引，仅支持在Rowkey上建立索引。目前，国内外在HBase多维索引研究上，已经产生了部分研究结果，下面分别进行介绍。

1.1 二级索引

华为公司的HBase二级索引^[7]基于协处理器实现，索引建好后，对HBase的scan、Puts、Deletes操作使用HBase原生代码(无需任何改动)即可获得索引的效果；但是它需要在建表时指定索引列(且不支持动态修改)，同时代码对HBase本身侵入性很大，难以升级维护。

360公司的HBase二级索引方案^[8]是在吸收华为索引的优点并摒弃其缺点的基础上建立的，它对HBase的侵入性小；且索引和数据在同一个region上，避免了索引与数据不在同一服务器上造成的I/O通信，减少了查询时间。

HBase二级索引虽然可以实现对多维数据的索引，但是时空查询请求一般需要多次查询候选数据，这会大幅降低查询速度，并不适合交通数据的时空查询。

1.2 空间索引

文献[9]提出利用Geohash算法进行空间降维实现的索引结构，该方案实现简单，不仅能有效提升邻近车辆查询的性能，在具体应用时，也不需要更改原有系统的架构。

文献[10]提出了MD-HBase索引方案，它是一种多维空间索引(Multi-Dimensional index)方案，采用了K-D树和四叉树对查询区域进行划分，并通过Z曲线将区域线性化，将线性化后的值作为HBase Rowkey来实现索引。

这两种空间索引结构都是采用降维思路，对空间查询有较好的性能，虽然不能很好支持时空查询，但其思路及实现方法非常具有借鉴价值。

1.3 时空索引

文献[11]提出的UQE-Index索引结构(Update and Query Efficient index framework)是一种基于HBase的、支持高吞吐率的写入和多维查询的索引结构。这种索引结构实现复杂，将数据分为实时数据和历史数据，其中：实时数据的时间和空间分开建索引，时间维用的是B+树，空间维用的是四叉树或K-D树；而对历史数据采用的是R树或网格。由于B树和R树的使用，使得这种索引结构在数据量过大时，索引的维护会变得困难，不适用于具有实时数据存储要求的场景。

文献[12]提出了一种基于Geohash编码和时间组合的时空索引结构，这种索引结构实现简单，它将一位Geohash编码和时间的年月部分作为HBase的Rowkey，三位Geohash编码作为列族名，三位Geohash编码和时间的日时部分作为列名。这样的结构将一个对象一天的记录都存在了表的同一行里，如果存放交通数据，一行就要存上几万条记录，并且由于Rowkey里只有一位Geohash码，在经过行键扫描时，需要扫描的区域范围会非常大，得到的初始结果集很大，需要耗费大量的时间在值过滤上，非常不利于交通数据的时空区域快速查询。

2 面向海量交通数据的HBase时空索引

基于HBase行键的索引具有简便、无侵入性等特点，而Geohash作为空间降维方案，能够将二维空间映射到一维字符串，天然适合用于Hbase行键索引。借鉴上述思路，本文设计了四类组合Geohash与时间的时空索引，介绍其索引结构，描述索引管理算法及基于索引的时空范围查询算法，并定性分析其适用场景。

2.1 索引结构 2.1.1 GT时空索引

GT时空索引(Geo-Time index) 由Geohash编码加上时间组合而成，其结构如图 1所示，在HBase行键中，Geohash编码在前，时间在后。这种索引结构中起主要索引作用的是Geohash编码，时间起辅助作用。

基于GT时空索引的交通数据时空查询过程是：先将查询区域的经纬度转换为Geohash编码，然后与HBase行键进行匹配，确定在查询区域内的记录范围；接着经过行过滤器过滤掉不在查询时间范围内的记录，进一步缩小扫描范围；最后再用值过滤器过滤得到最终的查询结果。

一般来讲，交通数据区域查询的Geohash编码是一个范围，在行键匹配过程中，匹配到查询起止行键的相同前缀的最后一位后，后续的行键索引功能就失效了，即靠后的时间几乎没有索引效果，只能通过行键过滤器来减少数据的扫描范围。如果数据库中存储记录的时间范围比较大，索引效果就会出现明显下降，故这种索引结构仅适用于数据库中存储数据的时间范围跨度比较小的情景。

2.1.2 TG时空索引

TG时空索引(Time-Geohash index)是由时间加Geohash编码作为HBase行键实现的，其结构如图 2所示，时间处于行键的首字段，即在数据索引时，时间起主要索引作用，Geohash编码起辅助作用。

这种索引结构的检索数据过程是：先通过查询时间匹配HBase行键，找到在查询时间范围内的记录，缩小需要扫描的数据范围；然后通过行键过滤器过滤掉不在查询的Geohash范围内的记录，进一步减少数据扫描的范围；最后通过值过滤器得到最终查询结果。

这种索引结构适用于查询时间范围较小的交通数据区域查询。如基于时间点的时空查询，这种情况下，需要扫描的数据范围时间相同，时间完全可以起到索引效果，而且Geohash编码的相同前缀也会起作用，所以查询效果会非常好。相反地，如果查询时间范围较大，效果则会变差，此时Geohash编码失去索引能力，造成查询性能下降。相比GT索引结构，数据库中交通数据记录的时间范围大小对TG索引结构影响不大。

2.1.3 STG时空索引

针对交通数据的特点，结合了GT和TG两种索引结构的优点，将时间与Geohash编码经过特殊组合作为HBase行键构建HBase时空索引，本文称为STG时空索引(Special Time-Geo index)，其结构如图 3所示，它将时间分割成年月日和时分秒两部分，并将年月日作为行键首字符，然后是Geohash编码，最后是时间的时分秒，即年月日+Geohash编码+时分秒的结构。

STG索引结构检索数据的过程是：先通过时间的年月日部分与Geohash编码的相同前缀组成的字段过滤掉大部分记录，得到一个较少的数据扫描范围，然后通过值过滤器即可得到最终的查询结果，这个过程几乎可以不用行键过滤器。

这种索引结构解决了TG索引结构在基于时间范围的时空查询时行键大部分失效的问题，在查询时间范围为一天以内的区域，时空查询有着良好的性能表现，但是在超过一天之后，Geohash编码会失去索引效果。对于交通数据而言，基于时间范围的区域查询，大多情况下时间范围很少超过一天。对于查询时间范围超过了一天的特例，本文的数据查询算法(详情见2.2.2 节)会将时间范围按天进行划分，最终得到若干时间范围都在一天内的子查询后再进行查询，这样保证了行键中整个年月日+Geohash部分都会起到索引效果，总体不会明显降低行键索引效果。整体而言，基于STG索引结构的时空查询性能明显优于TG索引结构。

相对GT索引结构，STG索引结构的优势也是明显的。在实际应用中，HBase数据库中一般会存长达数年的交通车辆动态数据，即对于同一个地点可能会存有近千万条记录，SGT在检索数据时，通过年月日+Geohash可以更大地减少需要扫描的数据范围，相对于GT索引结构扫描的数据会少很多，查询速度自然快了不少。

2.1.4 SGT时空索引

可以看到，STG算法实际是将时间维度进行分解后再与空间维度组合，相应地，空间维度分解后与时间维度组合也是一种索引方案，本文称为SGT(Special Geo Time index)时空索引，其结构如图 4所示。它将Geohash码分割成前缀和偏移量两部分，中间放入时间，即 Geohash前缀+时间+Geohash偏移量的结构。

这种索引结构在查询区域范围较小的情形下，往往效果较好，这是因为如果具有相同的Geohash前缀的话，时间这个维度也被用来进行索引过滤，从而克服了GT算法的不足。但是在查询区域较大的情形下，会出现大量的冗余候选结果，效果会比较差。更为重要的是，Geohash前缀位数的设置会直接影响索引效果，而交通数据查询查询半径和查询时间范围都是变化的，这导致难以找到一个较优的设置参数。STG方法则不存在该问题。

2.2 STG索引相关算法

相比较而言，STG索引结构最适合应用在海量交通数据时空查询场景。下面重点介绍基于STG索引结构的相关算法，GT、TG和SGT的相应算法也是类似的。

2.2.1 时空查询框架

基于时空索引的时空查询框架如图 5所示，由客户端、查询区域处理模块、索引层、数据库和过滤模块五个部分组成。客户端主要负责发出查询请求；查询区域处理模块主要负责将客户端选择的查询区域和查询时间进行时空处理，得到与HBase 行键格式对应的字符串；索引层是查询关键，主要通过行键匹配，从数据库中检索出初始结果集；数据库主要负责数据存储；过滤模块则通过将行键扫描到的初始结果集进行行键和值过滤，得到最终结果集，并返回给客户端。

2.2.2 算法描述

STG索引策略用到了索引构建和数据查询两种算法，其中索引构建算法如算法1所示，数据查询算法按照区域的不同分为圆区域查询和矩形区域查询算法，如算法2和算法3所示。

  算法1 索引构建算法。

  输入 车辆全球定位系统(Global Positioning System,GPS)数据。

  输出 一维字符串。

  步骤1 获取车辆GPS数据的经度、纬度和时间；

  步骤2 将经纬转为Geohash编码(G)；

  步骤3 将时间切分为年月日(yyMMdd)和时分秒(hhmmss)两部分；

  步骤4 将yyMMdd、G和hhmmss组合成一个字符串str；

  步骤5 返回步骤4得到字符串str。

  该算法将车辆GPS数据的经纬度和时间三个维度的数据组合成了一个一维的字符串，使之符合HBase Rowkey的需求，进而实现HBase时空索引。

  算法2 圆区域查询算法。

  输入 查询点的经纬度(lat,lon)、查询半径d和查询时间范围t₀~t₁。

  输出 符合查询条件的结果集A。

  步骤1 通过查询点的经纬度(lat,lon)和查询半径d,求出查询区域的右上顶点(lat1,lon1) 和左下顶点(lat2,lon2) ；

  步骤2 调用算法3，并将算法3的返回值赋给A′；

  步骤3 通过查询半径d对A′进行过滤，得到最终结果集A；

  步骤4 返回最终结果集A。

  算法3 矩形区域查询算法。

  输入 查询区域的右上顶点(lat1,lon1) 、左下顶点(lat2,lon2) 和查询时间范围t₀~t₁。

  输出 符合查询条件的结果集A。

  步骤1 将两个顶点的经纬度转为Geohash编码G1、G2。

  步骤2 判断查询时间范围t₀~t₁是否在一天之内：

  if 查询时间范围在一天之内 then

  调用算法4；

  将算法4的返回结果集添加到集合A中；

  else then

  将查询时间范围按日进行分割，得到一个子查询时间范围的List集合tlist；

  对tlist中的每一个元素都进行一次算法4的调用，并获得返回值；

  将每一次算法4的返回结果集添加到集合A中；

  end if；

  步骤3 返回最终结果集A。

  算法4 查询子算法。

  输入 G1、G2、查询半径d和查询时间范围t_i0~t_i1。

  输出 符合查询条件的结果集A。

  步骤1 将查询时间范围的年月日部分切分出来得到yyMMdd(起止时间的yyMMdd是相同的，只需一个即可)；

  步骤2 将yyMMdd分别与G1、G2组合得到查询的起止行键:r1、r2；

  步骤3 扫描HBase中Rowkey在r1和r2之间的数据得到初始结果集B；

  步骤4 通过HBase过滤器对B进行值过滤，得到结果集A；

  步骤5 返回结果集A。

数据查询算法通过扫描HBase中与查询区域得到的字符串具有相同yyMMdd+Geohash前缀的行键来实现快速定位数据，可以减少大量的冗余数据扫描，提升了数据查询速度。

3 实验结果及分析 3.1 实验环境

本文实验的HBase集群环境如下：

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

2) 硬件环境：双CPU，四核处理器，32 GB内存，10 TB硬盘的PC两台；双CPU，四核处理器，8 GB内存，10 TB硬盘的PC三台。

3.2 实验数据

本文实验的交通数据是车辆GPS数据，来源于某市智能交通系统的真实历史数据，共有三种数据集，分别为500万级、2500万级和7500万级，其中：500万级为2012年10月03日一天的数据，2500万级是2012年10月03日—2012年10月07日的数据，7500万级是2012年10月03日—2012年10月17日的数据，其数据模型如表 1所示。各种索引结构下数据在HBase中的存储模型如表 2所示：Rowkey中的时间年代前两位是去掉的，这样可以在不影响时间精度的前提下缩短Rowkey的长度，精确到秒是为了使得每一条记录都单独存一行，采用9位的Geohash编码，可以精确到4.8 m×4.8 m的空间区域；A是HBase的列族名；Others指的是其他不重要的数据列。SGT算法中Geohash取四位前缀。

本文实验的主要目的是测试在不同查询半径(查询区域)、不同查询时间范围、不同数量级情况下，GT、TG、SGT和STG四种时空索引的性能。

3.3 实验结果及分析

下面分别按基于时间点的区域查询和基于时间范围的区域查询进行实验：

实验1 基于时间点的区域查询。

随机设定某时间点(2012-10-03T00:12:52) ，查询区域中心点为东经116.5344567，北纬39.5674213。考虑查询半径与候选数据集规模对查询性能的影响。

1) 在7500万数量级的数据下，分别对四种时空索引方案进行不同查询半径的区域查询实验，实验结果如图 6所示。从图中可以看，TG索引结构在基于时间点的区域查询上性能最优，SGT和STG索引次之，GT索引最差。从图中还可以看出查询范围的变化对GT、SGT索引结构的性能影响最大，对TG索引结构性能影响最小，对STG索引结构的性能影响比TG索引结构略大一点，但是影响幅度不大。

2) 在查询半径为1000 m的前提下，分别对四种时空索引方案在不同数据量级的数据下进行查询实验，实验结果如图 7所示。从图中可看出，在基于时间点的区域查询时，STG和TG两种索引结构在不同数据量级情况下性能几乎不变，即数量级对它们基于时间点的区域查询性能影响不明显，而对于SGT和GT索引结构影响较大。

实验2 基于时间范围的区域查询。

随机设定查询区域中心点为东经116.5344567、北纬39.5674213，查询半径为1000 m。考虑查询时间范围与候选数据集规模对查询性能的影响。

1) 在7500万数量级的数据下，分别对四种时空索引方案进行不同时间范围内的区域查询实验，实验结果如图 8所示，图中横坐标为待查询的时间范围(单位：h)，纵坐标为查询耗时(单位:s)。从图中可以看出，在基于时间范围的时空区域查询性能上，STG索引优于GT索引，GT索引优于TG索引，SGT与GT性能相当。STG、SGT和GT这三种索引在基于时间范围的区域查询上的性能随着时间范围的增大变化不大，而TG索引结构对时间范围的变化非常敏感。

2) 在查询时间范围为(2012-10-03T00:12:52，2012-10-03T01:12:52) 的前提下，分别在不同数量级的数据下对四种时空索引方案进行区域查询实验，实验结果如图 9所示。从图中可以看出，数量级对STG和TG这两种索引在基于时间范围的区域查询上的性能影响不大，而对于GT和SGT索引影响明显。

综合实验结果分析可知，在上述四种索引中，本文提出的TG时空索引结构在基于时间点的交通数据区域查询上性能最优，STG时空索引结构在基于时间范围的交通数据区域查询上性能最优。虽然在基于时间点的区域查询上STG的性能稍逊于TG的性能，但是在基于时间范围的区域查询上SGT的性能优势明显，在同时有基于时间点和基于时间范围的时空区域查询需求下，STG时空索引方法应该是一个最佳的索引选择。此外，实验表明，基于STG时空索引，数据量级对于时空区域查询的性能影响不大，该特性非常适合在拥有海量数据的智能交通领域中应用。

4 结语

针对基于HBase管理海量交通数据时面临时空查询性能低下的问题，本文结合HBase行键的特点，基于空间维度和时间维度的组合与分解机制，提出了无侵入的HBase时空索引方案，详细介绍了索引结构，并分析了不同时空索引方法的实用场景，提出了基于上述索引方案的交通数据查询算法。实验结果表明没有任何一种方案在所有场景都能达到最优效果，但综合考虑，STG方案在大多数情况下能够具有比较明显的查询性能。下一步的工作主要包括两个方面：首先是测试与树形索引结构的性能对比；其次是寻找一种动态优选最佳索引的方法，即针对不同的查询条件，根据不同的优选策略，动态挑选出最佳的索引方案进行查询。