留言板

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

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

语义关联的轨迹-有向线移动过程模型及查询分析

向隆刚 陶强强 吴涛

向隆刚, 陶强强, 吴涛. 语义关联的轨迹-有向线移动过程模型及查询分析[J]. 武汉大学学报 ● 信息科学版, 2016, 41(8): 1034-1039, 1045. doi: 10.13203/j.whugis20140407
引用本文: 向隆刚, 陶强强, 吴涛. 语义关联的轨迹-有向线移动过程模型及查询分析[J]. 武汉大学学报 ● 信息科学版, 2016, 41(8): 1034-1039, 1045. doi: 10.13203/j.whugis20140407
XIANG Longgang, TAO Qiangqiang, WU Tao. A Semantics Associated Model for Trajectory-directed Line Movement and Its SQL Analysis[J]. Geomatics and Information Science of Wuhan University, 2016, 41(8): 1034-1039, 1045. doi: 10.13203/j.whugis20140407
Citation: XIANG Longgang, TAO Qiangqiang, WU Tao. A Semantics Associated Model for Trajectory-directed Line Movement and Its SQL Analysis[J]. Geomatics and Information Science of Wuhan University, 2016, 41(8): 1034-1039, 1045. doi: 10.13203/j.whugis20140407

语义关联的轨迹-有向线移动过程模型及查询分析

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

国家自然科学基金 41471374

国家自然科学基金 41001296

详细信息
    作者简介:

    向隆刚, 博士, 副教授, 主要从事轨迹数据分析与虚拟地球技术研究。geoxlg@whu.edu.cn

  • 中图分类号: P208

A Semantics Associated Model for Trajectory-directed Line Movement and Its SQL Analysis

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 the fields of trajectory data analysis and virtual globes technologies. E-mail: geoxlg@whu.edu.cn

图(5) / 表(6)
计量
  • 文章访问数:  802
  • HTML全文浏览量:  35
  • PDF下载量:  349
  • 被引次数: 0
出版历程
  • 收稿日期:  2014-09-12
  • 刊出日期:  2016-08-05

语义关联的轨迹-有向线移动过程模型及查询分析

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

    国家自然科学基金 41471374

    国家自然科学基金 41001296

    作者简介:

    向隆刚, 博士, 副教授, 主要从事轨迹数据分析与虚拟地球技术研究。geoxlg@whu.edu.cn

  • 中图分类号: P208

摘要: 轨迹在地理空间中相对一条有向线移动时,可能发生多次进入、离开、穿过、相遇、折返、停留等拓扑关系。针对轨迹-有向线的时空关联特征,提出语义关联的轨迹-有向线移动过程模型:基本思路是将轨迹-有向线的复杂拓扑细节描述为若干局部拓扑关系的组合,从拓扑和语义的角度描述轨迹相对于有向线的移动过程。最后设计并实现了面向该模型的关系模式,并以两类典型请求为例,分析了轨迹-有向线移动过程的纯SQL查询分析技术。

English Abstract

向隆刚, 陶强强, 吴涛. 语义关联的轨迹-有向线移动过程模型及查询分析[J]. 武汉大学学报 ● 信息科学版, 2016, 41(8): 1034-1039, 1045. doi: 10.13203/j.whugis20140407
引用本文: 向隆刚, 陶强强, 吴涛. 语义关联的轨迹-有向线移动过程模型及查询分析[J]. 武汉大学学报 ● 信息科学版, 2016, 41(8): 1034-1039, 1045. doi: 10.13203/j.whugis20140407
XIANG Longgang, TAO Qiangqiang, WU Tao. A Semantics Associated Model for Trajectory-directed Line Movement and Its SQL Analysis[J]. Geomatics and Information Science of Wuhan University, 2016, 41(8): 1034-1039, 1045. doi: 10.13203/j.whugis20140407
Citation: XIANG Longgang, TAO Qiangqiang, WU Tao. A Semantics Associated Model for Trajectory-directed Line Movement and Its SQL Analysis[J]. Geomatics and Information Science of Wuhan University, 2016, 41(8): 1034-1039, 1045. doi: 10.13203/j.whugis20140407
  • 随着GPS技术和通信技术的融合发展,以及位置服务[1](locationt based service,LBS)、移动社交网络[2](mobile social network)、物联网和智慧城市等应用的不断推进,相关行业积累了大量的轨迹数据,并服务于各种研究应用,如移动对象数据库[3, 4]、轨迹数据挖掘[5]等方面。

    本文以轨迹相对于某一有向线的移动过程(简记为轨迹-有向线移动过程)为研究对象,从拓扑和语义角度开展过程建模与查询分析工作。典型的轨迹-有向线移动过程如动物沿河流迁徙、车辆在路网中移动等。与本文研究密切相关的国内外研究成果主要包括两方面,即Stop-move模型和线-线空间关系。Stop-move模型由Spaccapietra等人提出[6],它将轨迹抽象成stop/move序列,易于集成语义标注信息,是当前轨迹数据研究的热点之一[7]。在线-线空间关系方面,Clementini等人建立了线目标间拓扑关系的拓扑不变量[8];Kurata等人提出了HBT(head-body-tail)模型[9],将有向线段分为head、body、tail三部分,以九交矩阵的形式区分出68种不同的拓扑关系;王生生等提出了细节拓扑关系模型(detail of directed line object, DDLO)[10],结合相应的图例,可以精确描述有向线对象多次相交的细节;吴静等人提出了一种有向线间拓扑关系与方向关系的集成表达模型(directed line relation, DLR)[11],能够描述二维空间中有向线对象之间的相对方向关系,还能有效区分相离、内部相交、相切、部分覆盖等拓扑关系,从而表达更复杂的拓扑关系。

    虽然轨迹-有向线在地理空间中的投影属于线-线范畴,但是直接引用线-线空间关系方面的研究成果来建模与分析轨迹-有向线移动过程存在诸多不足之处。例如,DDLO模型需要结合图例才能描述有向线之间的拓扑关系;当两个有向线对象部分重叠时,DLR模型不能区分重叠部分是正向重叠还是逆向重叠;更重要的是,线-线空间关系方面的研究未对轨迹在移动过程中的停留和折返等重要语义信息进行讨论,也很少就拓扑关系在查询分析方面的应用展开分析。

    本文提出了一种语义关联的轨迹-有向线移动过程模型,首先从Stop/move模型出发,以关键点将轨迹分割成若干连续的子轨迹;然后定义子轨迹-有向线拓扑关系矩阵及其语义矩阵,从拓扑和语义角度描述子轨迹-有向线的时空关联关系,进而通过组合推导,表达整条轨迹相对于有向线的移动过程;最后设计并实现了面向该模型的关系模式,并以两类典型请求为例,分析了轨迹-有向线移动过程的纯SQL查询分析技术。

    • 轨迹投影到地理空间后可看作是一种复杂的有向线(可自交、闭合成环、折返等),当指定轨迹相对于某一有向线移动时,两者可能发生多次进入、离开、穿过、相遇、折返和停留等拓扑关系。本文依据这一拓扑关系过程所形成的系列关键点,将轨迹分割成若干连续的子轨迹(可视为从一个关键点移动到另一个关键点的简单有向线对象),通过描述子轨迹-有向线的时空关联关系,进而表达整条轨迹相对于有向线的复杂移动过程。

      关键点记录了轨迹在移动过程中的重要信息。除了起止点外,还存在以下三类关键点。①交点,按交点的维数,轨迹与有向线的交点可划分为0维交点和1维交线段;②停留点,根据Stop/move模型,轨迹在其生命周期内不是一直移动的,某一时刻可能在某处停留,即轨迹停留点(stop);③折返点,轨迹沿有向线移动,可能在某处折返,沿着与原来相反的方向继续移动。

      基于点集拓扑理论[12],Egenhofer等人提出了四交集和九交集模型[13],并用九交模型区分了33种不同的线与线之间的拓扑关系[14]。但是九交模型没有考虑到线的方向性,且无法描述线对象内部的拓扑细节。本文扩展九交模型,定义如下。

      沿轨迹的方向,记子轨迹T的起点为Ts,内部为To,终点为Te。同理,有向线L的起点为Ls,内部为Lo,终点为Le。子轨迹与有向线的拓扑关系可用3×3的九交矩阵来描述,即其中,规定沿有向线的一端为正向。当轨迹沿有向线正向移动时,记ToLo的值为1;反之,当轨迹沿有向线反向移动时,记ToLo的值为-1。图 1展示了一个轨迹-有向线移动过程的例子。图中,→表示轨迹,表示有向线,▲表示轨迹起点,▼表示轨迹终点,△表示有向线起点,▽表示有向线终点,●表示交点,⊗表示停留点,表示既是交点又是停留点,○表示折返点。

      图 1所示,轨迹被分为8段,部分子轨迹与有向线的拓扑关系矩阵为:

      图  1  轨迹-有向线示例

      Figure 1.  Example of Trajectory-directed Line Movement

      不难看出,子轨迹-有向线拓扑关系矩阵的定义是相对于指定的轨迹和有向线而言的。理论上,子轨迹-有向线拓扑关系矩阵共可表达28×3=768种不同的情况。实际上,ToLs=0,ToLe=0,ToLo∈{0,1,-1},Ts(或Te)只能与LsLoLe中的某一个相交,或者都不相交,故共可区分24种有意义的情况。

    • 在语义层面上,轨迹相对于有向线移动时,在关键点处表现出明显的拓扑语义,如轨迹在有向线内部折返;在空间层面上,关键点是前后相邻两条子轨迹的空间连接点。因此,我们借助连接操作,从相邻两条子轨迹与有向线的拓扑关系矩阵中提取出用于表达关键点语义的矩阵,即语义矩阵。语义矩阵从拓扑和语义角度描述了轨迹相对于有向线的移动过程。同时,借助语义矩阵,针对轨迹-有向线移动过程的复杂查询需求可转化为标准的SQL语句,从而扩展了传统轨迹数据的查询分析功能。

      以有向线L为参考,沿轨迹移动方向,记相邻两条子轨迹的前一条子轨迹为Tpre,后一条子轨迹为Tnext,其与L的拓扑关系矩阵分别为MpreMnext,语义矩阵Ms定义在§2.1描述。

    • TpreTnext组合成的子轨迹为PPL的交点为Po。在以Po为中心,无穷小正数ε为半径的邻域内,沿轨迹移动的方向,记P相对于Po的入边为Pin,出边为Pout,则语义矩阵可定义为:

      (1)

      式中,MsMpreMnext经过运算得到:

      (2)

      式中,⊕的运算方法为:设。根据MpreMnext的定义可知a3=b1a2对应语义矩阵的第一行,a3对应第二行,b2对应第三行,则语义矩阵

      理论上,语义矩阵共可表达27×3×3=1 152种不同的情况。实际上,PinLs=0,PinLe=0,PoutLs=0,PoutLe=0,Po只能与LsLoLe中的某一个相交,或者都不相交,故共可表达18种有意义的情况。

    • 轨迹可能从不同的地方进入有向线,如有向线的起点、内部或者终点,然后沿有向线移动。该语义进一步细化,结果见表 1。(表 1表示轨迹,→表示有向线,下同)。

      表 1  进入语义

      Table 1.  Entering Semantics

      起点进入 内部进入 终点进入
      图例
      矩阵

      对于起点进入语义,{TpreTnext}共有8种不同的组合情况,但只能推导出唯一的语义矩阵。同理,内部进入和终点进入的语义矩阵也是唯一的。

    • 轨迹可能先沿有向线移动,然后从不同的地方离开有向线,如有向线的起点、内部或者终点。该语义进一步细化,结果见表 2

      表 2  离开语义

      Table 2.  Leaving Semantics

      起点离开 内部离开 终点离开
      图例
      矩阵

      对于起点离开语义,{TpreTnext}共有8种不同的组合情况,但只能推导出唯一的语义矩阵。同理,内部离开和终点离开的语义矩阵也是唯一的。

    • 轨迹从有向线的某一侧穿过有向线的内部移动到轨迹的另一侧,可认为轨迹穿过有向线。该语义进一步细化,结果见表 3

      表 3  穿过语义

      Table 3.  Crossing Semantics

      图例 矩阵

      对于穿过语义,{TpreTnext}共有16种不同的组合情况,但只能推导出唯一的语义矩阵。

    • 轨迹与有向线可能在不同的地方相遇,如有向线的起点、内部或者终点。该语义进一步细化,结果见表 4

      表 4  相遇语义

      Table 4.  Meeting Semantics

      起点相遇 内部相遇 终点相遇
      图例
      矩阵

      对于起点相遇语义,{TpreTnext}共有16种不同的组合情况,但只能推导出唯一的语义矩阵。同理,内部相遇和终点相遇的语义矩阵也是唯一的。需要指出的是,穿过语义与内部相遇语义的语义矩阵相同,我们将在后续的工作中考虑通过附加方向关系来进一步区分。

    • 轨迹先沿有向线移动,然后在有向线上某处(即折返点)折返,以与原来相反的方向继续沿有向线移动。该语义进一步细化,结果见表 5

      表 5  折返语义

      Table 5.  Retracing Semantics

      起点折返 内部折返 终点折返
      图例
      矩阵

      对于起点折返语义,{TpreTnext}共有4种不同的组合情况,但只能推导出唯一的语义矩阵。同理,内部折返和终点折返的语义矩阵也是唯一的。

    • 轨迹可能在有向线上或有向线外停留。当轨迹在有向线上停留时,可能与上述5类语义混合构成复合语义,此时需借助时间信息来进一步区分。停留语义进一步细化,结果见表 6

      表 6  停留语义

      Table 6.  Stopping Semantics

      线外停留 线上停留
      复合停留 单一停留
      图例
      矩阵

      由上面的讨论可知,对于线外停留语义,{TpreTnext}共有16种不同的组合情况,但只能推导出唯一的语义矩阵。同理,线上停留的语义矩阵也是唯一的,但需要区分两种不同的情况,包括线上复合停留(停留点与交点或折返点重合),即停留语义与其他语义构成复合语义;线上单一停留(停留点不与交点或折返点重合),即仅含停留语义。前者需结合时间信息以进一步区分,而后者借助语义矩阵编码即可直接区分。

    • 组织轨迹-有向线移动过程的表达模型如图 2所示。需要明确的是,该关系模式既可用于自由移动对象,如动物沿河流迁徙,也可用于受限移动对象,如车辆在路网中移动。对于后一种情况,一条有向线通常对应为路网中的一条路(如长安街),但依据用户的感兴趣情况,也可以是一个路段,甚至可以由多条路串接而成,即有向线不一定与路(或路段)是一一对应关系。

      图  2  轨迹-有向线拓扑移动过程模型的关系模式

      Figure 2.  Relational Schema for Topological Model of Trajectory-directed Line Movement

      显然,该关系模式显式表达了轨迹相对于有向线移动过程中形成的拓扑语义,如轨迹从有向线起点进入,在有向线内部停留和折返等,进而可直接利用关系数据库的SQL语句及其处理引擎,查询分析轨迹-有向线移动过程(详见§4)。在图 2的关系模式中,上述语义由语义矩阵承载,存储于Semantics表的Type字段中。为了进一步区分穿过语义与内部相遇语义,我们在Semantics表中设置了SubType字段。此外,在SubTrajectory-DLine表中,StartPointStartTime和StartPointEndTime字段记录子轨迹起点的开始和结束时间,EndPointStartTime和EndPointEndTime字段记录子轨迹终点的开始和结束时间,Type字段存储子轨迹-有向线拓扑关系矩阵;而Trajectory-DLine表的Type字段表达轨迹与有向线的整体拓扑关系矩阵。

      需要注意的是,线上复合停留的区分需结合语义矩阵编码和时间信息,而其他语义借助相应的语义矩阵编码即可区分。

    • 本节将以车辆在路网中的移动为例,通过实验展示本文提出的轨迹-有向线移动过程模型在查询分析方面的应用能力。实验对象为来自于OpenStreetMap(http://www.openstreetmap.org)的北京市路网数据和2008年2月北京市出租车GPS记录,选取代表性的轨迹和感兴趣的有向线(这里特指由多个路段串接而成的路),基于MySQL数据库建立§3中描述的关系模式,如图 3所示。轨迹-有向线移动过程模型的构建并不简单,但是一旦构建完毕,即可持久用于轨迹-有向线移动过程的查询与分析。本文从验证方法可行性的角度出发,采用手动方法建立了轨迹-有向线移动过程的关系模型,但在后续工作中,笔者将研究轨迹数据预处理和轨迹-有向线连接等算法,以大幅提高关系模型的构建效率。在下列实验中,对语义矩阵进行了整数编码。

      图  3  实验数据截图

      Figure 3.  A Screenshot for Experimental Dataset

      针对轨迹-—有向线移动过程,用户希望能够在语义层次上分析其时空拓扑过程,例如,车辆在什么时间驶入了某条路,什么时间在某条路上行驶并有过停留行为,又在什么时间驶离了某条路等。根据用户关注焦点的不同,我们将这类查询请求细分为两类,即关注某一条轨迹的移动过程,以及关注某一条路段的通行情况。

      问题1(Q1):在2008-02-02 21:30:00~2008-02-05 21:00:00时间段内,轨迹1在哪些路内部有过折返行为。

      问题2 (Q2):在2008-02-02 10:00:00~2008-02-06 10:00:00时间段内,轨迹4从哪些路的终点进入,然后从路的起点离开。

      针对类似的问题,本文采用先给出样例查询,然后用文字来分析如何基于我们设计的关系模式来回答这些查询的方法,以说明本文方法的有效性。

      Q1涉及到一种关键点语义,即内部折返语义,而Q2涉及到两种关键点语义——终点进入语义和起点离开语义。以Q2为例,首先借助轨迹ID和终点进入语义、起点离开语义对应的语义矩阵编码(设其编码分别为18、320),即可得到轨迹4从起点离开和从终点进入的两个路段粗选结果集合,取两者的交集,并通过比较子轨迹的序号来判断终点进入和起点离开的先后顺序关系,最后结合时间信息做进一步过滤,从而得到最终结果集。Q2查询语句及结果如图 4所示。

      图  4  查询Q2及结果

      Figure 4.  Query Q2 and Its Results

      问题3 (Q3):在2008-02-04 22:00:00~2008-02-06 22:00:00时间段内,哪些轨迹从起点进入东长安街。

      问题4(Q4):在2008-02-02 12:00:00~2008-02-02 22:00:00时间段内,哪些轨迹从北三环中路的内部进入并且有过停留行为。

      Q3涉及到一种关键点语义,即起点进入语义,而Q4涉及到两种关键点语义,即内部进入语义和停留语义。以Q4为例,首先根据路段名和内部进入语义对应的语义矩阵编码(设其编码为38),即可得到从北三环中路内部进入的轨迹粗选结果集,然后直接基于子轨迹的起止点时间信息,判断轨迹是否在北三环中路上有过停留,取这两者的交集,最后再通过时间信息进一步过滤,从而得到最终的轨迹结果集。Q4查询语句及结果如图 5所示。

      图  5  查询Q4及结果

      Figure 5.  Query Q4 and Its Results

      综上所述,如果按照传统方法处理类似的查询例子,需要执行大量的空间连接与空间运算操作,费时费力,结果不一定准确,而且无法回答轨迹是否在线上停留、折返等查询请求。而基于本文提出的语义关联的轨迹-有向线移动过程模型及其关系模式,即可利用纯SQL语句,从拓扑和语义角度查询分析轨迹相对于有向线的移动过程。虽然本节实验仅用到少量的轨迹与有向线,但考虑到上述关系模式及查询分析均建立在MySQL等成熟的关系数据库及其SQL处理引擎之上,其存储组织能力和查询检索性能在面向大规模轨迹与有向线数据时也是有保障的。

    • 针对轨迹-有向线的时空关联特征,本文建立了语义关联的轨迹-有向线移动过程模型,并设计了相应的关系模式,据此讨论两类典型请求的纯SQL查询处理。本文提出的模型,一方面从拓扑和语义的角度描述了轨迹相对于有向线的移动过程,挖掘了轨迹-有向线移动过程包含的行为和模式;另一方面支持SQL查询处理,用户只需借助业已成熟的SQL技术就能查询分析轨迹-有向线移动过程,无需另外设计专门的查询语言与过程。在后续的研究工作中,我们将考虑结合方向关系以进一步细化表达与分析轨迹-有向线移动过程。

参考文献 (14)

目录

    /

    返回文章
    返回