Discovery of convoys in trajectory databases
Discovery of convoys in trajectory databases
复制标题
DOI：
10.14778/1453856.1453971
复制
发表时间：
2008-08
期刊：
影响因子：
--
通讯作者：
Hoyoung Jeung;Man Lung Yiu;Xiaofang Zhou;Christian S. Jensen;Heng Tao Shen
中科院分区：
文献类型：
--
作者：
Hoyoung Jeung;Man Lung Yiu;Xiaofang Zhou;Christian S. Jensen;Heng Tao Shen
随着具有定位能力的移动设备继续激增，对捕获移动对象群体的历史运动的所谓轨迹数据库的数据管理变得重要。本文考虑了车队的数据库查询问题，车队是一组一起旅行了一段时间的对象。更具体地说，本文使用基于密度的概念形式化了护航查询的概念，以便捕获任意范围和形状的组。车队发现对于卡车吞吐量规划和车辆拼车的实际应用是相关的。尽管文献中对轨迹进行了广泛的研究，但这些研究都不能应用于正确检索准确的护航结果集。在此基础上，我们提出了三种高效的车队发现算法，并采用了著名的过滤-求精框架。在过滤步骤中，我们对轨迹应用线简化技术，并在简化的轨迹之间建立距离界限。这允许在简化的轨迹上高效地发现车队，而不会遗漏任何实际车队。在精化步骤中，对候选车队进行进一步处理，以获得实际车队。我们的综合实证研究提供了对本文建议的性质的洞察，并证明了这些建议在真实世界弹道数据上是有效和高效的。
As mobile devices with positioning capabilities continue to proliferate, data management for so-called trajectory databases that capture the historical movements of populations of moving objects becomes important. This paper considers the querying of such databases for convoys, a convoy being a group of objects that have traveled together for some time. More specifically, this paper formalizes the concept of a convoy query using density-based notions, in order to capture groups of arbitrary extents and shapes. Convoy discovery is relevant for real-life applications in throughput planning of trucks and carpooling of vehicles. Although there has been extensive research on trajectories in the literature, none of this can be applied to retrieve correctly exact convoy result sets. Motivated by this, we develop three efficient algorithms for convoy discovery that adopt the well-known filter-refinement framework. In the filter step, we apply line-simplification techniques on the trajectories and establish distance bounds between the simplified trajectories. This permits efficient convoy discovery over the simplified trajectories without missing any actual convoys. In the refinement step, the candidate convoys are further processed to obtain the actual convoys. Our comprehensive empirical study offers insight into the properties of the paper's proposals and demonstrates that the proposals are effective and efficient on real-world trajectory data.