Discovery of convoys in trajectory databases
By Hoyoung Jeung, Man Lung Yiu, Xiaofang Zhou, Christian S. Jensen, Heng Tao Shen. Proceedings of the VLDB Endowment, 2008
497 citations recorded by the source corpus.
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.
Subfields: Geography, Planning and Development, Transportation, Signal Processing
View Paper: https://www.semanticscholar.org/paper/fa8d53e6b6b589cfba25416dcdcf793cd848e938
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Geography, Planning and Development
In Transportation
In Signal Processing
Citations in the corpus
- Urban Computing: Concepts, Methodologies, and Applications (2014, background): “…branch of research is to discover a group of objects that move together for a certain time period, such as .ock [Gudmundsson et al. 2004, 2006], convoy [Jeung et al. 2008a, 2008b], swarm [Li et al. 2010], traveling companion [Tang et al. 2012, 2013], and gathering [Zheng et al. 2013b, 2014].”
- A Survey on Trajectory Data Management, Analytics, and Learning (2020, background): “es the point-to-trajectory distance. Type Work Map matching Storage Measure Representative query Clustering Indexing Monitoring [170, 173, 185] ✓ segment - Range query ✓ ✓ Road Traffic Jam & Flow [53, 91, 205] ✓ segment EBD ✗ ✓ ✓ Anomaly [34, 175] ✗ point EDR ✗ ✓ ✓ Network design [33, 116, 135] ”
- Spatio-Temporal Data Mining (2017, methodology): “2009) or “convoys” (Jeung et al. 2008) that are used for finding groups of objects moving together.”
- Trajectory Data Mining (2015, background): “A branch of research is to discover a group of objects that move together for a certain time period, such as flock [37][38], convoy [42][44], swarm [55], traveling companion [96][97], and gathering [135][136].”
- A review of moving object trajectory clustering algorithms (2016, methodology): “…complexity Euclidean distance Parameter-free The length of two trajectories must be the same Weakest O(n) PCA + Euclidean distance Parameter-free The length of two trajectories must be the same Weaker O(n) Hausdorff distance Parameter-free It is applicable for most of trajectory data Weaker…”
- Deep Representation Learning for Trajectory Similarity Computation (2018, background): “Quantifying the similarity between two trajectories is a fundamental research problem and is a foundation for many trajectory based applications, such as tracking migration patterns of animals [1], mining hot routes in cities [2], trajectory clustering [3] and moving group discovery [4], [5].”
- Swarm (2010, background): “One line of study is to find moving object clusters including moving clusters [14], flocks [10, 9, 4], and convoys [13, 12].”