随着GPS设备的广泛应用和位置采集技术的提高, 轨迹数据无处不在.轨迹数据的分析与挖掘可用于对交通情况进行分析、为旅行者推荐最佳的旅游路径、对社会关系或者用户行为进行分析等.原始轨迹数据通常非常庞大, 导致传输、存储和处理的开销非常大.此外, 许多应用并不需要给出高密集度的位置信息^[1].因此, 通常情况下, 在原始轨迹数据传输、存储和处理之前要对其进行压缩.

目前, 大部分的轨迹压缩方法是保留位置的轨迹压缩(position-preserving trajectory compression, PPTC)^[2-9], 主要考虑轨迹的位置信息以决定轨迹点是否保留.该类方法只保留了轨迹的位置信息, 而忽略了轨迹的方向信息, 压缩效果不是十分理想.近期, Long等^[10-11]提出了一种新的压缩轨迹的框架——保留方向的轨迹压缩(direction-preserving trajectory compression, DPTC), 其主要思想是在轨迹压缩过程中, 保留轨迹的方向信息, 同时限制轨迹位置的丢失.从压缩效果上看, DPTC要优于PPTC^[10].本文主要针对保留方向的轨迹压缩方法进行研究.

文献[10]中的DPTC主要研究的是在压缩轨迹的误差不超过可容忍误差的条件下, 其尺度最小化, 被称为最小尺度问题(min-size problem).最小尺度问题只适合于用户对可容忍误差已知的情况.但是, 大多数情况下用户无法明确地指定合理的可容忍误差.文献[11]中的DPTC主要研究的是在给定压缩轨迹尺度的条件下, 压缩误差最小, 被称为最小误差问题(min-error problem), 该问题是最小尺寸问题的一个对偶问题, 无需用户指定可容忍误差^[11].虽然, 最小误差问题提高了压缩后轨迹的可用性, 但是, 当前最小误差问题的解决方法时间代价较大, 且压缩效果不理想, 无法达到用户的需求.为了减小最小误差问题的时间代价, 改善压缩效果, 本文提出了基于排序树索引的轨迹压缩方法, 借助于排序树索引, 在轨迹压缩过程中进行有效的剪枝, 提高了轨迹压缩的时间效率.同时在压缩过程中, 重新定义了对压缩轨迹误差有重要影响的线段误差, 改进了压缩效果.

GPS原始轨迹是由一系列时空采集点构成的集合, T={(p₁, t₁), (p₂, t₂), …, (p_n, t_n)}表示移动对象在时间点t_i(i∈[1, n])位于轨迹点p_i, 其中, t₁＜t₂＜…＜t_n, p_i=(x_i, y_i)是以经纬度表示的轨迹点.轨迹中包含的轨迹点数称为轨迹长度.为表达方便, 本文将移动对象的轨迹表示为T={p₁, p₂, …, p_n}.

定义1 轨迹线段：轨迹点p_i与p_j(1≤i＜j≤n)的连线称为连接p_i与p_j的轨迹线段, 表示为p_ip_j, 其中, p_i称为线段的左端点, p_j称为线段的右端点.

p_i与p_j之间所有连接相邻轨迹点的轨迹线段集合表示为e[p_i:p_j], 即e[p_i:p_j]={p_ip_i+1, p_i+1p_i+2, …, p_j-1p_j}.

例1 在图 1所示的原始轨迹T={p₁, p₂, …, p₁₀}中, 轨迹长度为10, p₁p₂, p₁p₄都是轨迹线段, e[p₁:p₂]={p₁p₂}, e[p₁:p₄]={p₁p₂, p₂p₃, p₃p₄}.

图 1(Fig. 1)

图 1 轨迹线段示例 Fig.1 An example of trajectory segment

定义2 线段方向：给定轨迹T的一条线段p_ip_j, 其方向是在以p_i为原点, 以经度方向为x轴, 以纬度方向为y轴的坐标系中, 沿x轴正方向逆时针旋转到向量的角度, 表示为dir(p_ip_j).

对于线段集合e[p_i:p_j]中所有的线段, 其方向的集合表示为dir[p_i:p_j], 即dir[p_i:p_j]={dir(p_ip_i+1), dir(p_i+1p_i+2), …, dir(p_j-1p_j)}.

例2  图 2中, 线段p₁p₂的方向为dir(p₁p₂)=α, dir[p₁: p₄]={α, β, γ}.

图 2(Fig. 2)

图 2 线段方向示例 Fig.2 Examples of segment directions

对于方向α和β, 其偏差diff(α, β)可描述为从α到β或者从β到α逆时针旋转的最小角度, 即

(1)

定义3 线段误差：线段p_ip_j与原始轨迹T之间的误差ε(p_ip_j)定义为方向dir(p_ip_j)与方向集合dir[p_i:p_j]中所有方向之间角差和的均值, 即

(2)

其中，|dir[p_i: p_j]|为集合dir[p_i: p_j]的基数.

线段误差是决定轨迹点是否保留在压缩轨迹中的重要指标, 本文的上述定义充分体现了轨迹线段偏离原始轨迹的程度, 有助于改善轨迹压缩的效果.

定义4 压缩轨迹误差：给定原始轨迹T={p₁, p₂, …, p_n}, 其压缩轨迹CT={p_s1, p_s2, …, p_sm}(m≤n)的误差ε(CT)定义为CT中所有相邻轨迹点间的线段误差总和, 即

(3)

压缩轨迹中包含的轨迹线段数量与原始轨迹包含的轨迹线段数量的比率称为压缩轨迹尺度.通常, 在进行轨迹压缩时由用户指定最大的压缩轨迹尺度, 称为压缩轨迹尺度阈值, 表示为τ.

本文的目标是对原始GPS轨迹T进行压缩, 在满足尺度要求的前提下, 使得压缩后的轨迹CT与原始轨迹T之间的误差最小.具体的问题定义描述见定义5.

定义5 轨迹压缩：给定原始轨迹T和压缩轨迹尺度阈值τ, 轨迹压缩即是发现T的压缩轨迹CT, 满足:①|CT|≤τ×(n-1)(|CT|表示压缩轨迹CT所包含的轨迹线段数量, n为原始轨迹长度); ② ε(CT)最小.同时满足上述两个条件的轨迹称为最终压缩轨迹.

本文通过建立排序树索引进行轨迹压缩.排序树中每个节点node的结构如图 3所示.

图 3(Fig. 3)

图 3 排序树中节点的结构 Fig.3 Structure of nodes in sort tree

其中, Segment是以轨迹线段p_ip_j表示的节点标志(根节点除外, 其标识为null), 因此, 节点node又称为节点p_ip_j; Parent是指向其父节点的指针, 在基于排序树索引进行轨迹压缩的过程中, 需要依据节点的Parent域向上回溯, 以完成路径搜索过程; Error是节点node中线段Segment的误差ε(Segment), 在基于排序树索引的轨迹压缩中用于计算压缩轨迹误差; Stack是由node的子节点构成的排序栈, 栈中的元素是由其子节点的线段及其误差构成的二元组(Segment, ε(Segment)), 栈中元素从栈顶到栈底按照误差非递减的顺序排序.借助于排序栈可按顺序生成node的子节点, 因此, 该树结构本文称为排序树.

排序树的建立应满足以下条件:

1) 根节点的子节点是以轨迹起点p₁为左端点的线段;

2) 每个节点的子节点按照其排序栈中的顺序建立;

3) 父节点线段的右端点与其子节点线段的左端点相同.

由上述条件可以看出, 当叶节点为轨迹终点时, 从根节点到叶节点的路径将形成一条压缩轨迹.

为了描述基于排序树索引的轨迹压缩过程, 先给出以下定义.

定义6 累计误差：若节点node的线段为p_ip_j, 其累计误差定义为从根节点至节点node的路径上所有线段误差的累加和, 表示为ε^s(node)或ε^s(p_ip_j).

定义7 节点高度：若节点node的线段为p_ip_j, 其高度定义为从根节点至节点node的路径上所有线段的计数.

定义8 最小误差：在当前找到的所有压缩轨迹中, 最小的压缩轨迹误差称为最小误差, 表示为ε₀.

基于排序树索引的轨迹压缩过程主要由以下三步构成:首先, 针对给定的原始轨迹, 创建一个误差空间E; 然后, 根据误差空间E, 为每条线段创建由其子节点及其误差构成的排序栈; 最后, 创建排序树索引, 返回最终压缩轨迹.

1) 创建误差空间E.误差空间E是以每个轨迹点p_k(1≤k≤n)为行、列的上三角矩阵.矩阵元素E[i, j]为线段p_ip_j(1≤i＜j≤n)的误差ε(p_ip_j).

创建误差空间的目的是为了下一步建立子节点排序栈, 误差空间所占用的内存可在子节点排序栈建立之后进行释放.

2) 子节点排序栈的建立.根据误差空间E中的误差对每条线段创建排序栈, 用以存储其子节点线段及其误差, 使其子节点可按照误差大小有序地建立.

根据排序树建立的条件, 对于节点p_ip_j, 其子节点是以p_j为左端点的线段, 其子节点排序栈如图 4所示.

图 4(Fig. 4)

图 4 排序树节点pipj的子节点排序栈 Fig.4 Child-node sort stack of node pipj in sort tree

其中, j＜j₁, j₂, …, j_m≤n且ε(p_jp_j1)≤ε(p_jp_j2)≤…≤ε(p_jp_jm).

特别地, 根节点的排序栈存储的是以轨迹起点p₁为左端点的线段及其误差.

3) 排序树索引的创建.创建排序树的过程即是发现最终压缩轨迹的过程.以排序树为索引, 进行轨迹压缩的步骤为

步骤1 初始化根节点, 其数据域Segment, Parent, Error和Stack分别初始化为Null, Null, 0和由以轨迹起点为左端点的线段及其误差构成的排序栈, 并将根节点作为当前节点node.

步骤2 当前节点node的排序栈不为空时, 弹出其栈顶, 建立node的子节点child.若子节点child中的线段不为p_ip_n(其中, i＜n, p_n为原始轨迹终点), 则以child作为当前节点node, 重复执行步骤2;否则, 若子节点child中的线段为p_ip_n, 则根节点至child的路径形成一条压缩轨迹, 此时, 需要进行以下处理:

① 计算累计误差ε^s(child);

② 将最小误差ε₀更新为min(ε₀, ε^s(child));

③ 继续以node为当前节点, 重复步骤2.

步骤3 若当前节点node的排序栈为空, 则对当前节点进行回溯, 将其父节点作为当前节点node, 重复执行步骤2.

步骤4 当回溯到根节点且其排序栈为空时, 整个过程结束.此时, 与最小误差ε₀相对应的压缩轨迹即为最终压缩轨迹.

在上述基于排序树索引的轨迹压缩过程中, 本文依据下面的性质和定理进行安全剪枝, 从而大大提高了基于排序树索引进行轨迹压缩的效率.

性质1 若当前节点的高度为τ×(n-1), 则其所有子孙节点均无需建立.

定理1 若当前节点的子节点排序栈的栈顶误差超过最小误差ε₀, 则其所有子孙节点均无需建立.

证明略.

定理2 在当前节点的所有子节点中, 若有一个子节点, 其所含轨迹线段的右端点已为轨迹终点, 则当前节点的其他子节点均无需建立.

证明略.

为了验证所提出的基于排序树索引的轨迹压缩方法的性能, 本文在两个真实的数据集(Geolife和T-Drive)上进行了实验, 其中, GeoLife包含了182个用户的17 621条轨迹数据, 覆盖了中国近30个城市以及美国和欧洲的部分城市; T-Drive包含10 357辆出租车采集的轨迹样本, 包含有1.5亿个轨迹点.

所有实验程序的开发环境为Intel(R) Core^TM I5-2400 CPU@3.10 GHz, 4GB内存, 操作系统为Windows 7(64位), 编程语言为JAVA.

实验将本文提出的基于排序树索引(sort tree, ST)的轨迹压缩方法与文献[11]中的动态规划(dynamic programming, DP)方法和误差搜索(error search, ES)方法分别从运行时间、空间占用、压缩轨迹误差，以及实际压缩效果4个方面进行比较.

图 5给出了原始轨迹长度和压缩轨迹尺度阈值τ变化时, 三种方法的运行时间比较.从图 5可以看出, 三种方法的运行时间均随原始轨迹长度的增加而增大, 因为原始轨迹越长, 需要处理的轨迹点数越多.从图 5还可以看出, ST方法相比于DP和ES方法, 轨迹压缩所需的时间更短, 因为ST的轨迹压缩在借助于排序树索引的基础上, 从三方面(见性质1、定理1和定理2) 进行了安全剪枝, 显著减少了发现最终压缩轨迹的时间.

图 5(Fig. 5)

图 5 原始轨迹长度对运行时间的影响 Fig.5 Effect of raw trajectory length on running time (a)—Geolife; (b)—T-Drive.

图 6给出了两个数据集上压缩轨迹误差随原始轨迹长度的变化情况.文献[11]中DP和ES方法的压缩误差相同, 因此, 图 6只给出了ST与ES方法的压缩误差比较.由图 6可以看出, ST与ES方法的压缩轨迹误差都随原始轨迹长度呈正相关增长, 但ES方法的压缩误差高于ST方法, 且随着原始轨迹长度不断增加, 二者差距越来越大.原因在于, 在轨迹压缩过程中, 原始轨迹中的哪些轨迹点能保留在压缩轨迹中, 有一个重要的指标就是线段误差, 本文对线段误差重新进行了定义, ST方法的线段误差计算方式相比于ES方法能更好地体现线段偏离原始轨迹的偏差, 压缩轨迹中的保留点可更好地表达原始轨迹, 因此, 压缩轨迹误差低于ES方法, 且原始轨迹越长, 优势越明显.

图 6(Fig. 6)

图 6 原始轨迹长度对压缩轨迹误差的影响 Fig.6 Effect of raw trajectory length on compressed trajectory error (a)—Geolife; (b)—T-Drive.

本文对考虑方向的轨迹压缩方法进行了研究.针对现有的基于方向的轨迹压缩方法的不足, 提出了基于排序树索引的轨迹压缩方法.在轨迹压缩的过程中, 对与轨迹点保留密切相关的指标进行了重新定义, 并提出了排序树索引建立过程中安全剪枝的方法.真实数据集上的实验表明, 本文所提出的方法相比于已有的轨迹压缩方法, 在运行时间和压缩轨迹误差方面均有较大提升, 实际的压缩效果更好.