留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

大规模轨迹数据的Geohash编码组织及高效范围查询

向隆刚 王德浩 龚健雅

向隆刚, 王德浩, 龚健雅. 大规模轨迹数据的Geohash编码组织及高效范围查询[J]. 武汉大学学报 ● 信息科学版, 2017, 42(1): 21-27. doi: 10.13203/j.whugis20150175
引用本文: 向隆刚, 王德浩, 龚健雅. 大规模轨迹数据的Geohash编码组织及高效范围查询[J]. 武汉大学学报 ● 信息科学版, 2017, 42(1): 21-27. doi: 10.13203/j.whugis20150175
XIANG Longgang, WANG Dehao, GONG Jianya. Organization and Efficient Range Query of Large Trajectory Data Based on Geohash[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 21-27. doi: 10.13203/j.whugis20150175
Citation: XIANG Longgang, WANG Dehao, GONG Jianya. Organization and Efficient Range Query of Large Trajectory Data Based on Geohash[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 21-27. doi: 10.13203/j.whugis20150175

大规模轨迹数据的Geohash编码组织及高效范围查询

doi: 10.13203/j.whugis20150175
基金项目: 

国家自然科学基金 41471374

国家自然科学基金 41001296

详细信息
    作者简介:

    向隆刚, 博士, 副教授, 主要从事轨迹数据处理与分析。geoxlg@whu.edu.cn

  • 中图分类号: P208

Organization and Efficient Range Query of Large Trajectory Data Based on Geohash

Funds: 

The National Natural Science Foundation of China 41471374

The National Natural Science Foundation of China 41001296

More Information
    Author Bio:

    XIANG Longgang, PhD, associate professor, specializes in trajectory processing and analyzing.geoxlg@whu.edu.cn

图(6) / 表(1)
计量
  • 文章访问数:  3367
  • HTML全文浏览量:  345
  • PDF下载量:  667
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-09-07
  • 刊出日期:  2017-01-05

大规模轨迹数据的Geohash编码组织及高效范围查询

doi: 10.13203/j.whugis20150175
    基金项目:

    国家自然科学基金 41471374

    国家自然科学基金 41001296

    作者简介:

    向隆刚, 博士, 副教授, 主要从事轨迹数据处理与分析。geoxlg@whu.edu.cn

  • 中图分类号: P208

摘要: 面向成熟的关系-对象型空间数据库,利用Geohash编码的唯一性、一维性和递归性等特征,提出了一种基于Geohash编码的大规模轨迹数据组织方法及范围查询技术。该方法结合Geohash编码和B+树索引,设计了适应不同尺度范围查询的大规模轨迹数据的关系组织模式,并给出了相应的两阶段查询处理算法,同时提出了一种Z合并优化,以进一步提高范围查询的处理效率。实验结果表明,此方法适合于组织管理与查询分析大规模的轨迹数据,其范围查询性能高于内置的R树索引。

English Abstract

向隆刚, 王德浩, 龚健雅. 大规模轨迹数据的Geohash编码组织及高效范围查询[J]. 武汉大学学报 ● 信息科学版, 2017, 42(1): 21-27. doi: 10.13203/j.whugis20150175
引用本文: 向隆刚, 王德浩, 龚健雅. 大规模轨迹数据的Geohash编码组织及高效范围查询[J]. 武汉大学学报 ● 信息科学版, 2017, 42(1): 21-27. doi: 10.13203/j.whugis20150175
XIANG Longgang, WANG Dehao, GONG Jianya. Organization and Efficient Range Query of Large Trajectory Data Based on Geohash[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 21-27. doi: 10.13203/j.whugis20150175
Citation: XIANG Longgang, WANG Dehao, GONG Jianya. Organization and Efficient Range Query of Large Trajectory Data Based on Geohash[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 21-27. doi: 10.13203/j.whugis20150175
  • 近年来,人们愈加方便地获取位置信息、请求基于位置的服务(location-based service,LBS)[1],并将人或物体的移动过程以轨迹的形式记录下来。轨迹数据本身的价值催生了基于轨迹的位置服务,如线路分享、车辆调度和安保等[2]。同时, 对轨迹数据进行挖掘分析可以获得有关个人行为模式、人与人之间的相关性以及人在不同地域之间的活动模式等知识,从而为用户提供更加智能、有效、人性化的位置服务[2-3]。由地理数据、轨迹数据和应用记录等构成的位置大数据已经成为分析地理国情和构建智慧城市的重要战略资源[4]

    越来越多的应用要求管理移动对象产生的大规模轨迹数据并提供查询分析能力,其中,范围查询的快速处理是需要迫切解决的关键问题之一,常见的解决之道是设计和构造合适的索引结构,以此来大幅减少范围查询的搜索空间。目前, 针对轨迹数据索引技术的研究主要集中于二维空间索引结构的变形与扩展方面[5-14]。文献[5-14]中提出的方法虽能面向各自的查询优化问题,建立相应的有效索引结构来辅助查询处理,但是,这种针对二维空间索引进行的变形或扩展使得其组织与管理方法变得异常复杂,难以集成到空间数据库管理系统(如Oracle[16]、PostgreSQL[17]等)之中。

    目前,空间数据库主要以内置的B+树或R树等简单成熟的索引结构来辅助查询处理。本文面向关系-对象型空间数据库,提出了一种基于Geohash[18]的大规模轨迹数据的高效组织结构及快速范围查询方法。该方法的核心思想是建立不同编码长度的Geohash索引表,在多种空间尺度下用覆盖轨迹的网格来近似表达轨迹,从而将针对二维空间中轨迹数据的范围查询降维处理为针对相应Geohash索引表的一维查询。此外,本文分析讨论了查询范围初始编码长度的选择问题,并根据Geohash编码的递归特征,提出了始于初始编码长度的自底向上Z合并优化,以进一步提高范围查询的处理效率。

    • Geohash是一种地理编码格式,它沿着经度和纬度的方向交替二分地球表面,并使用一个二进制数(Geohash编码)表示所形成的互不重叠网格。对全球进行两次划分后形成4个编码长度为2的Geohash编码(00、01、10、11),对应4个网格。以编码为11的网格为例,经度范围为[0, 180°],纬度范围为[0, 90°],若继续对此网格做两次划分,将形成4个编码长度为4的Geohash编码(1100、1101、1110和1111)。

      Geohash编码具有几个特点:(1)唯一性[19]。每个单元网格都有全球唯一的编码与之对应。(2)一维性。Geohash用一维数字或字符串表示二维空间区域。(3)递归性。Geohash下级单元网格由上级单元网格划分而得,其本质上是一种空间Z曲线填充,一个“Z”字型内的4个Geohash网格属于同一个父网格,它们的二进制编码具有相同的前缀。Geohash现已被应用在兴趣点快速搜索[20]、面数据区域查询[21]等方面。

    • 编码确定轨迹的Geohash编码需要在给定编码长度下,计算轨迹穿过了哪些Geohash网格。以图 1为例具体说明轨迹的Geohash编码。图 1(a)展示了示例轨迹在编码长度为17时穿过的9个网格及其编码, 而图 1(b)则展示了同一示例轨迹在编码长度增加为19时穿过的22个网格及其编码。由此可见,一条轨迹可能对应一个或多个Geohash编码。同时,可能有多条轨迹穿过同一个Geohash网格,因此,轨迹与网格之间是多对多的关系。

      图  1  轨迹Geohash编码示例

      Figure 1.  A Demonstration of Trajectory Geohash Encoding

    • 针对大规模轨迹数据,本文面向关系-对象型数据库,设计了基于Geohash编码的关系组织模式及其范围查询框架(见图 2)。其主要思想是对轨迹进行Geohash编码组织,利用一维的B+树来处理二维的范围查询。为了兼顾大小迥异的范围请求,本文共设计了5种不同码长的Geohash索引表,在5种空间尺度下表达轨迹与Geohash网格之间的多对多关系。范围查询使用经典的两阶段处理策略,索引筛选阶段直接使用标准SQL语言查询相应的Geohash索引表,以获得候选轨迹集,据此再通过遍历求精来获得最终查询结果。

      图  2  基于Geohash的轨迹数据关系模式及其范围查询框架

      Figure 2.  Geohash-Based Relational Scheme of Trajectory Data Andits Processing Framework of Range Query

    • 除了轨迹数据表之外,本文还在关系组织模式中引入了Geohash索引表,并在其Geohash编码字段上建立B+树索引。由于Geohash是一种固定大小的空间划分编码技术,通常由R树支持的范围请求便可转化为针对Geohash索引表及B+树索引的查询处理。考虑到用户提出的查询范围可大可小,本文建立了码长分别为19、21、23、25和27的5种Geohash索引表,以将不同大小的范围查询导向合适码长的Geohash索引表。此外,这种设计有利于范围查询的并行化处理,而且这种并行既可以针对多个范围查询,也可以用于单个查询处理。

    • 范围查询使用经典两阶段处理策略,首先索引筛选,通过Geohah索引表筛选出候选集,然后遍历求精,通过检验轨迹的几何信息从候选集中求出最终结果。由于遍历求精阶段并无特殊之处,本节着重讨论索引筛选阶段。

      首先计算覆盖了查询范围q,且初始码长为P0的Geohash网格编码集C0;然后从码长P0开始,以自底向上方式Z合并编码集C0,得到对应于码长序列(设为 < P0, …, Pl>,Pi=P0-2×i,0≤il≤4)的多个Geohash编码集(设为D0, …, Dl,分别对应P0, …, Pl);接着为每一种码长(设为Pi)生成针对相应Geohash索引表的SQL语句Si,其WHERE条件则由相应Geohash编码集(即Di)构造而来;最后将不同的SQL语句(即S0, …, Sl)发往不同的Geohash索引表,以并行方式执行这些SQL语句。需要指出的是,P0设置和Z合并优化是提高索引筛选性能的关键。

    • 当码长为p时,范围查询q的代价模型可以表示为:

      $$ C\left( {q,p} \right) = {C_f}\left( {q,p} \right) + {C_r}\left( {q,p} \right) $$ (1)

      其中,Cf(q, p)表示索引筛选代价;Cr(q, p)表示遍历求精代价。若保持q不变,增加码长,Geohash编码数目将增多,相应Geohash索引表的规模也会增大,从而导致Cf(q, p)增大。由此可知,p越长,索引筛选代价越高,反之亦然,即:

      $$ p \uparrow {C_f}\left( {q,p} \right) \uparrow ,p \downarrow {C_f}\left( {q,p} \right) \downarrow $$ (2)

      同时,随着码长p的减小,一般情况下覆盖查询范围的Geohash网格面积Sg会随之减小。图 3举例说明了Sgp的关系,深色矩形表示查询范围,其面积Sq约为222.7 km2,红框矩形为覆盖查询范围的Geohash网格集。图 3(a)显示p为25时,Sg约为480 km2图 3(b)显示p为27时,Sg约为288.1 km2。较小的Sg往往意味着较少的轨迹落于其中,因而Cr(q, p)也随之减小。所以,p越长,遍历求精代价越小,反之亦然,即:

      图  3  不同码长网格覆盖同一查询范围面积对比

      Figure 3.  A Comparison of Covering Areas with Different Geohash Code Precisions

      $$ p \uparrow {C_r}\left( {q,p} \right) \downarrow ,p \downarrow {C_r}\left( {q,p} \right) \uparrow $$ (3)

      综合式(1)和式(2)可知,针对某一范围查询窗口,当初始码长P0变长时,索引筛选代价增高,遍历求精代价降低。因此,需要找到合适的P0,使得式(3)最小。然而在实际应用中,受查询窗口大小、数据分布密度、不同数据库查询效率差异等因素的影响,精确计算出P0是一件非常困难的事情。实验观察发现, 当查询窗口的面积小于1°×1°时,Geohash编码数目总体较少,索引筛选时间很短,遍历求精占据范围查询的大部分时间,此时应选择较长的P0(27位),以有效降低Cr(q, P0)。随着查询窗口面积逐渐增大,索引筛选时间对查询效率逐渐形成了较大影响。当面积超过1°×1°时,应选择P0为25,而当面积超过3°×3°时,P0为23较为合适。需要指出的是,在初步选定P0后,还应进一步判断以其父网格(即码长为P0-2)覆盖q时是否满足以下两种情况之一:① P0-2生成的网格面积和P0相同。② P0-2的网格面积所覆盖的轨迹和P0相同,或者只是稍多一些。若成立,则应以P0-2作为初始码长,否则以P0作为初始码长。

    • 索引筛选阶段,以初始码长P0计算覆盖查询范围的Geohash编码集合可能包含数量巨大的Geohash编码,如果直接将其表达为SQL语句的WHERE谓词,将在解析和过滤两方面给查询处理引擎带来较大负担。考虑到Geohash编码是一种Z曲线填充,一个“Z”范围内的4个编码具有相同的前缀,Z合并优化利用这一递归特性,用一个更短的编码替代同一“Z”字内4个编码,以减少编码总数。

      Z合并优化过程首先将编码集Di拆分为两个编码集Dz, iDnz, i,其中,Dz, i包含能够合并的编码,Dnz, i包含不能合并的编码。接着将Dnz, i作为码长为Pi的编码集(即Di)加入list。然后Z字合并Dz, i中的编码,形成码长为Pi+1(Pi+1=Pi-2)的编码集,并以该编码集作为Di+1循环执行上述过程,直到没有可以合并的编码为止。最终,算法返回包含多种码长编码集的集合list{D0, …, Dl}。

      图 4展示了Z合并优化的效果,图 4(a)中阴影部分代表的查询范围由48个相同长度的Geohash编码覆盖。图 4(b)显示经过Z合并优化处理后,形成了3种长度的编码集{D0, D1, D2}。其中,D0包含24个编码,D1包含2个编码,D2包含1个编码。可见,Z合并优化既可以减少Geohash编码数目以简化查询条件,又能生成多种码长支持并行查询处理。

      图  4  Geohash编码Z合并优化示意

      Figure 4.  Diagram of Geohash Code Z-Merge Optimizing Method

    • 为验证本文方法的性能,本文使用C++基于Oracle 11g数据库实现了基于Geohash大规模轨迹数据组织结构及其范围查询方法。实验数据为开放街道地图(OpenStreetMap, OSM)上美国范围用户自愿上传的31 880条GPS轨迹,约11.1 GB。实验环境为Windows 7操作系统,2.93 GHz Intel Core i3 CPU,4 GB内存,931 GB 7200 RPM硬盘驱动器。

      首先建立轨迹数据表,导入实验数据,并为轨迹数据添加R树索引,作为对比实验。然后对数据分别建立19位、21位、23位、25位、27位和29位6种码长的整型Geohash索引表。实验中查询范围的选择方法是在美国范围内随机选取点,以之作为东北角分别生成0.01°×0.01°、0.1°×0.1°、1°×1°、2°×2°、3°×3°、4°×4°、5°×5°、10°×10°的矩形。查询时间统计是对每种范围做500次查询实验,计算其平均时间。

      1)实验1:初始码长选择实验。针对不同大小范围查询,分别以21、23、25、27、29作为初始码长,总查询时间对比结果见表 2。在1°×1°及以下查询范围内,27位和29位作为始码长查询效果更好,但29位较27位的性能提升不明显,因此在实际应用中只需建立27位的Geohash索引表。范围在1°×1°到3°×3°之间的查询,25位初始码长的查询效果最好。当范围超过3°×3°时,23位初始码长的查询效果最好。以上即是本文推荐的初始码长选择策略,后文实验均遵照此策略选择初始码长。同时实验1也说明本文建立的5种Geohash索引表可以满足大小迥异的范围查询请求。

      表 1  不同查询范围下初始码长选择

      Table 1.  Selection of Initial Code Precision for Range Queries of Various Sizes

      查询范围 初始码长
      21/ms 23/ms 25/ms 27/ms 29/ms
      0.01°×0.01° 750.52 569.52 246.7 145.1 132.8
      0.1°×0.1 1 098.9 874.1 472.9 315.2 298.7
      1°×1° 5 026.3 4 451.9 3 969.1 3 548.5 4 876.9
      2°×2° 10 639.7 9 012.7 7 958.9 9 587.7 11 198.3
      3°×3° 15 972.1 13 574.4 10 585.7 14 402.4 34 782.7
      4°×4° 18 857.8 15 612.3 20 234.1 27 979.3 52 863.1
      5°×5° 26 729.4 19 611.6 34 689.4 40 074.1 78 896.3
      10°×10° 49 393.5 39 979.3 67 763.6 10 1023.2 20 1486.9

      2)实验2:Z合并优化性能测试实验。对比使用和不用Z合并优化对索引筛选时间的影响,实验结果见图 5

      图  5  使用与不使用Z合并优化索引筛选时间比较

      Figure 5.  Comparison of Indexing Time of Using and not Using Z-Merge Optimization

      范围查询的面积较小时,Geohash编码总量较少,Z合并优化没有大幅减少索引筛选时间。随着查询范围面积增大,Z合并优化的优势变得明显,原因在于Geohash编码数目随着查询面积的增大快速增加,而Z合并优化能有效减少SQL语句中查询条件的数目。值得注意的是,在4°×4°范围处,两条曲线均出现了时间下降的现象,这是查询范围超过3°×3°,选择23位码长引起的效率提升。实验2表明,Z合并优化能显著地减少索引筛选时间。

      3)实验3:范围查询效率对比实验。比较本文方法与传统的基于R树索引查询方法(简称为R树法)的范围查询效率,实验结果见图 6。其中图 6(a)给出了索引筛选阶段对比结果,本文方法的索引筛选时间在0.01°×0.01°至5°×5°范围内小于R树法,而在10°×10°范围时超过了R树法。这是因为随着查询范围的增大,覆盖查询范围的编码数目增长速度非常快,导致检索Geohash索引表的SQL语句变得非常庞大复杂,其处理代价随之急剧升高。图 6(b)给出了过滤求精阶段对比结果,可以看到基于Geohash的范围查询方法遍历求精时间总是小于R树法,说明其索引筛选的准确率更高。图 6(c)给出了查询总时间对比图,显然无论针对何种查询范围,基于Geohash的范围查询方法的查询效率总高于R树法。但是受到索引筛选时间的影响,基于Geohash的范围查询方法在查询范围较小时的效率优势更加明显。

      图  6  两种方法查询时间对比

      Figure 6.  Comparison of Range Query Performance Using Two Different Indexing Methods

    • 本文提出了大规模轨迹数据的Geohash编码组织方法,采用球面剖分数据模型,可以针对小到城镇、大到国家,甚至全球范围的轨迹数据,进行统一建模。同已有方法相比,本文结合Geohash编码和B+树索引,直接在通用数据库系统及标准SQL语句之上实现了针对大规模轨迹数据的高效范围查询,实验结果表明其显著优于传统的R树索引方法。显然,此方法同样适合于处理近邻查询。此外,在数据更新时只需在关系表中增加或删除记录即可,更新代价很小。下一步将研究如何在本文提出的框架之上实现更为复杂的轨迹数据查询。

参考文献 (21)

目录

    /

    返回文章
    返回