轨迹简化: 实验研究与质量分析外文翻译资料

英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料

轨迹简化: 实验研究与质量分析

摘要

随着全球定位系统（Global Positioning System，GPS）传感器在智能手机、车辆、可穿戴设备中的广泛应用，采集的轨迹数据的规模以指数形式增长。因此，迫切需要一种高效的轨迹数据库压缩技术。主流压缩技术称为轨迹简化即找到近似原始轨迹的子序列，并尝试最小化给定误差度量下的信息丢失。尽管在过去几十年中已经提出了许多优秀的轨迹压缩算法，但仍然缺乏全面的比较来覆盖所有最先进的算法，并使用多种运动模式的真实数据集来评估轨迹压缩算法的压缩质量。因此，GPS 数据采集器在具体应用中确定合适的轨迹压缩算法仍然是一个挑战。此外，以前的几乎所有的方法都使用基于误差的度量来评估压缩质量，忽略了它们在压缩之后的数据库之上支持时空查询的准确性.为了解决以上的问题，我们完成了迄今为止对已有的轨迹压缩算法最为全面的评价工作。同时在5种不同运动模式的数据集上，对25种轨迹压缩算法进行比较。根据实验产生的结果，我们将为将为研究者们在算法的使用和选择上提供指导。

近些年来，随着市场上智能手机、汽车、可穿戴设备的等产品数量增加，通过植入的GPS传感器，众多企业能够通过追踪移动物体的实时位置，收集海量物体移动的轨迹信息。Fitbit 是最受欢迎的健康监测和活动跟踪可穿戴设备之一，它从 2300万的活跃用户中以高采样率收集了最新的 GPS 数据。另一方面2016 年 6 月，Uber 载客次数已经达到了20 亿次，这就意味着已经获得了数十亿规模的轨迹数据。因此急需一种有效的的数据管理系统采取数据的压缩、存储、管理、挖掘。

面对这些大量的轨迹数据，有效的压缩机制成为轨迹数据库存储层的关键组成部分。一个直截了当的想法是消除空间和时间属性中的冗余，进而提出无损轨迹压缩技术。例如，MIT 提出的 TrajStore 算法的主要思想是：分别计算两个连续轨迹点和的空间和时间维度的差值，然后对计算得到的差值进行编码压缩。因此，轨迹中的大多数点需要一个字节去存储增量。Trajic 与 TrajStore 相比，计算预测值的方式不同，该算法假设物体在一定时间段内匀速直线运动，然后对真实值和预测值之间的差异 进行编码压缩。然而这些算法受限于对于存储空间的减少。如表1所示，分别表示已有两种典型的无损压缩算法 TrajStore、Trajic 5 种不同运动模式的真实的数据集上面进行无损压缩得到的压缩率。

轨迹有损压缩是主流的轨迹压缩技术，因为轨迹简化压缩算法可以得到更高的压缩率，并且保证信息损失在可接受的范围内。其主要思想是：丢弃冗余或者不重要的点，然后通过从剩余点构造的一些连续线段得到压缩之后的轨迹，用压缩之后的轨迹近似代替原始轨迹。现有轨迹简化压缩算法会根据应用模式的不同分为两类：离线压缩算法、在线压缩算法。离线压缩算法中我们知道完整的历史数据。旨在实现压缩率和数据丢失率之间的良好的平衡。在线压缩算法，传感器端存在一个本地缓冲区，其目标是保留 GPS 数据流中最重要的轨迹点。值得注意的是，可以在这两种轨迹压缩模式中强制要求误差限制误差?，以确保任何丢弃的点的误差不超过给定的误差阈值 ? 。

图一：无损压缩算法的压缩比

语义压缩是一种可供选择的解决方案，它利用道路网络的知识来促进轨迹压缩。 GPS产生的轨迹点通过任何现有的地图匹配方法映射到道路段上。 然后将二维位置转换为路段的ID。 由于连续点的局部序列通常可以映射到同一段，因此空间冗余性得到了改善，这往往将产生更高的压缩比。此外，还可以利用路网中的频繁出行路径进一步降低存储成本。本文对语义压缩算法的实验评价超出了本文的研究范围，主要有两个原因。首先，这些方法需要额外的道路网络信息，而这些信息并不总是可获得的(例如在室内跟踪应用程序中)。其次，这些压缩方法被应用于道路段中地图映射点之上，而不是原始轨迹中的点。有可能移动的物体没有被很好地匹配到相应的路段，导致原始轨迹数据和映射数据之间存在偏差。总结以上两点原因，语义压缩算法、基于路网结构的轨迹压缩算法难以与原始轨迹中的其他压缩方法进行公平的比较，所以本文的实验对比分析不涉及语义压缩算法。

在本文中，论文的目标是对已有的、已被公认为大规模轨迹存储的主流解决方案轨迹简化压缩算法进行全面评估。虽然Muckell和Hunnik等人已经对轨迹压缩领域也做了一个综述。但是，目前对轨迹简化压缩领域的研究中只涉及少量轨迹压缩算法。近年来，轨迹压缩技术取得了重大的进展，因此本文认为有必要进行新一轮的更全面的实验分析，以更加充分的实验结果、全面的分析结果表明最近压缩算法的进展。

首先，文献评估的大多数轨迹压缩算法都是启发式算法，不是最新的轨迹压缩算法。在这之后提出了相当多的最新轨迹压缩算法，而且具有更复杂的距离度量和处理逻辑。最近，还提出了一种新的保留方向的轨迹压缩方法。该方法保留方向信息的全面性。

轨迹压缩算法旨在同时保证方向和位置的误差是合理的。本文首次对 25 种不同的轨迹压缩算法进行分析和实验整理，涵盖在线和离线的两种模式。其次，尽管已经提出了多种基于误差的度量方式来评估轨迹压缩算法的压缩的效果，但是压缩之后的轨迹数据的可用性仍然是未解决的问题。在本文中，合理地假设在轨迹数据库管系统中，轨迹压缩算法位于数据库存储层以支持高级查询处理或模式挖掘任务。因此，数据可用性也是压缩质量评估的关键因素。本文首次实证研究在压缩之后的轨迹数据库上支持流行时空查询的准确性，也就是研究轨迹压缩对数据库查询优化的影响。

总之，本文做出的主要贡献与创新如下：

1、我们对轨迹简化进行了迄今为止最全面的评估，共包括25个算法和5个不同运动模式下的真实数据集。评估包括4种类型的误差指标，包括垂直欧式距离误差(PED)、同步欧式距离误差 (SED)、方向误差和速度误差。

2、首次提出压缩之后的轨迹数据可用性作为新的算法评价标准，在压缩之后的轨迹上进行空间范围查询，?NN 查询，空间连接查询，轨迹聚类等时空查询的准确性进行了详细的对比实验分析与研究

3、涉及的代码已经开源在Github社区

本文的后续章节结构安排如下：第二章对本文中涉及的轨迹压缩算法里面轨迹的相关概念和定义进行说明第三节介绍并总结了离线和在线模式下的压缩算法。第四章，通过全面的实验对算法做出评价和分析。第五章：本文对之前的实验分析结果做出总结，然后提出未来轨迹压缩领域改进的方向。

2 问题的定义

2.1 轨迹的基本概念

轨迹 ? 是带有时间序列的 GPS 数据的序列 ?1, ?2, . . . , ?原始轨迹 ? = {?1, ?2, ?3, . . . , ?8} 。轨迹? 中的第 ? 轨迹点可以表示为 ? [?] ，也可以用三元组表示 ，其中 (??, ??) 表示的是 ??的空间位置，也就是经度，轨迹数据点 ??的采样时间，本文中使用 ? 表示轨迹 ? 中的轨迹点在时间窗口 的轨迹点?组成的子迹其中 ? lt; ? lt; ? 。相反，轨迹 ? 的子序列可以表示为 ，其中轨迹点 ?isin; ? ，并且1 lt; ?1lt; . . . lt; ?lt; ? 。本文中用 ? lt; ? le; ? ，来表示有向轨迹段有向轨迹段 的起始轨迹点为 ??，??点结束。有向轨迹段 的方向定义如下：

定义一：轨迹端的方向：轨迹段的方向用表示，表示的为从轴的正方向到向量逆时针的旋转角度。

轨迹简化的基本问题就是找到 ? 个点的子序列作为原始轨迹 ? 的最佳近似轨迹，这 ? 个点的子序列称为压缩之后的轨迹 ?′，其中 ? lt;lt;N,这M个点将原始轨迹的索引空间 [1,?] 划分为 ? 1 区间。本文将称为简化轨迹段这些轨迹点将会被丢弃，造成数据损失另外，原始轨迹点到对应的简化轨迹段的距离为压缩误差接下来，文中将会对已经提出的压缩误差度量方法进行了详细的总结。

2.2 基于误差的度量：

本文首先给出了已有的轨迹简化算法中所采用的最流行的误差度量方式进行介绍。为了便于解释和说明，文中假设点是轨迹压缩算法丢弃的点，并的对应的简化轨迹段。

定义二：垂直欧式距离（Perpendicular Euclidean Distance，PED） 轨迹点 到简化轨迹段的垂直欧式距离是到简化轨迹段的最短距离，正式

定义如下：

同步欧式距离（Synchronized Euclidean Distance，SED）轨迹点到它在简化轨迹段上的同步点的同步欧式距离定义如下

其中：

定义三：方向感知距离（ Direction-Aware Distance，DAD ） 本文分别定义，的方向为和。轨迹段的角度距离用来表示，定义为两个方向的、的最大的角度差，如下：

举例：图一列举了关于, ,的例子。在这些例子中，们假定点和点将被保留，点将会被移除，其中是轨迹点的简化线段。根据PED算法的定义可以得知，是到其简化线段的最短距离，同理是到其简化线段的最短同步欧式距离，而和之间的角度差

被称为：.

除了上述描述3种流行的基于误差的度量方式外，还存在一些其他类型的误差度量方法。例如，陈等人提出的累积平方同步欧氏距离。文献认为位置和速度是值得保留的轨迹运动特征，速度误差用于评价轨迹的压缩质量。值得注意的是，如果选定一种误差度量的方式，轨迹简化算法可以保证丢弃的轨迹点的最大误差不超过给定的误差阈值 ? 。

2.3数据的可用性

已有的轨迹压缩算法将轨迹压缩和存储认为是轨迹管理系统中的相互独立的组成部分。然而在更大的轨迹管理系统中，压缩之后的轨迹通常被存储，并建立相应的索引，用以支持查询处理和模式挖掘任务.我们发现几乎所有先前的轨迹简化算法都忽略了简化之后轨迹数据的可用性。因此，文中建议将数据可用性作为评估压缩轨迹质量的关键性因素。接下来，本文将定义在轨迹数据库中流行且具有代表性的 4 种不同类别的时空查询，包括区域查询， ?NN 查询，空间相交查询和轨迹聚类，以及在简化之后的轨迹数据库进行时空查询的准确性评价标准进行相关的定义和说明。

定义五：Window Range Query(W-RQ)时间窗口的空间范围查询就是找到数据库中所有的轨迹，满足在给定的一个查询多维数据集立方体中轨迹中至少有一个点满足以下的条件：，，并且

为了定义在轨迹数据库中的 ?NN 查询，本文需要确定两个轨迹之间的合适的距离度量方式。在与之相关工作中，已经提出了几种轨迹距离的度量方式，比如动态时间弯曲距离（DTW，和真实补距离（ERP），最长公共子序列（ LCSS ），实序列编辑距离（EDR）。其中，EDR 由于能够降低离群值的影响，并具有处理局部时间偏移的能力而被广泛引用和采用。此外，它还可以对两个匹配子轨迹之间的距离进行惩罚，并提供更准确的结果。

EDR 的定义如下:

其中，? 和 ?表示两条轨迹，match 函数确定轨迹 ?i ，?i 的距离是否在给定的误差阈值 ? 之内。在本文中，文中使用 EDR 作为距离的度量来定义轨迹数据库中基于窗口的 ?NN 查询。另外，假设所有的轨迹是同步的，缺失的轨迹数据可以利用插值法来填补

定义六：基于窗口的?近邻查询（Window ?NN Query，W-?NN），给定查询的轨迹，时间窗口 ，和轨迹数据库 ? ，W-?NN 查询返回的?集合?集合中有?条轨迹，满足对任一一条轨迹 满足于条件

基于窗口的轨迹距离相交查询（ Window Trajec-tory Distance Join，W-TDJ ），给定轨迹 时间窗口距离阈值 ? ， ?′表示 ? minus;??? 查询返回的轨迹，如果那么查询的轨迹?和返回的轨迹 ?′的同步欧式离，其中 ?(·, ·) 在本文中表示欧式距离。

对于轨迹聚类算子，我们遵循文献[24中提出的定义它使用定制的距离度量，考虑到垂直距离，平行距离和角度距离。有兴趣的读者可参阅了解详情。

3 轨迹简化算法

在过去的几十年里，在线和离线处理模式的轨迹简化压缩技术得到了深入研究。轨迹简化压缩的主要目的是将原始轨迹从 ? 个轨迹数据点减少到 ? 个轨迹点，? lt;lt; ? ，并且仍保留重要的位置或拓扑特征。在离线处理模式中，存储在轨迹数据库中所有的历史轨迹数据在服务器端可用，优点在于可以以更高的计算成本实现压缩率和压缩误差之间更好的折中。在线模式下，本文考虑主流应用程序，传感器端只提供一个本地缓冲区，在线轨迹简化算法的目标是在有大小限制的缓冲区中保留最重要的轨迹点，因此可以减少通信开销。

在下文中，本文将轨迹简化算法分为离线压缩算法和在线压缩算法，并分别在表2和表3中对已有典型的轨迹简化压

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[241459]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

您可能感兴趣的文章

• 船舶在浅水航道中航行时的岸壁效应数值研究外文翻译资料
• 基于三维面元法限制水域船体下蹲的数值研究外文翻译资料
• 关于甲板大开口船体梁极限抗扭强度的实验研究外文翻译资料
• 基于斯托克斯方程计算和系统识别 方法预估实船操纵模型参数外文翻译资料
• 水面舰艇5415在PMM演习中的基准CFD验 证数据-第二部分:平均相位的立体PIV流 场测量外文翻译资料
• 初步设计阶段船舶功率推进预测第二部分初步设计中有用的服务速度船舶功率推进数学模型外文翻译资料
• 对某高速船模湍流自由表面的数值与试验研究外文翻译资料
• 第三章水下搜救与恢复操作外文翻译资料
• 液化天然气供求关系的现状与展望:一个全球性展望外文翻译资料
• 基于CFD的高层钢结构建筑风效应数值评估外文翻译资料