适用于海量时空数据的多维检索方法的研究

　　摘要：针对当前常规方法无法满足大数据量存储与快速索引的问题，该文在分布式数据库HBase的基础上，设计了一种面向海量时空数据的多维检索策略。首先利用三维时空格网分割编码；然后将格网编码、感兴趣维度属性与HBase行键进行融合，设计了一种时空可定制的多维索引结构，并给出了相应的检索策略和算法，较好地实现了多维数据的快速检索。基于2014年8月份成都市出租车轨迹数据的实验结果表明，相较于传统方法，所提方法能大幅度提升多维数据检索的效率，数据规模为1亿行时，耗时比达到319。79倍，且数据规模越大优势越明显；与Geohash空间降维编码相比，检索命中率明显提高，耗时明显减少。
　　关键词：HBase多维检索时空时空大数据格网编码测绘学
　　移动互联网、卫星导航定位、基于位置的服务技术的普及产生了海量的时空数据〔1，2，3〕，为城市交通态势感知、车辆行进路线规划、居民出行特征分析等提供了足够的数据支持〔4〕。与此同时，其多源异构、巨量增长的特征对数据存储及索引方法也提出了更高的要求〔5，6〕。
　　在时空数据索引方面，学者们提出了许多有效方法，包括基于版本的HRtree和MV3Rtree索引〔7〕，通过扩展时间维的TB和STR多维索引树〔8〕，集成多种索引方法的HBSTRtree〔9〕等，但仍然面临着索引创建效率低、未顾及数据存储、数据结构单一等问题。HBase〔10〕作为Hadoop大数据处理框架下的成熟开源数据库，兼顾异构数据快速索引与分布式存储，为海量时空数据的多维检索提供了解决思路。文献〔11〕基于HBase提出了UQEIndex索引结构，支持高吞吐的写入和多维查询，但结构设计复杂，维护困难。开源项目Hindex〔12〕实现了HBase多维数据的快速索引能力，但构建复杂，且对HBase原生机制侵入性大。文献〔13，14，15〕基于HBase采用Geohash编码和时间组合索引，但由于Geohash自身的局限性，使得在进行时空数据检索时效率受到了一定影响。
　　本文设计了一种基于HBase的海量时空数据多维检索方案，利用三维时空格网对数据进行剖分，融合格网编码及多维条件属性，生成HBase原生行键（rowkey）索引，结合相应的检索策略，实现海量时空数据的高效存储和多维检索。
　　1、索引构建及多维数据检索算法
　　1。1格网划分及索引结构设计
　　1。1。1三维时空格网划分
　　格网划分方法广泛应用于空间索引、影像金字塔、矢量切片等领域〔16〕，可以实现对海量数据的快速存储和索引。如图1所示，本文利用时间经度纬度三维规则格网，对海量时空数据进行等间隔划分，为每个格网赋予唯一编码，编码长度根据实际分割情况确定。若格网原点坐标为（T0，Lon0，Lat0），则时空数据点（T，Lon，Lat）所在格网编码CTCLonCLat计算方法为：
　　式中：T、Lon、Lat分别为时间、经度、纬度维度方向的间隔。需要注意的是，由于编码长度为定长，需要根据预设长度以0前置补齐。
　　图1三维规则格网划分示意图
　　1。1。2时空索引结构设计
　　目前以三维时空检索、四维时空目标检索为代表的多维检索需求愈发广泛，而HBase本身是一个稀疏、多维度、排序的映射表，由若干行组成，数据模型可以抽象为行键：列族：列限定符：时间戳，值，检索时虽然通过前4个参数定位数据，然而高效的关键在于行键（rowkey）相关算法的实现，为此，本文设计了灵活的时空行键索引结构，在保留HBase原生机制的前提下，提升时空数据多维检索的效率，索引结构如图2所示。
　　图2时空行键索引结构
　　Fig。2SpatiotemporalRowKeyIndexStructure
　　由于HBase行键匹配顺序是从前往后，由高位到低位，位置越靠前对于检索的影响越大。考虑到时空检索的频率，本文将三维时空格网编码置于索引结构的高位，并在其后可定制追加多个感兴趣维度，最后以随机编码作为结尾保证行键唯一性。这样的行键结构设计首先保证了时空检索的效能，之后由于追加维度的存在，可以实现以时空维度为基础的多维数据索引。
　　1。2数据检索策略
　　结合设计的时空多维索引结构和HBase的运行机制，本文设计了相应的数据检索策略，如图3所示。
　　图3数据检索策略
　　1）首先连接HBase表并输入检索条件，包括时空范围和其他维度检索需求。
　　2）根据输入条件计算检索覆盖的三维格网及编码，结合其他维度条件共同确定行键集合。
　　3）由于行键依字典序排列，其可能不唯一且不连续，因此在检索时需要对行键分组，确定每组起止行键值。
　　4）对行键组依次进行数据检索，采用外部过滤器对索引数据进行精确过滤，并将结果保存。
　　5）判断行键组是否遍历完毕，如果没有，则重复步骤4）；如果遍历完毕，则检索完毕，输出结果。
　　1。3多维数据检索算法
　　依据提出的数据检索策略，以圆形区域的时空数据检索应用为例，对检索算法进行详细阐述。设定背景为：检索T0Tk时间范围内，以（Lonc，Latc）点为中心，半径为r范围内的数据集合。算法步骤如下。
　　1）计算圆形区域最小外接矩形。根据中心点坐标及查询半径计算最小外接矩形范围，左上角坐标为（Lonl，Latl），右下角坐标为（Lonr，Latr），如图4所示。
　　2）格网覆盖计算。利用式（1）根据时空范围确定时间维所覆盖的格网CT0CTk，外接矩形左上和右下顶点所处的格网坐标（CLonl，CLatl）和（CLonr，CLatr）。
　　图4圆形区域覆盖格网
　　3）构建行键索引并确定分组。如图5所示，行键索引主要由固定部分、可定制部分两个模块组成。固定部分为三维时空格网编码模块，用于时空检索；可定制部分为追加的一个或多个其他感兴趣维度的索引，如图5所示，Dnm代表追加的第n个维度的第m种属性。起止行键组则根据索引字典序确定。
　　图5起止行键组生成示意图
　　4）数据提取与精过滤。由于格网粒度的原因，根据行键提取的结果包含了部分无用数据，因此根据检索条件添加数据过滤器进行精确过滤，包括时间维度上利用时间戳进行精确圈定，空间维度上通过距离与半径r的比对判定等。
　　5）循环遍历行键组直至结束，输出结果。
　　2、实验结果与分析
　　2。1实验数据与环境
　　为了验证所设计方法的可行性，本文以2014年8月45日成都市13000余辆出租车06：00：0024：00：00的轨迹数据为数据源，数据规模约为5000万行（2。5GB）d，数据格式为｛TargetID，Lontitude，Latitude，Status，Time｝，对本文设计的多维检索策略进行对比验证。
　　在实验环境方面，本文利用VirtualBox搭建7台虚拟机作为实验平台，配置均为单核4GB内存，操作系统均为CentOS6。5，Hadoop版本为2。7。5，HBase版本为1。4。0，zookeeper版本为3。4。10，Java开发包版本为jdk1。8。0162，程序开发平台采用IntelliJIDEA2017。3。4x64，算法使用Java编写实现。
　　2。2时空检索效能分析
　　为验证方法在时空检索方面的正确性和效率，本文以成都市三环以内作为研究区域，（30。594099，103。98316，1407103200）作为三维格网原点，取Lat为0。00135415、Lon为0。00180182、T为1h进行三维时空格网剖分和编码。
　　2。2。1时间维编码影响分析
　　为了验证时间维编码的影响，以（30。661285，104。067273）为原点，半径为200m的圆形区域作为待查询的空间范围，以2014年8月4日10：00：00作为起始时间，分别对10、30、60以及90min等不同的时间范围进行实验，对比分析本文编码方法和无时间维编码（仅保留空间维）两种情况下检索效能的不同，其结果如图6和表1所示。
　　图6时间编码对数据检索时间的影响对比
　　表1时间编码对检索数量及结果的影响
　　如图6所示，含时间编码的检索耗时明显要少，因为时空编码是对数据进行3个维度的切分，时间维的存在能在空间维索引之前，直接将数据检索范围锁定在包含时间范围的格网内，避免检索其他无用数据。此外，无时间维的方法在不同的时间间隔下检索耗时不变，这是由于查询的空间区域不变，其检索的数据范围也没有发生变化。本文方法在10、30、60min时耗时基本不变，而90min时耗时发生增长，这是所设定的时间维粒度为1h所致，因此前3种情况所覆盖的时间格网一致，检索数据范围也相同，而90min情况多覆盖了一个时间格网，造成了检索数量的提升。表1的检索数量以及命中率两个指标验证了理论分析的正确性。
　　2。2。2空间编码影响分析
　　为了验证空间编码的影响，以2014年8月4日10：00：0011：00：00作为查询的时间范围，对以（30。661285，104。067273）为原点，半径分别为100、200、500以及1000m的圆形区域进行检索实验，对比分析本文格网编码方法、Geohash空间降维编码方法〔15〕以及无空间维编码（仅保留时间维）的检索效能。
　　实验结果如图7所示，无空间维索引方法耗时最多，相较于前者，Geohash方法有明显的性能提升，而本文方法优势最为明显，耗时最少。结合表2分析，虽然3种方法检索结果均完全一致，但无空间维索引方法的命中率明显远低于另外两种，原因在于本文方法和Geohash方法都对空间维进行了分割和编码，检索时能够通过空间维的编码索引，避免检索目标范围之外的大量无用数据。此外，虽然Geohash方法也取得了一定的效果，但当Geohash编码和HBase检索机制结合应用时，它的编码索引命中范围仍然比目标区域要大很多，而本文方法中格网编码与位置结合更为紧密，检索时的命中率更高，耗时也更少。
　　图7不同编码方式下检索时间对比
　　表2不同空间维情况下检索结果对比
　　2。3多维检索效能分析
　　为验证本文方法的正确性以及在多维条件检索时的效能，本文以时空目标四维条件检索为例，在1000、2000、5000以及1亿行4种不同数据规模下，对本文方法（时空格网编码目标编码）以及传统方法（无行键索引，遍历检索）开展实验，检索条件为：目标编号为6804，起止时间为2014年8月4日10：00：0011：00：00，空间范围为以坐标（30。661285，104。067273）为原点，半径为500m的圆形区域。实验结果如图8所示。
　　图8不同数据规模下多维检索耗时对比
　　由图8结果可知，多维检索（时空目标）的情况下本文方法的检索耗时远比传统方法要少。结合表3的实验结果，随着数据规模的增大，虽然两种方法耗时都随之增加，但从耗时比来看，本文方法优势始终存在且不断扩大，并当数据规模为1亿行时，耗时比达到了319。79倍。从检索数量以及命中率可以看出，这是由于传统方法采用遍历检索，检索命中率较低；而本文通过多维索引直接快速定位数据，大幅度缩小了检索范围，提升了检索效率。另外，由于传统方法采用遍历的方式，其结果数量可以作为参考标准，通过对比不同数据规模情况下本文方法与传统方法的检索结果数量发现，本文方法的查全率为100，证明了本文方法的正确性。
　　表3实验结果对比3结束语
　　针对海量时空数据背景下，多维数据检索较慢的难题，结合HBase的索引机制，设计了时空可定制多维数据索引结构，并针对时间维、空间维、数据规模的影响开展了对比分析实验。结果表明：
　　1）在海量数据背景下，本文方法不但能够准确地检索数据，并且与传统方法相比，能大幅度降低耗时。另外，随着数据规模的增大，优势会愈发明显。
　　2）索引结构上，时间维和空间维均发挥了重要作用，并且与现有的Geohash空间降维算法相比，本文方法与HBase相结合时，能够更加快速、精确地命中数据。
　　3）本文方法能够在时空检索的基础上满足多维检索需求，定制灵活且性能良好。
　　综上，本文设计的方法具有较为明显的优势，在保证准确性的前提下，不仅时间效率高，且能够适应海量数据的增长。然而，由于受索引结构以及检索机制的影响，本文方法在随机检索任意一个或多个维度时效能不高，后续将通过研究增加辅助索引的方式解决相关问题。