论文部分内容阅读
为支持从各种移动对象产生的大量GPS数据，后端服务器通常存储低采样率的轨迹。因此，人们不能直接从后端服务器获得精确的位置信息，换句话说，不确定性是这些时空数据的固有特性。从而，如何应对移动对象轨迹数据的不确定性成为一个基本而具有挑战性的问题。然而，大量的现有研究仅仅关注移动对象本身的不确定性，而往往忽略了这些数据产生的上下文信息。我们发现，移动对象轨迹数据的不确定性可以有效地利用上下文信息进行消减和排序。在本文中，我们利用上下文信息，提出了一个综合框架，来对移动对象轨迹进行不确定性消减和排序。具体来说，对两个连续的采样数据，我们的目标是对可能的移动路径进行推断和排序。由于一些上下文信息可以减少不确定性，而一些上下文信息可用于不确定性的排序，所以我们的框架自然地分为互为补充的两个阶段:消减阶段和排序阶段。我们分别针对不同的上下文信息设计了算法，实现了对不确定性的消减和排序。我们还实现了一个原型系统来验证我们提出的框架的有效性。大量的实验对比结果表明我们的框架可以实现不确定性的消减，并能对可能的移动路径进行排序。 基于不确定性消减后的轨迹数据，我们研究了如何精确对旅行代价分布进行估计。在一个给定的道路网络中，给定出发时间，利用车辆的历史轨迹数据，我们需要准确地估计任意路径的旅行代价分布。这个问题有三个挑战:第一（数据稀疏性），即使非常大的轨迹数据集也不一定能覆盖道路网络中的所有路径。同时，被覆盖的路径也有可能没有做够多的轨迹数据;第二（分布复杂性），路径的旅行代价分布是复杂的:它是随时间变化的，而且可以是任意的分布。第三（变量相关性），在路径所包含的多条边上的旅行代价分布可能相互相关。为了应对这三个挑战得到准确的旅行代价分布，我们首先在有足够多的轨迹的路径上学习一组不同维度的联合分布。然后，给定一个查询的时间和路径，我们从学习到的随机变量集中计算最优子集，这样，随机变量的组合可以覆盖对应的查询路径。通过这样的步骤，我们可以准确地对查询路径的联合概率分布进行估计。最后，联合分布被用来计算一个表示查询路径的旅行代价分布的边缘分布。我们在真实世界产生的大量GPS轨迹数据集上进行了深入的实验，实验结果证明了我们的方法的可以准确地估计出来较长（包含5个路段以上）路径的旅行代价分布，并且可以在7秒内完成对包含100个路段的路径旅行代价进行计算。 驾驶员通常会考虑多种不同的旅行代价来规划路线，例如，旅行距离，旅行时间和燃料消耗等。不同的驾驶员可能在相同的源和目的地之间选择不同的路线，因为他们拥有不同的驾驶偏好（例如，具有强时间观念的驾驶员会倾向于选择较短旅行时间的路线，而节能型的驾驶员更喜好消耗更少燃料的路线）。现有的路径推荐服务并没有给不同的驾驶员建立不同的推荐模型，从而不能够给不同的驾驶员提供不同的路线。它们大多数会考虑尽量减少其中一个的旅行代价的路线（例如，最短路径或最快的路线）。我们研究的问题是如何基于海量轨迹数据推荐符合单个驾驶员驾驶偏好的个性化路线。首先，我们能从驾驶员的轨迹中建立和更新不同的驾驶偏好。然后，我们提供不同的过滤器来搜索符合当前驾驶偏好的历史轨迹，并基于它们构建相应的局部参考路网。最后，在参考路网上进行快速的路线推荐。我们在真实世界产生的大量GPS轨迹数据集上进行了深入实验，实验结果证明了我们的方法通常可以在1秒内推荐出欧氏距离达到20千米以上的路线，并且与现有的方法比较，这些路线具有更高的满意度。