留言板

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

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

Geohash-Trees:一种用于组织大规模轨迹的自适应索引

向隆刚 高萌 王德浩 龚健雅

向隆刚, 高萌, 王德浩, 龚健雅. Geohash-Trees:一种用于组织大规模轨迹的自适应索引[J]. 武汉大学学报 ● 信息科学版, 2019, 44(3): 436-442. doi: 10.13203/j.whugis20160523
引用本文: 向隆刚, 高萌, 王德浩, 龚健雅. Geohash-Trees:一种用于组织大规模轨迹的自适应索引[J]. 武汉大学学报 ● 信息科学版, 2019, 44(3): 436-442. doi: 10.13203/j.whugis20160523
XIANG Longgang, GAO Meng, WANG Dehao, GONG Jianya. Geohash-Trees: An Adaptive Index Which can Organize Large-Scale Trajectories[J]. Geomatics and Information Science of Wuhan University, 2019, 44(3): 436-442. doi: 10.13203/j.whugis20160523
Citation: XIANG Longgang, GAO Meng, WANG Dehao, GONG Jianya. Geohash-Trees: An Adaptive Index Which can Organize Large-Scale Trajectories[J]. Geomatics and Information Science of Wuhan University, 2019, 44(3): 436-442. doi: 10.13203/j.whugis20160523

Geohash-Trees:一种用于组织大规模轨迹的自适应索引

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

国家自然科学基金 41471374

国家自然科学基金 41001296

详细信息
    作者简介:

    向隆刚, 博士, 教授, 主要研究方向为轨迹数据处理与分析。geoxlg@whu.edu.cn

    通讯作者: 高萌, 硕士。gmshepard@whu.edu.cn
  • 中图分类号: P208

Geohash-Trees: An Adaptive Index Which can Organize Large-Scale Trajectories

Funds: 

The National Natural Science Foundation of China 41471374

The National Natural Science Foundation of China 41001296

More Information
    Author Bio:

    XIANG Longgang, PhD, professor, specializes in trajectory processing and analysis. E-mail: geoxlg@whu.edu.cn

    Corresponding author: GAO Meng, master. E-mail:gmshepard@whu.edu.cn
图(5)
计量
  • 文章访问数:  802
  • HTML全文浏览量:  70
  • PDF下载量:  248
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-01-15
  • 刊出日期:  2019-03-05

Geohash-Trees:一种用于组织大规模轨迹的自适应索引

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

    国家自然科学基金 41471374

    国家自然科学基金 41001296

    作者简介:

    向隆刚, 博士, 教授, 主要研究方向为轨迹数据处理与分析。geoxlg@whu.edu.cn

    通讯作者: 高萌, 硕士。gmshepard@whu.edu.cn
  • 中图分类号: P208

摘要: 蕴含着挖掘价值的轨迹数据分布在世界各地,且规模庞大。如何在全球范围内组织轨迹数据并支持高效范围查询成为难题。一种自适应索引组织框架被提出来管理查询全球范围大规模轨迹数据集,其基本思想为:针对不同轨迹数据集,根据Geohash编码,生成层数最深的Geohash格网覆盖住整个轨迹数据集范围;以格网作为根节点,生成Geohash-Trees;为了加快查询定位到对应索引,根据编码前缀相同的特点设计了字典查询树。Geohash-Trees是一种基于格网划分的空间索引,它能够根据轨迹密度自适应使用多种剖分策略划分空间,提高范围查询效率。为了支持索引动态更新,设计了增量插入和更新算法。同时,该索引被移植到商用数据库Oracle中,利用数据库性能高效管理查询轨迹数据。实验结果表明,该方法在范围查询以及占用空间等方面明显优于Oracle内置的R树索引。

English Abstract

向隆刚, 高萌, 王德浩, 龚健雅. Geohash-Trees:一种用于组织大规模轨迹的自适应索引[J]. 武汉大学学报 ● 信息科学版, 2019, 44(3): 436-442. doi: 10.13203/j.whugis20160523
引用本文: 向隆刚, 高萌, 王德浩, 龚健雅. Geohash-Trees:一种用于组织大规模轨迹的自适应索引[J]. 武汉大学学报 ● 信息科学版, 2019, 44(3): 436-442. doi: 10.13203/j.whugis20160523
XIANG Longgang, GAO Meng, WANG Dehao, GONG Jianya. Geohash-Trees: An Adaptive Index Which can Organize Large-Scale Trajectories[J]. Geomatics and Information Science of Wuhan University, 2019, 44(3): 436-442. doi: 10.13203/j.whugis20160523
Citation: XIANG Longgang, GAO Meng, WANG Dehao, GONG Jianya. Geohash-Trees: An Adaptive Index Which can Organize Large-Scale Trajectories[J]. Geomatics and Information Science of Wuhan University, 2019, 44(3): 436-442. doi: 10.13203/j.whugis20160523
  • 随着GPS技术的精进和完善以及移动通信技术的迅猛发展,越来越多的移动设备中都携带GPS芯片组。技术的进步和硬件的普及为基于位置的服务(location-based service, LBS)[1]打下了良好的基础。移动定位应用记录的大量轨迹数据有着非比寻常的挖掘价值。轨迹数据记录的是人或物体移动过程,通过轨迹数据挖掘分析能够得出一系列有价值的结论。例如, 对人轨迹进行分析能得出有关个人的行为模式[2]等。这些结论能够有效应用于复杂的社会应用,如智能交通决策[3]和智慧城市建设[4]

    一方面,轨迹数据集包含的轨迹可能分布在不同的地理范围。世界上有很多网站可以让用户上传任意轨迹,例如Wikiloc (https://www.wikiloc.com/)。轨迹的分布可以来自全世界。另一方面,轨迹数据集在空间分布上是稀疏且不均匀的,轨迹密度和人口分布与活动等息息相关,即存在天然的空间分异性[5]。如何对大规模、多尺度、不均匀分布的轨迹数据进行组织管理以及高效范围查询成为亟待解决的难题,对现有的数据库索引技术提出了严峻的挑战。

    近年来,轨迹数据索引的研究可以分为数据划分和空间划分两类。数据划分一般采用二维空间索引R树的变种和扩展。例如,文献[6]提出的3D R-Tree针对移动对象有时序性的特点,将R树扩展成高维索引;文献[7]对3D R-Tree的索引对象以及查询处理算法进行了改进,提高了查询效率;文献[8]设计了STR-Tree和TB-Tree,前者改写了R树的插入和分裂算法,使其更适用于轨迹数据存储,后者在插入新轨迹时要求叶节点存储的轨迹片段属于同一轨迹;文献[9]提出了HBSTR索引,改变时空R树插入策略,以节点插入。这类方法大多时空查询能力良好,但是索引结构复杂,更新维护效率较差。空间划分方式一般利用B+树索引、格网或者四叉树[10]去划分空间,将轨迹分割成轨迹片段,每个空间管理划分到此空间的轨迹片段。例如,文献[11]提出的B+-Tree利用空间填充曲线将移动对象线性化,再利用B+树对线性元组进行索引;文献[12]提出的SETI将空间格网化,每个格网利用R树管理轨迹数据;文献[13]提出利用不同码长的Geohash[14]编码格网近似表达轨迹,将二维轨迹查询降维成一维的Geohash编码查询,提高效率;文献[15]提出了一种混合索引,一方面根据数据空间分布建立索引,另一方面根据历史查询数据聚类建立查询模型,二者通过Geohash编码格网进行关联;文献[16]提出的CSE-Tree利用四叉树去划分空间,每个分区根据结束和开始时间戳分别建立B+树索引;文献[17]采用一种动态的四叉树索引去划分空间,能根据轨迹的密集程度自适应地分割空间。这类方法优点在于构建索引、查询效率高,缺点在于需要将轨迹分为片段来管理,集成到现有的空间数据库中很困难。另外,如果用户想得到感兴趣完整的轨迹信息,还需将轨迹片段合成一段完整的轨迹,加大了查询难度。

    基于现有研究状况,本文面向对象-关系数据库,提出了一种利用Geohash编码技术的框架来组织管理多尺度、大规模、大范围的轨迹数据集。该框架利用Geohash编码生成的格网覆盖不同的轨迹数据集,以这些格网作为根节点,生成Geohash-Trees。该索引考虑到轨迹数据的空间分异性,设计了多种空间划分方式,根据轨迹的密度自适应地划分空间。与四叉树索引不同的地方有两点:(1)自适应空间划分,增加了查询的命中率,提高了查询的效率;(2)轨迹数据不会拆分成轨迹片段,Geohash-Trees索引的是完整轨迹在轨迹数据库中的ID,用户可以提取到完整的轨迹信息而不是轨迹片段。

    • Geohash-Trees自适应索引采用的是Geohash地理编码格式。这种编码方式是将二维经纬度转化为一维字符串,具体原理是沿着经纬度方向交替二分全球表面,利用二进制来表示划分结果,将二进制串用32进制编码方式进行编码。

      Geohash具有3个特点:(1)全球唯一性。通过Geohash划分出来的区域有且只有全球唯一的空间区域与之对应。(2)递归性。同一区域不同层级的编码前缀相同,编码越长,表示的范围越小、越精确。(3)编码的一维性。二维经纬度用一维字符串来表示。降维处理有利于进行检索,提升查询速度。基于以上特点,Geohash广泛应用于邻近点查询[18]、面数据查询等[19]

      图 1展示的是索引的框架。框架主要分为存储管理模块、增量更新模块以及查询引擎模块3个部分。用户通过查询引擎模块进行轨迹的范围查询。增量更新模块是用来支持索引增量更新功能。存储管理模块主要有字典查找树[20]、Geohash-Trees以及轨迹数据库。

      图  1  Geohash-Trees自适应索引框架

      Figure 1.  Framework of Geohash-Trees Index

      对导入的每个轨迹数据集都通过Geohash编码生成格网来覆盖轨迹数据集所在的兴趣区域,将格网作为根节点,建立Geohash-Trees。为了快速定位到对应索引进行查询,根据Geohash编码前缀相同等特点,建立了字典查找树来管理对应索引根节点入口地址。字典查找树是一种以空间换取时间的树形结构,主要优点是利用字符串公共前缀来降低查询时间开销。字典树作为一种经典的数据结构不在此赘述。

      Geohash-Trees索引的项是完整轨迹在数据库中的ID。为了解决轨迹稀疏性问题,该索引会随着轨迹的分布自适应划分。单元不仅可能会四分为子单元,也可能横向或纵向二分为子单元。因此,非叶节点的孩子可能为2或4个。下层空间范围可能是上层空间范围的横(纵)向1/2以及1/4。根节点将覆盖兴趣区域的格网作为键,指向子节点。其他节点根据轨迹分布自适应划分这些格网。将叶子节点层数设为0,非叶子节点层数为自身到达叶子节点的最长路径。

    • 查询存在筛选以及遍历求精两个过程。二者时间长短和单元分裂有关。如果一个单元分裂,叶子节点数目和树高度都会增加,导致范围查询时间增加。另一方面,搜索空间会减少,筛选出来的候选轨迹集也随之减少。单元分裂越多,筛选代价越高,遍历求精代价越低。因此,设计的单元分裂条件与规则要在筛选时间和遍历求精代价之间找一个平衡点,使总代价最小。

      随着轨迹不断被导入,单元中存储的轨迹数目越来越多,当一个单元中轨迹数目达到一个阈值(P-Threshold)时,单元准备分裂。P-Threshold的大小与文件系统的page大小有关(NTFS系统page大小默认为4 096字节)。同时,单元不能无限分裂下去,无限分裂会增加树的高度,使树的结构变得复杂,搜索树节点变得困难。因此,当单元分裂到设置的最小值时,不会再进行分裂操作。

      大型轨迹数据集在空间分布上一般是不均匀的,呈一种偏态分布[21]。大部分轨迹集中于人口密集区域(例如市中心、热门商业区域),而偏远区域(例如郊区、森林)轨迹分布较为稀疏。轨迹分布与人口分布和活动相关,呈现空间分异性。因此,考虑根据轨迹分布的密度来自适性划分空间,能够有效减少搜索空间,提高查询效率。假设某个单元被均匀四分,子单元填充顺序遵循Z字形。一条轨迹可能会与这4个子单元中的一个或者几个相交,也可能完全不相交。根据轨迹和单元相交情况可以得出16种可能,具体情况见图 2。这16种相交情况称为轨迹的空间类型,可用4位整数表示:第k位代表第k个子单元是否与轨迹相交,相交为1,不相交为0。例如,如果一条轨迹只与子单元2和子单元4相交,那么该轨迹的空间类型被表示为(0101)2=(5)10,它被简称为type-5。相应地,type-0的轨迹意味着它不与任何子单元相交。

      图  2  轨迹-单元之间的相交情况以及编码

      Figure 2.  Trajectory-Cell Spatial-Type and Their Codes

      轨迹与单元之间的常见情况如下:如果大部分轨迹属于type-15,则单元并不会分裂。此种情况下分裂,查询空间并不会缩小。然而,如果大部分轨迹属于type-1,分裂有助于缩小查询空间,变为原来的1/4,此种情况就适合分裂。基于以上事实,本文设计了3种分裂规则:

      1) 若(α1+α2+α4+α6+α8+α9)/αvΔsup,单元四分。

      2) 若(α5+α10)/αv>Δsup,单元纵向二分。

      3) 若(α3+α12)/αv>Δsup,单元横向二分。

      其中,αk代表对应空间类型的轨迹数目;αv是除了type-0以外的所有轨迹数目;Δsup是单元分裂策略阈值(例如0.5)。

      除了传统四分策略,本文还设计了另外两种更好的分裂策略:横向或者纵向二分。考虑到type-5或者type-10轨迹,虽然四分策略能够缩小查询空间,但是纵向二分策略远比四分好。四分策略会比纵向二分策略多引进节点,导致更复杂的结构。

    • 为了保证Geohash-Trees能够进行增量更新,索引生成算法由两部分组成:(1)初始化兴趣区域的Geohash-Trees;(2)轨迹逐个导入,进行索引更新。

      树初始化的核心思想是计算合适的Geohash格网作为索引的根节点。具体过程为:(1)根据编码规则去递归搜索至多4块格网(一般来说格网数目为1块、2块或者4块)来覆盖兴趣区域,同时保证这些格网所在层数最深;(2)每个搜索出来的格网还要进行遍历求精,递归检查该格网的子格网是否覆盖兴趣区域,直到不满足条件,返回当前子格网,取代原先搜索出来的格网。因此,根节点中的格网可能不是来自同一Geohash层。根节点将每个返回的格网作为键,指向空的叶子节点。

      索引自顶向下生成算法的主要思想是采用自顶向下策略来插入增量。具体步骤如下:

      1) 如果轨迹信息被接收,将它加入原始轨迹数据库。

      2) 开始建立Geohash-Trees。如果节点为根节点或者叶子节点,将轨迹ID加入该节点。计算该轨迹和该节点的4个子节点的相交关系,更新节点数据统计,也就是空间类型。如果节点的轨迹数量在阈值以下,则不用分裂。如果超过则分裂。满足分裂条件1,节点单元四分;满足分裂条件2,节点单元纵向二分;满足分裂条件3,节点单元横向二分。分裂的工作主要是创建空节点,例如四分就创建4个。然后将轨迹ID加入对应节点,并计算空间类型。最后检测该节点是否还满足分裂条件,不满足则合并节点。

      3) 如果节点为中间节点,重复执行第2步,直到遇到叶子节点。

    • 索引更新算法主要包括轨迹数据删除和修改。修改可看作先删除旧版本轨迹,再插入新版本轨迹,这个过程与R树索引修改类似。而对于删除算法而言,类似于插入算法,只用在插入算法的基础上修改以下两点:

      1) 算法第2步中节点加入轨迹ID,改为删除,且更新节点统计数据,以减少对应空间类型的数量。

      2) 如果叶子节点为空,或者非叶子节点的子节点被删除,则从树中剔除这些节点。显然,在算法第2步可以加上对应步骤。

    • 在成熟的空间数据库中,管理轨迹数据并未采用学术界的索引,而是采用R树索引。Geohash编码的一维性易于管理。因此,本文将索引移植到Oracle数据库。自适应索引可以用表来表示,每个节点也就是表中的一条记录,另外原始轨迹数据存入另一张表。为了形象说明Geohash-Trees在数据库中的情况,将GeoLife[22-24]轨迹数据集导入数据库,建立了索引。图 3是北京市海淀区清华大学附近区域的索引结构,图 4是该区域自适应索引可视化的情况。图 3中有7个非叶子节点,12个叶子节点。非叶子节点表中字段Types表示该节点如何分裂,字段Statistics记录3种分裂条件计算出来的分数,字段Poin-ters指向子节点。叶子节点表中字段TrajIDList存储的是轨迹ID集合。结合图 3图 4,可以看出非叶子节点是如何进行空间划分的。将此区域的轨迹数据进行了最邻近指数分析。当显著水平α=0.05时,Z远小于-1.645,则该区域轨迹数据空间聚集性模式是显著的,存在着空间分异性。

      图  3  Geohash-Trees扁平化实现

      Figure 3.  Flatted Geohash-Trees

      图  4  Geohash-Trees可视化实例

      Figure 4.  Example of Geohash-Trees Visualization

    • 本文对Geohash-Trees自适应索引进行了测试。索引结构从索引插入的时间、索引占用空间大小以及索引查询时间3个方面来进行评估和比较。本文选取的比较对象是Oracle中内置的R树索引。两种索引都是基于Oracle实现的,本文在Oracle上部署了Geohash-Trees自适应索引。

      实验软件环境为Windows 7 64位操作系统以及Oracle 12c数据库,硬件环境为3.10 GHz Intel Core i3-2100 CPU,8 GB内存,931 GB 7200RPM硬盘驱动器。

      实验数据来自于OpenStreetMap网站,位于德国的32 766条GPS轨迹,数据大小约11.0 GB。空间范围[lonmin, latmin, lonmax, latmax]为[5.72°, 46.55°, 14.35°, 54.58°]。

    • 目前Geohash-Trees自适应索引只有增量建立一种构建方式。整个索引建立时间将近4 h,而Oracle数据库自带R树索引建立时间远小于该索引建立时间。在实际情况中,索引只需建立一次即可。如果有新的轨迹数据,则通过增量建立方式来更新维护索引。该索引插入一条轨迹平均时间为486.25 ms,和R树插入时间相差无几。

      索引占用空间方面,Geohash-Trees自适应索引所占空间为2.1 MB,R树索引所占空间为3 MB。这说明该索引更节省空间。

    • 实验主要围绕空间范围查询设计,选取范围方法是在德国范围随意取一点作为查询矩形的左上角,分别生成0.01°×0.01°、0.1°×0.1°、1°×1°、2°×2°、3°×3°、4°×4°、5°×5°范围的查询矩形,记为查询范围1、2、3、4、5、6、7。实验次数是500次。查询时间统计分为两部分:(1)索引筛选时间,(2)索引遍历求精时间。二者记录的是500次查询的平均时间。图 5展示的是实验结果。

      图  5  范围查询时间对比

      Figure 5.  Comparison of Range Query Performance

      图 5(a)展示的是索引筛选时间对比,Geohash-Trees自适应索引筛选时间远小于R树索引,并且随着查询范围扩大,筛选时间也只是缓慢增加。图 5(b)展示的是遍历求精时间对比。由于遍历求精的算法一致,因此遍历求精时间跟候选轨迹数目正相关。由图 5(b)可以看出,Geohash-Trees自适应索引候选轨迹数目少于R树候选轨迹数目,说明其筛选准确率高于R树。图 5(c)展示的是查询时间总和。无论是小范围查询还是大范围查询,Geohash-Trees自适应索引查询效率高于R树索引。

    • 本文提出的Geohash-Trees自适应索引框架能够组织管理检索全球范围大规模轨迹数据集,支持空间范围查询以及增量更新。本文方法在Geohash编码格网之上建立了自适应Geohash-Trees,通过多种分裂策略解决轨迹数据在空间分布上的分异性,从而有效减少查询空间,提高空间范围查询效率。为了快速定位到对应索引,本文还充分利用Geohash编码的特点设计了字典查找树。索引实验结果表明,Geohash-Trees自适应索引在范围查询以及占用空间方面表现明显优于R树索引。同时,本文还将该索引移植到商用数据库Oracle中,有利于索引结构的持久化,便于提取轨迹数据信息。未来,要进一步改善Geohash-Trees自适应索引建立方式,支持批量建立,缩短建立时间,使索引更好地适用于实际应用。

参考文献 (24)

目录

    /

    返回文章
    返回