EN中文

Journal of Geo-information Science >

2023 , Vol. 25 >Issue 1: 63 - 76

DOI: https://doi.org/10.12082/dqxxkx.2023.220145

Adaptive Data Model and Index Structure for Network-constrained Trajectories

  • LUO Yubo , 1, 2 ,
  • CHEN Biyu , 1, 2, *
Expand
  • 1. State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China
  • 2. Geo-Computation Center for Social Sciences, Wuhan University, Wuhan 430079, China
*CHEN Biyu, E-mail:

Received date: 2022-04-02

  Revised date: 2022-04-29

  Online published: 2023-03-25

Supported by

National Key Research and Development Program of China(2021YFB3900900)

Natural Science Foundation of Hubei Province of China(2020CFA054)

The State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing Special Research Funding

Fold

Abstract

An adaptive spatiotemporal data model and a spatiotemporal index structure are proposed to support efficient storage and querying of network-constrained trajectories. The proposed adaptive spatiotemporal data model extends the hierarchical Compressed Linear Reference (CLR) data model by establishing the adaptive route-based linear datum in road network with high-frequency network routes mined from the trajectory dataset. Network-constrained trajectories can be transformed from the link-based linear datum to the adaptive route-based linear datum, and the transformed trajectories consist of fewer sub-entities that can be stored with lower storage capacity. The proposed adaptive spatiotemporal index structure is an extension of the LRS-based index structure, which is constructed based on the adaptive route-based Linear Reference System (LRS). Fewer spatiotemporal sub-entities are saved in the adaptive spatiotemporal index structure, which allows for efficient spatiotemporal querying of network-constrained trajectories. In order to verify the effectiveness of the proposed adaptive data model and index structure, adequate experiments are conducted at the end of this paper using the real open-source T-Drive taxi trajectory dataset and the synthetic trajectory dataset. The experiments take two popular spatiotemporal intersection queries as an example, and the proposed adaptive data model and index structure with the conventional hierarchical CLR data model and the LRS-based spatiotemporal index structure are compared in terms of storage efficiency and query efficiency. The analysis results show that the proposed adaptive data model and index structure can improve storage efficiency by 40% and query efficiency by 50%, which confirms that the proposed method can provide a new solution for the management of network-constrained trajectory data.

Key words： network-constrained trajectories; space-time path; spatiotemporal data model; spatiotemporal index structure; adaptive; frequent pattern mining; compressed linear reference; dual space-time transformation

Cite this article

LUO Yubo , CHEN Biyu . Adaptive Data Model and Index Structure for Network-constrained Trajectories[J]. Journal of Geo-information Science, 2023 , 25(1) : 63 -76 . DOI: 10.12082/dqxxkx.2023.220145

1 引言

精密空间定位诸如北斗导航等位置感知技术推动了社会感知[1]的进步，使得获取海量、多源的空间大数据成为可能[2]，相关基于位置的服务[3]已经成为人们日常出行必不可少的需求。移动性是物理世界中广泛存在的现象，通过对移动对象(Moving Object)的空间位置按时序不间断采样，可以获取高分辨率时空路径(Space-time Path)[4]，又称时空轨迹。时空轨迹大数据蕴含着丰富的模式与规律，对智能交通[5]、城市规划[6]、人类移动性研究[7]等有着重要的意义。
时空轨迹可以分为受限于道路网络的时空轨迹与其他自由空间时空轨迹。其中路网时空轨迹因与城市问题息息相关，是目前的研究热点所在。包括交通工具GNSS(Global Navigation Satellite System)时序定位数据、公共交通刷卡数据等都属于路网时空轨迹的范畴。深入挖掘路网轨迹数据，有利于分析道路交通状态、居民出行规律、城市功能结构等社会问题[8]。对路网轨迹的管理与查询是数据处理与分析的基础[9]，如道路交通状态评估需要从数据库中查询特定时间段内某个空间区域内的轨迹[10-11]。庞大的数据量、动态的时变性、复杂的道路网络给路网轨迹的高效管理与查询带来挑战。路网轨迹数据的管理需要时空数据模型的支撑；路网轨迹数据的查询需要使用索引结构来过滤出符合查询要求的对象[12-13]。
基于道路网络的数据模型是最常用的路网轨迹数据模型，该类模型[14⇓⇓-17]往往以移动对象所关联的路段(Road)或路径(Route)等网络1维线性元素(Linear element)[18]为基本建模单元。以CLR数据模型[16]为例，该模型利用压缩线性参考(Compressed linear reference, CLR)技术实现了3维路网时间地理实体的时空降维，可支持路网时间地理实体以2维空间实体的形式存储于空间数据库中。为了支撑多语义模式的时空查询，Chen等[17]进一步开发了多层CLR数据模型。该多层CLR数据模型可对不同语义网络层上的时间地理实体分别进行建模，也可实现不同层之间实体的转换与查询。然而以上这些模型均将路段或者功能性路径如街道视作建模单元，这类建模单元均为人工设置，对于高动态变化的时空轨迹而言，自适应程度较低，没有考虑时空轨迹在路网的空间分布状态。
面向路网轨迹的索引技术[19⇓⇓⇓⇓⇓⇓-26]往往结合R树[27]的变化以及对路网的适当处理[28-29]。考虑到路网事件一般采用线性参考系统(Linear reference system, LRS)进行定位[30]，一种简单有效的方法是采用两层索引结构对路网轨迹建立索引[20]，即把一个3维的时空查询问题转化为两个维度较低的子问题。其中第一个子问题是对底层2维路网构建索引，第二个子问题是对1维线性元素上的时空轨迹子实体构建索引。较早的FNR-Tree[19]设计为包含一层2维R树索引底层道路网络，与多个1维 R树索引1维路段上的运动轨迹。FNR-Tree的缺点在于其假定移动对象沿着路段做匀速运动，在1维R树中只存储轨迹进入与离开路段的时间间隔，并不支持路段上移动对象速度的改变。针对这个问题，MON-Tree[20]做出了进一步的改进，该索引结构包含两层2维R树分别索引路网与路径上的时空轨迹子实体，并通过哈希表匹配路径ID与指向路径上2维R树的指针。Chen等[17]在此基础上提出了基于LRS的时空索引结构，该时空索引结构以多层CLR时空数据模型为基础，可以对全时空对象建立索引，同时能够实现不同路径语义层之间的跨层查询。FNR-Tree、MON-Tree与基于LRS的时空索引结构对不同线性元素独立构建索引的设计提高了时空查询的效率。然而，以上时空索引结构所定位的线性基准(Linear datum)均为人工设置，如底层基于路段的LRS或基于街道(Street)的LRS[17]等。这些线性基准的建立没有考虑时空轨迹在路网空间的分布状态[31]。
综上所述，现有面向路网轨迹的数据模型与索引结构其线性基准均由人工设置的网络线性元素组成，没有从数据分布的角度考虑网络线性元素所承载的轨迹段数量，造成了线性元素的冗余，影响了存储效率以及查询效率的进一步提升。针对以上问题，本文提出一种面向路网轨迹的自适应数据模型与索引结构。所提出的自适应数据模型基于时空轨迹的路网空间分布状态，建立自适应的线性基准，可减少LRS中线性元素的数量，提高单个线性元素轨迹段的承载量，并提升存储效率。同时所提出的自适应索引结构能够减少从索引中搜索轨迹的次数，提高时空查询效率。

2 基本概念

本节将对本文所涉及到的基本概念进行简要介绍，以描述自适应数据模型与索引结构。一个道路网络由一个有向图 G = ( N , A )表示，包括一组节点 N = n 1 , n 2 , … , n m以及一组有向路段 A = a 1 , a 2 , … , a n。每个路段 a u都包含一组属性，包括唯一标识符 l u，路段长 d u，起点节点 n s和终点节点 n e。一个网络点可由其在路段 a u上的地理坐标 x i , y i表示；因此一个时空网络点 c i = x i , y i , t i可由其地理坐标 x i , y i和时间戳 t i表示。同时，路段 a u上的网络点还可以使用线性参考系统表示为 l u , m i，其中路段标识符 l u是唯一的正整数，线性测量值 m i ∈ ( 0,1 )是路段 a u上的百分比位置；因此一个时空网络点还可以表示为 c i = l u , m i , t i。
路网时空轨迹 T r q由3维 x ,   y ,   t时空间内的一条时空路径 P q表示，如图1所示，其中x和y是空间维度，t是时间维度。时空路径 P q代表了移动对象的运动路径，为 x ,   y ,   t时空间内一条连续的三维折线(LineString)，可由一组3维直线段表示为：
P q = s u , i j , … , s w , m n
式中： P q表示时空路径； s u , i j = c i , c j表示路段 a u上以恒定速度从时空点 c i到时空点 c j的直线运动。时空路径 P q记录了移动对象改变移动速度或方向的所有时空点，如图1所示为时空路径 P q的时空点集合 c o , c 2 , … , c 5 , c d。时空路径 P q在 x , y平面空间中的投影 T q是一组连续的路段，表示为：
T q = a u , … , a w
式中： T q表示时空路径在平面空间的投影； a u表示路网路段。
图1 路网时空路径

Fig. 1 Network space-time path

时空路径是 x ,   y ,   t时空间内复杂的3维元素，不易在现有GIS平台中进行存储和管理。为了解决这一问题，Chen等人[17]提出基于多层LRS的CLR时空数据模型，以支持包括路网时空路径在内的所有网络时间地理实体的存储与管理。在该模型的支持下，3维的路网时空路径可以借助CLR技术表示为 C L R ,   t时空间内的2维元素，并可存储于空间数据库进行管理；3维时空关系可通过GIS平台开源的2维空间操作确定。该多层CLR模型以基于路段的LRS为底层的拓扑线性基准，定义多个基于功能性路径的LRS在同一个拓扑线性基准之上。与基于路段的CLR模型相比，基于功能性路径的CLR模型可以减少路网时空路径中子实体的数量，从而提高存储和查询性能。
如图2所示为面向时空路径的多层CLR模型示意图。在不同LRS层上的时空路径可基于不同的线性基准，借助CLR技术在不同的 C L R ,   t时空间内表达为数量各异的2维折线段。CLR技术是一种对网络时间地理对象实现时空降维的技术。以基于路段的CLR模型为例，如图2(a)所示，路段 a u的标识符 l u是唯一的正整数， m i L是0~1之间的实数，借助基于路段的CLR技术可将 l u和 m i L整合为一个单一的实数 z u , i L，即：
z u , i L = l u + m i L
式中：上标L表示基于路段的CLR模型； z u , i L是2维地理坐标 x i , y i的等效1维表示，可通过动态分割技术[30]进行转换。通过上述基于路段的CLR技术，路段 a u上的时空点 c i = x i , y i ,   t i可在2维 C L R L ,   t时空间内表示为 c i L = ( z u , i L , t i )。因此，基于路段的LRS层上的时空路径可表示为2维 C L R L ,   t时空间内的2维折线段。
图2 多层CLR模型示意

Fig. 2 Schematic of hierarchical CLR data model

以路径为线性基准，在基于路径的LRS层上的时空路径可记录对应路径的语义信息（如街道名），同时在基于路径的 C L R R ,   t时空间内，时空子实体的数量相应地变少。如图2(b)所示，相同的时空路径在基于路径的 C L R R ,   t时空间内由2个折线段组成，而在基于路段的 C L R L ,   t时空间内由3个折线段组成。其中上标R表示基于路径的CLR模型。
基于多层CLR模型中时间地理实体由LRS上一组互不相交的子实体所构成这一独特结构，Chen等[17]提出基于LRS的时空索引结构对包括时空路径在内的所有时间地理实体构建索引。该索引结构能够同时索引时间地理实体以及它们对应的分层网络。时间地理实体集以图层为单位构建索引。对于每一个图层，通过设计一组不同线性元素上的2维R树以对通过同一线性元素的所有子实体构建一个索引，不同线性元素上构建的2维R树将通过每一层网络所保留的拓扑关系进行关联。相较于传统索引结构，基于LRS的索引结构充分考虑了时间地理实体由多个不相交的子实体构建这一独特结构，能够支持全部时间地理实体的索引构建与高效搜索，而且能够实现跨层查询。然而，对于时空路径而言，多层CLR数据模型以及索引结构中的线性基准均为人工规划（包括底层路段基准以及所有顶层功能性路径基准如街道），并没有考虑时空路径的路网空间分布状态，导致多层CLR数据模型以及基于LRS的时空索引结构调节能力不高、自适应程度较低。因此，针对上述不足，本文将提出面向路网时空轨迹的自适应数据模型与索引结构，以支持路网轨迹的高效管理与查询。

3 基于自适应线性基准的CLR数据模型

本节主要介绍基于自适应线性基准的CLR数据模型，简称自适应CLR模型，包括自适应线性基准挖掘与基于自适应路径(Adaptive Route)的LRS构建，以及基于自适应LRS的时空路径转换。
自适应线性基准挖掘的目标在于找出时空路径层内频繁通过的路段组合，即高频路径(High-frequency Route)。根据高频路径重构网络，获得自适应线性基准，并根据基于自适应线性基准的CLR模型转换时空路径，可进一步减少时空路径子实体的数量，减少索引结构中R树的数量，从而减少查询次数以达到优化查询效率的目的。值得注意的是，与基于路段或基于功能性路径的网络不同的是，一个基于自适应路径的网络上，只存在一个时空路径图层，如图3所示，因为时空路径层的空间分布状态决定了自适应网络的结构。
图3 基于自适应线性基准的CLR模型

Fig. 3 CLR data model based on the adaptive linear datum

自适应线性基准的主体，即高频路径，可通过挖掘路段ID序列集的频繁模式得到。如图4(a)所示，时空路径 P q通过的路段组合可表示成为空间序列 S q = l 1 , l 3 , l 5，其中 l u为路段 a u的唯一标识符。时空路径层可通过上述方式生成空间序列集合 R S。随后可采用频繁序列模式挖掘算法生成高频路径。本文采用较为常用的PrefixSpan(Prefix-projected Sequential Pattern Mining)前缀投影序列模式挖掘算法[32]。该算法的总体思路是只检查前缀子序列，将其相应的后缀子序列投影到投影数据库中。在每个投影数据库中，只通过探索局部频繁模式来增长序列模式。通过PrefixSpan算法挖掘出的高频路径之间具有重叠项，本文以高频路径所组成的路段数量为变量对高频路径集进行降序排序，排序较高的高频路径优先建立自适应线性元素，排序较低的高频路径若含有重复路段ID，则以重复路段ID为界打断高频路径，以高频子路径建立自适应线性元素。根据高频路径建立自适应线性元素后，剩余所有路段或其他功能性路径自动成为其余自适应线性元素。如图4(a)所示为时空路径层包括时空路径 P q与 P b，自适应路径 a r 1为经频繁序列模式挖掘算法生成的高频路径，该路径由路段组合 a 1 , a 3 , a 5组成。自适应路径集 a r 1 , a r 2 , a r 3即为以高频路径 a r 1为主体其余路段为辅的自适应线性基准。
图4 自适应CLR模型示意

Fig. 4 Schematic of adaptive CLR data model

基于自适应路径的LRS使用基于自适应线性基准的网络，每条自适应路径都覆盖了底层基于路段的网络中的一组连续路段（仅包含一条路段的路径是路径的特例）。自适应路径与路段的关系以表格的形式存储于数据库中。其中每一条路段 a u对应的自适应路径唯一标识符 b v、于所在自适应路径中的位置序号 I u、于所在自适应路径中的起止线性参考位置 m u , s A R和 m u , e A R、以及于所在自适应路径中的长度占比 L R u均予以记录，以支持时空路径在不同LRS层之间的快速转换。如下所示为路网点从基于路段的LRS中的线性参考位置 m i L，转换至基于自适应路径的LRS中的线性参考位置 m i A R的公式：
m i A R = m u , s A R + m i L m u , e A R - m u , s A R
式中：上标AR表示自适应CLR模型； m u , s A R与 m u , e A R分别是路段 a u的起始节点 n u , s和终止节点 n u , e在基于所在自适应路径的线性参考位置。
采用上述公式，时空点 c i L = z u , i L , t i可从基于路段的 C L R L ,   t时空间内转换至基于自适应路径的 C L R A R ,   t时空间内，表示为 c i A R = z v , i A R , t i，其中 z v , i A R = b v + m i A R。在一条自适应路径上的时空点可按照时间顺序以2维直线段相连形成2维 C L R A R ,   t时空间内的时空路径。如图4(b)所示，采用自适应CLR模型，可将时空路径 P q转换至2维 C L R A R ,   t时空间内，时空路径 P q的子实体数量减少至1，少于基于路段以及基于功能性路径的CLR模型（图2）。同时相邻2条速度一致的轨迹段可进行合并，从而可以减少时空点的存储以达到减少数据存储量的目的。时空路径从基于路段的LRS层转换至自适应LRS层的处理流程如图5所示。该流程包括了自适应线性基准的挖掘，以及基于自适应路径的LRS构建。
图5 时空路径转换流程

Fig. 5 Flowchart of space-time paths transformation

相较于其余基于功能性路径的CLR模型而言，如基于街道的CLR模型，自适应CLR模型可以增加单条路径所承载的轨迹段数量，从而整体上减少时空路径在 C L R ,   t时空间内子实体的数量，减少时空路径在空间数据库中的存储量。

4 基于自适应LRS的时空索引结构

4.1 自适应时空索引结构

基于多层LRS的时空索引结构能够支持不同LRS层间时空路径的快速查询[17]。本节将对该时空索引结构进行扩展，增加基于自适应LRS的时空索引结构，简称自适应索引结构，以支持时空路径的快速检索。其相关类扩展如图6所示。
图6 自适应索引结构

Fig. 6 Adaptive index structure

在自适应索引结构中，对于每个自适应网络，所有自适应路径的路段-路径对应关系保留在索引结构中，用于快速对不同LRS层之间的时空路径进行转换；每条自适应路径保留了经过该路径的时空路径数量，以显示该条自适应路径的频繁通行程度；一个自适应网络只能构建单个时空路径层的索引；对于单个时空路径图层，构建一组不同自适应路径上的2维R树以对通过同一自适应路径的所有子实体建立索引，不同自适应路径上构建的2维R树将通过自适应网络所保留的拓扑关系进行关联。相较于基于功能性路径的索引结构，自适应索引结构所存储的时空路径子实体更少，2维R树的数量更少，能支持更高效率的时空查询。
通过以上设计，所扩展的自适应索引结构能够充分考虑不同时空路径图层中时空路径群的空间分布状态，结合自适应CLR模型，构建出合理的时空索引结构，支持特定时空路径层的高效时空查询。

4.2 时空查询

使用自适应索引结构，可以高效进行时空查询，包括时空窗口-时空路径相交查询以及时空路径-时空路径相交查询等常见查询类型。时空窗口-时空路径相交查询可以检索特定时间段内某个空间区域内的所有个体，其检索结果可支持诸如地区交通流量监控等决策与管理；时空路径-时空路径相交查询可以检索与输入时空路径时空相交的所有个体，其检索结果可支持诸如流行病学调查等时空追踪与分析。本小节主要介绍如何基于自适应索引结构，实现上述时空相交查询。
（1）时空窗口-时空路径相交查询
首先定义时空窗口-时空路径相交查询：给定空间窗口 W = ( x 1 , x 2 , y 1 , y 2 )，和时间段 [ t o , t d ]，找到所有在 t o到 t d的时间段内与空间区域 W相交的时空路径。该查询可通过4个步骤实现：① 空间查询。通过自适应索引结构中对路网构建的索引，快速检索最小包围盒(Minimum Bounding Box, MBB)与空间区域 W相交的路径集 r u , … , r v；通过空间相交操作过滤路径集并确定每个路径的线性相交区间 z u , i R , z u , j R , … , z v , i R , z v , j R；② 时空窗口定义。时空窗口由 C L R R , t时空间内一组时空矩形 O u R , … , O v R组成。每个时空矩形 O u R由每个线性相交区间上的4个控制点 c i R , - = z u , i R , t o , c i R , + = z u , i R , t d , c j R , + = z u , j R , t d , c j R , - = z u , j R , t o确定；③ 时空路径检索。对于每一个输入时空矩形 O u R，其最小包围盒 M B B o , u R作为输入，从存储在路径 r u上的R树中进行检索。检索结果为最小包围盒 M B B b , u R与 M B B o , u R相交的时空路径子实体 E b , u R；④ 时空路径过滤。对上一步检索结果进行过滤，即确认时空矩形 O u R与时空路径子实体 E b , u R的时空相交关系。该步骤可基于时空对偶变换(the dual space-time transformation)实现，具体实现细节将在下一节展开阐述。通过对每个输入时空矩形进行R树搜索，可以得到一组与时空窗口相交的时空路径，至此完成时空窗口-时空路径相交查询。
（2）时空路径-时空路径相交查询
首先定义时空路径-时空路径相交查询：给定时空路径 P q，查找所有与 P q时空相交的时空路径。该查询可通过2个步骤实现：① 时空路径检索。时空路径 P q由一组时空路径子实体 E q , u R , … , E q , v R组成，对于每一个输入子实体 E q , u R，其最小包围盒 M B B q , u R作为输入，从存储在路径 r u上的R树中进行检索。检索结果为最小包围盒 M B B b , u R与 M B B q , u R相交的子实体 E b , u R；② 时空路径过滤。对上一步检索结果进行过滤，即确认子实体 E q , u R与 E b , u R的时空相交关系。该步骤可基于时空对偶变换实现，具体实现细节将在下一节展开阐述。通过对每个输入时空路径子实体 E q , u R进行R树搜索，可以得到一组与时空路径 P q相交的时空路径，至此完成时空路径-时空路径相交查询。上述查询步骤同样适用于基于路段的LRS层上的时空路径，因路段可以视作是路径的一种特例。

4.3 基于时空对偶变换的时空相交操作

本节简要介绍如何通过使用一维情况下的对偶变换，以直观的方式解决 C L R R , t时空间内时空实体的相交判定。方程为 C L R R t = v t + a的一条轨迹线 p R可映射至对偶空间中的一个点 p * = ( v ,   a )。该对偶空间中其中一轴代表该轨迹线的速度 v，另一轴是该轨迹线的截距 a。类似地，原始空间中的一个点 c R = ( t ,   C L R R )可映射至对偶空间中的一条直线 c *，其方程为 a v = - t v + C L R R。对偶变换的一个重要属性是它保留了几何图形的上下左右关系，即原始空间内轨迹线 p R与点 c R的上下左右关系，和对偶空间内点 p *与直线 c *的上下左右关系一致。利用上述属性，2维 C L R R , t时空间内时空实体的相交操作，可映射至2维对偶空间 a , v内实现[33]。为直观展示时空路径随时间的动态变化，原始空间中以 C L R R为横轴，时间 t为纵轴；相应地，对偶空间中以 a为横轴，速度 v为纵轴；几何图形间均以左右关系进行描述。
（1）时空矩形-时空路径相交操作
如图7(a)所示，时空路径子实体 E b , u R由多个轨迹段 s b , i j R , … , s b , p k R组成。若轨迹段 s b , i j R的MBB与时空矩形 O u R的MBB相交，则轨迹段 s b , i j R与时空矩形 O u R的相交情况，可通过轨迹段 s b , i j R所在直线 p b , i j R与时空矩形对角线段 k m n R的相交情况判定。而直线 p b , i j R与线段 k m n R的相交情况，可通过直线 p b , i j R与线段 k m n R两个端点 c m R , c n R的左右关系确定。直线 p b , i j R与端点 c m R , c n R之间的左右关系可映射至对偶空间，如图7(b)所示，由轨迹直线 p b , i j R的对偶点 p b , i j *与端点 c m R , c n R的两条对偶直线 c m * , c n *之间的左右关系确定，即：
Q = Q 1 ∧ Q 2 Q 1 = a b , i j * ≥ - t n R v b , i j * + C L R n R Q 2 = a b , i j * ≤ - t m R v b , i j * + C L R m R
式中： Q 1用于判断对偶点 p b , i j * = a b , i j * , v b , i j *是否位于对偶直线 c n *之右，其中 c n *表示为 a = - t n R v + C L R n R； Q 2用于判断对偶点 p b , i j *是否位于对偶直线 c m *之左。若 Q 1与 Q 2均成立，则轨迹直线 p b , i j R位于点 c n R之右以及点 c m R之左，得出轨迹直线 p b , i j R与对角线段 k m n R相交，进一步可得轨迹段 s b , i j R与时空矩形 O u R相交。
图7 基于时空对偶变换的时空矩形-时空路径时空相交操作

Fig. 7 Spatiotemporal intersection operation between space-time rectangle and space-time path based on the
dual space-time transformation

（2）时空路径-时空路径相交操作
如图8(a)所示，时空路径子实体 E b , u R由多个轨迹段 s b , i j R , … , s b , p k R组成， E q , u R由 s q , i j R , … , s q , p k R组成，任意2个轨迹段 s b , i j R与 s q , i j R相交即可判定子实体 E b , u R与 E q , u R相交。若轨迹段 s b , i j R与 s q , i j R的MBB相交，则 s b , i j R与 s q , i j R的相交情况，可通过轨迹段 s b , i j R所在直线 p b , i j R与轨迹段 s q , i j R的相交情况以及轨迹段 s q , i j R所在直线 p b , i j R与轨迹段 s b , i j R的相交情况判定。类似地，直线与线段的相交可通过直线与线段两个端点的左右关系确定，而直线与点的左右关系可进一步映射至对偶空间，如图8(b)与图8(c)所示，由直线的对偶点与点的对偶直线间的左右关系确定。因此，轨迹段 s b , i j R与 s q , i j R的相交情况，可通过以下公式判定：
Q = Q 1 ∧ Q 2 ∧ Q 3 ∧ Q 4 Q 1 = a b , i j * ≥ - t q , i R v b , i j * + C L R q , i R Q 2 = a b , i j * ≤ - t q , j R v b , i j * + C L R q , j R Q 3 = a q , i j * ≥ - t b , i R v q , i j * + C L R b , i R Q 4 = a q , i j * ≤ - t b , j R v q , i j * + C L R b , j R
式中： Q 1用于判断轨迹线 p b , i j R的对偶点 p b , i j * = a b , i j * , v b , i j *是否位于点 c q , i R的对偶直线 c q , i *之右，其中 c q , i *表示为 a = - t q , i R v + C L R q , i R； Q 2用于判断对偶点 p b , i j *是否位于对偶直线 c q , j *之左； Q 3用于判断对偶点 p q , i j * = a q , i j * , v q , i j *是否位于对偶直线 c b , i *之右； Q 4用于判断对偶点 p q , i j *是否位于对偶直线 c b , j *之左。若以上均成立，则轨迹段 s b , i j R与 s q , i j R相交。上述空间相交操作同样适用于基于路段的LRS层上的时空路径，因路段可视作是路径的一种特例。
图8 基于时空对偶变换的时空路径-时空路径时空相交操作

Fig. 8 Spatiotemporal intersection operation between space-time paths based on the dual space-time transformation

5 实验分析

本节对所提出的自适应CLR模型与自适应索引结构的存储以及查询效率进行测试。实验数据包括人工合成的时空轨迹数据集与真实的出租车轨迹数据集。实验软件环境为Windows 10 64位操作系统，硬件环境为3.50 GHz Intel Core E3-1240 CPU, 32 GB 内存。自适应CLR模型与自适应索引结构以及时空查询实验均采用微软Visual C# 编程语言实现。在查询实验中，所有数据均提前加载至内存中，并在内存中进行测试。

5.1 实验数据

实验数据包括两类数据，地点北京。第一类数据是路网数据，北京路网数据摘取于OpenStreetMap网站，包括111 543个节点以及304 434条有向路段，作为自适应CLR数据模型中的底层拓扑网络。第二类数据是时空轨迹数据，时空轨迹数据包括真实时空轨迹数据与人工合成时空轨迹数据集。
真实时空轨迹数据采用北京T-Drive开源出租车轨迹数据集[34]。该数据集包含10 357辆出租车在一周内的轨迹数据。本文选取2008年2月2日至8日18:00—18:30的16 192条轨迹数据进行实验，所有轨迹数据均视为在2月2日这一天收集。采用MDP-MM算法[35]对真实轨迹进行地图匹配，并将匹配后的结果作为单独的时空路径层存储于Oracle数据库中。
人工合成数据集共包括5个时空路径层，每层共有20 000条时空路径。通过设定时空路径的路网路径活动范围，每层时空路径集的空间分布状态均不同。每层时空路径集合成步骤如下：随机组合N条路网路径作为人工合成时空路径的空间运动范围，随后从中随机选择一条路径生成一条时空路径，共生成20 000条时空路径。其中时空路径的起始时间为2008年2月2日18点，时空路径于每条路段假定为匀速运动，其速度为一个小于12 m/s大于5 m/s的随机值。如表1所示，N的大小决定了该层时空路径层的空间集中程度，N的取值包括 10 ,   5000,10   000,15   000 ,   20   000共5个，分别对应5层人工合成时空轨迹数据集。
表1 实验数据说明

Tab. 1 Description of trajectory data

数据来源 数据名称 空间路径数量/N 时空轨迹数量/个 时间段
T-Drive数据集 TD - 16 192 18:00 — 18:30
人工合成数据集 AD1 10 20 000 18:00 —
AD2 5000 20 000 18:00 —
AD3 10 000 20 000 18:00 —
AD4 15 000 20 000 18:00 —
AD5 50 000 20 000 18:00 —

5.2 存储性能分析

本小节分析所提出的自适应CLR模型的存储性能。图9显示了使用不同CLR技术的时空路径所需的存储空间：基于底层路段的CLR模型、基于顶层功能性路径（以街道为例）的CLR模型、以及自适应CLR模型。
图9 不同数据集在不同CLR数据模型下的存储空间对比

Fig. 9 Comparison of storage requirement of different data sets under different CLR data models

与基于底层道路的CLR模型相比，基于街道的CLR模型具有明显的存储优势。例如， z L , t时空间中基于底层道路的数据模型需要20.75 MB来存储真实TD数据集。通过将这些时空路径转换到 z R , t时空间，基于街道的CLR模型可以减少约33%的存储空间，达到13.97 MB。对于人工合成的AD数据集，也能达到平均约2%的存储性能提升。存储效率的原因在于，街道通常覆盖了基于路段的底层网络中许多连续路段。因此，在基于路段的CLR模型中，同一街道上的几个子实体在基于街道的CLR模型中被合并为一个子实体[17]。与基于街道的CLR模型相比，自适应CLR模型进一步提高了时空路径的存储空间效率。例如，通过将TD数据集转换至 z A R , t时空间，自适应CLR模型进一步减少了约40%的存储空间，达到8.36 MB。对于人工合成的AD数据集，也能达到平均约3%的存储效率提升。存储效率进一步提升的原因在于，相较于街道或其他功能性路径，自适应路径能够合并更多的路段上的子实体，从而减少存储量。

5.3 查询效率分析

本小节分析基于自适应索引结构的时空查询性能，包括时空窗口-时空路径相交查询以及时空路径-时空路径相交查询。所有查询时间均为运行10次的平均值。
图10显示了使用合成AD数据集的时空窗口-时空路径相交查询的效率。所有实验中，输入的空间窗口设置为覆盖整个路网；输入的时间窗口起始时间设定为18点，时间段的长度设置为30 min。在5个不同的合成AD数据集中，自适应索引结构均显示出了显著的查询优势。例如，在AD2数据集中，基于路段的时空索引结构需要19.65 s完成 20 000条时空路径的查询，基于街道的时空索引结构仍然需要12.53 s，而自适应索引结构仅需要 6.26 s即可完成时空窗口-时空路径查询，相比于基于街道的时空索引结构提高了约50%。
图10 AD数据集在不同时空索引结构下时空窗口-时空路径相交查询时间对比

Fig. 10 Comparison of query time of spatiotemporal window-path intersection query for AD dataset with different spatiotemporal index structures

自适应索引结构能够提升查询效率的主要原因在于其建立在基于自适应线性基准的CLR技术之上，考虑了时空路径的空间分布状态，提高了单条路网路径上轨迹段的承载量，减少了时空索引结构中子实体数量，因此减少了从索引结构中进行查询的次数，提高了查询性能。例如，如表2所示，在AD2数据集中，当输入空间窗口设置为覆盖整个路网、输入时间窗口设置为30 min时，基于路段的时空索引结构共包含1 060 371个时空路径子实体，需要在不同路段对应的R树中进行9246次搜索；基于街道的时空索引结构共包含672 471个时空路径子实体，子实体数量减少了37%，需要在不同路径对应的R树中进行5424次搜索，搜索次数减少了41%；自适应索引结构仅包含317 440个时空路径子实体，子实体数量进一步减少了53%，需要在不同自适应路径对应的R树中进行3158次搜索，搜索次数进一步减少了42%。
表2 AD数据集在不同时空索引结构下时空窗口-时空路径相交查询效率对比

Tab. 2 Comparison of query efficiency of spatiotemporal window-path intersection query for AD dataset under different spatiotemporal index structures

数据集 基于路段的
时空索引结构		 基于街道的
时空索引结构		 自适应
时空索引结构
时空路径
子实体数量/个		 搜索次数/次 时空路径
子实体数量/个		 搜索次数/次 时空路径
子实体数量		 搜索次数/次
AD1 1 125 037 415 670 589 232 218 220 19
AD2 1 060 371 9246 672 471 5424 317 440 3158
AD3 1 057 270 10 149 669 139 5883 321 793 3893
AD4 1 058 169 10 280 671 203 5925 322 768 4089
AD5 1 055 623 10 409 670 116 5993 338 253 4301
图11显示了采用真实TD数据集的时空窗口-时空路径相交查询的效率。其中空间窗口长与宽均设置为整个路网最小包围盒长与宽的十分之二；时间窗口的起始时间设定为18点，时间段的长度设置为30 min。图11显示随着时空路径数量的增加，时空窗口-时空路径的查询效率随之下降。这是因为随着数据量的提升，时空索引结构中含有的子实体数量增加，降低了从索引结构中查询的效率，同时也增加了基于时空对偶变换的时空相交操作的次数，因此降低了整体时空窗口-时空路径相交查询的性能。不同数量的TD数据集中，自适应索引结构的查询效率均优于基于路段以及基于街道的时空索引结构。例如，基于路段的时空索引结构需要1.5 s完成TD数据集16 192条时空路径的查询，基于街道的时空索引结构仍然需要0.93 s，而基于自适应索引结构仅需要0.53 s即可完成时空窗口-时空路径相交查询，效率提升43%。该查询效率的提升原因与图10相同，即所提出的自适应索引结构提高了单条路网路径上轨迹段的承载量，减少了时空索引结构中子实体数量，减少了查询次数，提高了查询性能。
图11 不同轨迹数量下不同索引结构的时空窗口-时空路径相交查询效率对比

Fig. 11 Comparison of query efficiency of spatiotemporal window-path intersection query for different index structures with different trajectories numbers

图12显示了采用真实TD数据集的时空路径-时空路径相交查询的效率。其中16 192条真实TD数据集中的每一条均作为输入以获得平均查询时间。图12显示随着时空路径数量的增加，时空路径-时空路径相交查询的效率也在下降。其原因与图11相同，即随着数据量的提升，时空索引结构中含有的子实体数量增加，降低了从索引结构中查询的效率，同时也增加了基于时空对偶变换的时空相交操作的次数。不同数量的TD数据集中，自适应索引结构的查询效率均优于基于路段以及基于街道的时空索引结构。例如，基于路段的时空索引结构平均需要0.0149 ms完成TD数据集16 192条时空路径的查询，基于街道的时空索引结构平均需要0.01 ms，而基于自适应索引结构仅需要0.0075 ms即可完成时空路径-时空路径相交查询，效率提升25%。该查询效率的提升原因与图11相同，即所提出的自适应索引结构提高了单条路网路径上轨迹段的承载量，减少了时空索引结构中子实体数量，减少了查询次数，提高了查询性能。
图12 不同轨迹数量下不同索引结构的时空路径-时空路径相交查询效率对比

Fig. 12 Comparison of query efficiency of spatiotemporal path-path intersection query for different index structures with different trajectories numbers

6 结论

本文概述了经典路网轨迹数据模型与索引结构，分析得出了经典数据模型与索引结构自适应调节能力低的问题。结合路网轨迹在路网空间的投影为连续的路段组合这一特点，本文首先通过频繁模式挖掘算法获得时空轨迹高频路径，以高频路径为主要线性元素构建自适应线性基准，采用基于自适应线性基准的CLR数据模型对时空轨迹进行建模。其次，本文根据自适应线性基准建立自适应线性参考系统，采用基于自适应线性参考系统的时空索引结构对时空轨迹进行检索，并基于时空对偶变换判定时空2维图形的空间相交关系，实现时空窗口-时空路径相交查询以及时空路径-时空路径相交查询。实验表明：相较于基于功能性路径的CLR数据模型，所提出的自适应数据模型最高能够提升约40%的存储效率；相较于基于功能性路径的时空索引结构，所提出的自适应时空索引结构最高能够提升约50%的查询效率。
综上所述，相较于传统数据模型与索引结构，所提出的自适应数据模型与索引结构能够支持时空轨迹数据以更高的效率进行管理与查询，为后续轨迹数据高效的挖掘与分析奠定了基础，符合大数据时代对数据处理速度的要求。其次，本文以数据自适应的角度对以往轨迹数据模型与索引结构进行了扩展，取得了一定的效果，可为其余经典GIS数据模型的发展提供借鉴思路。与此同时，关于自适应数据模型与时空索引结构还有几点可以深入探讨，比如自适应线性基准的建立可以通过高频路径的聚合重组进行最优化，从而进一步提高存储与查询效率；其次，本文所提出的自适应数据模型与索引结构适用于历史轨迹数据，对于实时扩充的轨迹数据集而言，仍面临着较大的挑战。未来将开展相关研究讨论自适应线性基准的自动更新，以支持轨迹数据的实时高效查询。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
Liu Y, Liu X, Gao S, et al. Social sensing: A new approach to understanding our socioeconomic environments[J]. Annals of the Association of American Geographers, 2015, 105(3):512-530. DOI:10.1080/00045608.2015.1018773

DOI

[2]
刘经南, 方媛, 郭迟, 等. 位置大数据的分析处理研究进展[J]. 武汉大学学报·信息科学版, 2014, 39(4):379-385.

[Liu J N, Fang Y, Guo C, et al. Research progress in location big data analysis[J]. Geomatics and Information Science of Wuhan University, 2014, 39(4):379-385. ] DOI:10.13203/j.whugis20140210

DOI

[3]
龚健雅, 黄文哲, 陈泽强, 等. 全球位置信息叠加协议与位置服务网技术研究进展与展望[J]. 地球信息科学学报, 2022, 24(1):2-16.

DOI

[Gong J Y, Huang W Z, Chen Z Q, et al. Global location information superposition protocol and location-based service network technology: Progress and prospects[J]. Journal of Geo-information Science, 2022, 24(1):2-16. ] DOI:10.12082/dqxxkx.2022.210762

DOI

[4]
Miller H J. A measurement theory for time geography[J]. Geographical Analysis, 2005, 37(1):17-45. DOI:10.1111/j.1538-4632.2005.00575.x

DOI

[5]
Zheng Y, Chen Y, Li Q, et al. Understanding transportation modes based on GPS data for web applications[J]. ACM Transactions on the Web, 2010, 4(1):1-36. DOI:10.1145/1658373.1658374

DOI

[6]
Liu X, Kang C, Gong L, et al. Incorporating spatial interaction patterns in classifying and understanding urban land use[J]. International Journal of Geographical Information Science, 2016, 30(2):334-350. DOI:10.1080/13658816.2015.1086923

DOI

[7]
陆锋, 刘康, 陈洁. 大数据时代的人类移动性研究[J]. 地球信息科学学报, 2014, 16(5):665-672.

DOI

[Lu F, Liu K, Chen J. Research on human mobility in big data era[J]. Journal of Geo-information Science, 2014, 16(5):665-672. ] DOI:10.3724/SP.J.1047.2014.00665

DOI

[8]
吴华意, 黄蕊, 游兰, 等. 出租车轨迹数据挖掘进展[J]. 测绘学报, 2019, 48(11):1341-1356.

[Wu H Y, Huang R, You L, et al. Recent progress in taxi trajectory data mining[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(11):1341-1356. ] DOI:10.11947/j.AGCS.2019.20190210

DOI

[9]
Zheng Y. Trajectory data mining: An overview[J]. ACM Transactions on Intelligent Systems and Technology, 2015, 6(3):1-41. DOI:10.1145/2743025

DOI

[10]
Funke S, Rupp T, Nusser A, et al. PATHFINDER: Storage and indexing of massive trajectory sets[C]. Proceedings of the 16th International Symposium on Spatial and Temporal Databases, 2019:90-99. DOI:10.1145/3340964.3340978

DOI

[11]
Li R, Ruan S, Bao J, et al. Efficient path query processing over massive trajectories on the cloud[J]. IEEE Transactions on Big Data, 2020, 6(1):66-79. DOI:10.1109/TBDATA.2018.2868936

DOI

[12]
De Souza A P R, Renso C, Perego R, et al. MAT-Index: An index for fast multiple aspect trajectory similarity measuring[J]. Transactions in GIS, 2022, 26(2):691-716. DOI:10.1111/tgis.12889

DOI

[13]
Brisaboa N R, Fariña A, Galaktionov D, et al. Improved structures to solve aggregated queries for trips over public transportation networks[J]. Information Sciences, 2022, 584:752-783. DOI:10.1016/j.ins.2021.10.079

DOI

[14]
Vazirgiannis M, Wolfson O. A spatiotemporal model and language for moving objects on road networks[M]. Advances in Spatial and Temporal Databases. Springer-Verlag, Berlin, 2001:20-35.

[15]
陈碧宇, 陈晓玲, 陈慧萍, 等. 网络中移动对象的2维时空数据模型[J]. 测绘学报, 2007, 36(3):329-334.

[Chen B Y, Chen X L, Chen H P, et al. 2-dimentional spatio-temporal data model for moving objects in network[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(3):329-334. ] DOI:10.3321/j.issn:1001-1595.2007.03.015

DOI

[16]
Chen B Y, Yuan H, Li Q, et al. Spatiotemporal data model for network time geographic analysis in the era of big data[J]. International Journal of Geographical Information Science, 2016, 30(6):1041-1071. DOI:10.1080/13658816.2015.1104317

DOI

[17]
Chen B Y, Luo Y B, Jia T, et al. Spatiotemporal data model and index structure for computational time geographical studies[J]. International Journal of Geographical Information Science, 2022, under review.

[18]
Scarponcini P. Generalized model for linear referencing in transportation[J]. GeoInformatica, 2002, 6(1):35-55. DOI:10.1023/A:1013716130838

DOI

[19]
Frentzos E. Indexing objects moving on fixed networks[M]. Advances in Spatial and Temporal Databases. Springer-Verlag, Berlin, 2003:289-305. DOI:10.1007/978-3-540-45072-6_17

DOI

[20]
De Almeida V T, Guting R H. Indexing the trajectories of moving objects in networks[J]. GeoInformatica, 2005, 9(1):33-60. DOI:10.1007/s10707-004-5621-7

DOI

[21]
李国徽, 钟细亚. 一种基于固定网络的移动对象运动轨迹索引模型[J]. 计算机研究与发展, 2006, 43(5):828-833.

[Li G H, Zhong X Y. Indexing moving objects trajectories on fixed networks[J]. Journal of Computer Research and Development, 2006, 43(5):828-833. ] DOI:CNKI:SUN:JFYZ.0.2006-05-008

DOI

[22]
李红军, 唐常杰, 乔少杰, 等. UTR*-Tree受限网络中移动对象不确定轨迹索引模型[J]. 四川大学学报·工程科学版, 2010, 42(2):118-125.

[Li H J, Tang C J, Qiao S J, et al. UTR*-Tree an uncertain trajectories model for indexing moving objects in constrained networks[J]. Journal of Sichuan University·Engineering Science Edition, 2010, 42(2):118-125. ] DOI:10.15961/j.jsuese.2010.02.037

DOI

[23]
林许, 李清泉, 杨必胜. 一种基于道路网的移动对象的位置索引与邻近查询方法[J]. 测绘学报, 2010, 39(3):316-327.

[Lin X, Li Q Q, Yang B S. A moving object index structure and nearest neighbor query method based on road network[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(3):316-327. ] DOI:CNKI:SUN:CHXB.0.2010-03-020

DOI

[24]
丁治明. 一种适合于频繁位置更新的网络受限移动对象轨迹索引[J]. 计算机学报, 2012, 35(7):1448-1461.

[Ding Z M. An index structure for frequently updated network-constrained moving object trajectories[J]. Chinese Journal of Computers, 2012, 35(7):1448-1461. ] DOI:10.3724/SP.J.1016.2012.01448

DOI

[25]
Chen L, Tang Y, Lv M, et al. Partition-based range query for uncertain trajectories in road networks[J]. GeoInformatica, 2015, 19(1):61-84. DOI:10.1007/s10707-014-020 6-6

DOI

[26]
Abbasifard M R, Naderi H, Isfahani Alamdari O. Efficient indexing for past and current position of moving objects on road networks[J]. IEEE Transactions on Intelligent Transportation Systems, 2018, 19(9):2789-2800. DOI:10.1109/TITS.2017.2762425

DOI

[27]
Guttman A. R-trees: A dynamic index structure for spatial searching[J]. ACM SIGMOD Record, 1984, 14(2):47-57. DOI:10.1145/971697.602266

DOI

[28]
Brisaboa N R, Gagie T, Gómez-Brandón A, et al. An index for moving objects with constant-time access to their compressed trajectories[J]. International Journal of Geographical Information Science, 2021, 35(7):1392-1424. DOI:10.1080/13658816.2020.1833015

DOI

[29]
Pelekis N, Theodoridis Y. Mobility database management[M]. Mobility Data Management and Exploration. Springer, New York, 2014:75-99. DOI:10.1007/978-1-4939-0392-4_4

DOI

[30]
Miller H J, Shaw S L. Geographic information systems for transportation: Principles and applications[M]. New York: Oxford University Press, 2001.

[31]
Sandu Popa I, Zeitouni K, Oria V, et al. Indexing in-network trajectory flows[J]. The VLDB Journal, 2011, 20(5):643-669. DOI:10.1007/s00778-011-0236-8

DOI

[32]
Pei J, Han J, Mortazavi-Asl B, et al. PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth[C]. Proceedings 17th International Conference on Data Engineering. 2001:215-224. DOI:10.1109/ICDE.2001.914830

DOI

[33]
Kollios G, Tsotras V J, Gunopulos D. Mobile object indexing[M]. Encyclopediaof GIS. Springer International Publishing, Cham, 2017:1256-1266. DOI:10.1007/978-3-319-17885-1_793

DOI

[34]
Yuan J, Zheng Y, Zhang C, et al. T-drive: Driving directions based on taxi trajectories[C]. Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2010:99-108. DOI:10.1145/1869790.1869807

DOI

[35]
Chen B Y, Yuan H, Li Q, et al. Map-matching algorithm for large-scale low-frequency floating car data[J]. International Journal of Geographical Information Science, 2014, 28(1):22-38. DOI:10.1080/13658816.2013.816427

DOI

Options
Outlines

/

〈 〉