Source-linked AI summary
Discovery of Convoys in Trajectory Databases
Hoyoung Jeung, Man Lung Yiu, Xiaofang Zhou, Christian S. Jensen, Heng Tao Shen
TL;DR
The paper addresses exact convoy querying in trajectory databases, where existing trajectory methods do not directly retrieve convoy result sets. It formalizes convoys with density-based notions and develops filter-refinement algorithms using trajectory simplification and distance bounds. Experiments on real datasets report effective and efficient proposals, with CuTS* showing the best performance.
Problem
Existing trajectory methods do not correctly retrieve exact convoy result sets, while convoy discovery is needed for applications such as throughput planning and carpooling.
Method
The paper defines convoys using density connection and develops four algorithms using line simplification, distance bounds, and filter-refinement processing.
Results
CuTS* shows the best performance in experiments with real datasets, while CuTS+ performs well for trajectories with few objects and long histories.
Takeaways & Limitations
Density-based convoy queries capture arbitrary group shapes and extents while the proposed filters reduce data processed without eliminating actual convoys.
Takeaways & Limitations
Moving-cluster methods cannot compute exact convoy results with a single absolute overlap threshold, and λ does not precisely capture dataset distributions.
Abstract
from arXiv · showhide
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.
1. INTRODUCTION
The paper addresses efficient convoy discovery in growing trajectory databases, defining convoys to capture groups of arbitrary shapes and extents. It proposes filter-refinement algorithms that simplify trajectories while preserving exact convoy results.
- Trajectory databases support applications including travel-time prediction, rerouting, throughput planning, and carpooling.
- Flocks are sensitive to user-specified disc size and circular shape, creating lossy results for naturally grouped objects.
- Convoys use density connection to retrieve groups of at least m objects that remain density-connected within distance e for k consecutive time points.
- Existing trajectory methods do not directly retrieve exact convoys, whose set-based queries over short time durations are more expensive than pairwise spatio-temporal joins.
- The paper evaluates four convoy-discovery algorithms on several real trajectory datasets and analyzes their advantages and disadvantages.
- CuTS, CuTS+, and CuTS* use line simplification, distance bounds, and filter-refinement processing to reduce data while avoiding missed actual convoys.
2. RELATED WORK
Related work covers trajectory clustering, simplification, distance measures, and spatio-temporal joins. The discussion distinguishes convoy semantics from moving clusters and identifies limitations of existing simplification and distance approaches.
- Clustering over Trajectories: Moving clusters link snapshot clusters through overlap thresholds, but their semantics and lifetime conditions do not necessarily match convoys.
- Clustering over Trajectories: Trajectory-grouping methods based on segments or future positions may ignore whether objects were close together at the same time or focus on the wrong temporal direction.
- Clustering over Trajectories: Flocks require at least m objects to remain within a circular region of radius e, making their results dependent on a specified spatial shape and size.
- Trajectory Simplification: Line simplification represents trajectories as polylines and reduces points according to a user-specified resolution; Douglas-Peucker is a well-known method for this task.
- Trajectory Simplification: Douglas-Peucker ignores the time domain, while DP* incorporates temporal positions when measuring simplification deviation.
- Trajectory Distance and Joins: Common trajectory distances, including DTW, LCSS, EDR, and ERP, address similarity but may not capture all trajectory characteristics or the paper’s short-duration setting.
3. PROBLEM DEFINITION
The paper defines convoy queries over trajectories using density connection, allowing groups with arbitrary shapes and extents to persist for a minimum lifetime.
- Distance functions: The paper defines point, point-to-segment, segment-to-segment, and bounding-box distance functions for trajectory analysis.These functions support later distance and range-search operations.
- Trajectory model: A trajectory is a timestamped polyline representing an object's movement over an interval in the space-time domain.Trajectories may have different lengths, appearances, disappearances, and regular or irregular sampling.
- Density connection: Density connection captures connected groups of points with arbitrary shape and extent, avoiding the rigid disk-size restriction of flocks.The paper motivates this formulation as a response to cases where no single disk size fits the data.
- Convoy query: A convoy query returns maximal groups of at least m density-connected objects within distance e for at least k consecutive time points.The query is defined over a set of trajectories and uses distance threshold e, object threshold m, and lifetime k.
- Example: For m = 2 and k = 3, the example returns objects o2 and o3 as a convoy from t1 through t3.The reported result is ⟨o2, o3, [t1, t3]⟩.
4. COHERENT MOVING CLUSTER (CMC)
CMC adapts snapshot density clustering to discover convoys across time, addressing missing samples and the required lifetime constraint through interpolation and candidate tracking.
- Motivation: A simple snapshot-clustering approach can miss exact convoys because moving-cluster overlap thresholds do not guarantee exact results.Moving clusters also need not satisfy the convoy lifetime constraint, and missing time points prevent direct density-connection measurement.
- CMC design: CMC linearly interpolates virtual locations for missing time points and requires candidates to persist across at least k consecutive clusters.These extensions address irregular sampling and the convoy lifetime requirement.
- Example: With m = 2 and k = 3, CMC reports candidate v1 after it retains two common objects across three consecutive time points.The example illustrates candidate intersection and lifetime accumulation.
- CMC processing: At each time point, CMC applies DBSCAN to active object locations, intersects clusters with existing candidates, and reports candidates reaching lifetime k.Clusters with insufficient overlap become new candidates for subsequent iterations.
5. CONVOY DISCOVERY USING TRAJECTORY SIMPLIFICATION (CUTS)
CuTS reduces convoy-discovery cost by simplifying trajectories, searching simplified segments with error bounds, and refining candidate convoys on the original trajectories.
- CuTS overview: CuTS uses filter-and-refinement because CMC generates virtual locations for missing points and clusters at every time point, incurring high cost.The filter seeks an efficient superset of actual convoys; refinement recovers the actual results.
- Trajectory simplification: Trajectory simplification derives a shorter polyline whose deviation from the original trajectory is at most tolerance δ.CuTS applies Douglas-Peucker recursively, retaining points whose distance from the approximating line exceeds δ.
- Trajectory simplification: The actual tolerance of a simplified segment is the maximum point-to-segment distance over its time interval, and the trajectory tolerance is the maximum segment tolerance.Actual tolerances can be smaller than the user-specified δ and tighten later distance computations.
- Distance bounds: CuTS performs range search over time-overlapping simplified line segments using bounding-box and segment distance bounds to prune non-qualifying candidates.The search applies Lemma 2 before examining individual segments and Lemma 1 afterward.
- Range search: Surviving line segments support efficient density-connected clustering, while trajectory-level search can further reduce filter cost and control granularity.The generalized search also applies to sub-trajectories.
6. EXTENSIONS OF CUTS
The extensions of CuTS improve convoy discovery by accelerating trajectory simplification or tightening temporal distance bounds, while trading off simplification power in some cases.
- Extensions of CuTS: Two CuTS enhancements accelerate trajectory simplification and shorten clustering search ranges using temporal information.The latter reduces the number of candidates after CuTS's filter step.
- CuTS+: DP+ selects a point near the trajectory midpoint among points exceeding tolerance δ, producing more balanced recursive divisions than DP.DP instead selects the point with the largest distance from the approximating segment.
- CuTS+: DP+ may simplify less than DP because its divisions preserve the original trajectory shape less effectively.In the example, DP+ retains p1, p4, p6, p7, whereas DP retains p1, p6, p7.
- CuTS+: Despite lower reduction, DP+ can improve CuTS by simplifying faster and producing actual tolerances no larger than DP's, tightening range-search error bounds.The supplied passage gives δ4 < δ6 as an example.
- CuTS*: CuTS's original simplification can produce loose segment-distance bounds because intermediate simplified locations lack fixed timestamps, creating excessive candidates for refinement.The refinement step can therefore become more expensive.
- CuTS*: CuTS* combines DP* temporal simplification with tightened distance measures and uses the resulting bounds during filter-step range searches.These modifications are reported to improve filter-step effectiveness.
- CuTS*: DP* preserves time ratios in simplified segments, enabling tighter distance measures but yielding a lower vertex reduction ratio than DP.The tightened measure evaluates closest approach over the segments' common time interval; non-overlapping intervals have distance ∞.
7. EXPERIMENTS
Experiments compare CMC with the CuTS family on real vehicle and animal trajectories, then examine how simplification, tolerance, and partition settings affect efficiency. The CuTS methods substantially outperform CMC, with CuTS* generally strongest and CuTS+ advantageous on long trajectories with few objects.
- 3.9–33.1 times faster: the CuTS family outperformed CMC across all datasets, with CuTS* achieving the highest efficiency.
- CMC incurred extra computational cost on Car and Taxi because missing trajectory points required virtual-point generation, whereas CuTS required no such extra processing.
- CuTS remained faster overall than CMC on Cattle despite substantial trajectory-simplification cost.
- CuTS+ reduced both simplification time and refinement cost on Cattle because DP+ was faster and produced tighter error bounds than DP.
- Filtering consumed about 70%–80% of computation on two datasets, while simplification used about 5%–15% and refinement about 20%–30%.
- The actual tolerance reduced post-filter candidate counts considerably, although its efficiency benefit was small on Truck and Taxi.
- Increasing δ reduced filtering effectiveness and discovery efficiency because δ affects both trajectory simplification and clustering range search.
- CuTS* generally performed best, while CuTS+ matched or exceeded it on Cattle for λ ≥50 because simplification dominated total runtime.
8. CONCLUSION
The conclusion presents convoy discovery as a difficult trajectory-querying problem and summarizes density-based modeling, four algorithms, error-bounded filtering, and real-data evaluation. CuTS* performs best overall, while CuTS+ performs well for small object sets with long histories.
- The paper formalizes convoy queries with density-based notions to represent groups with arbitrary shapes and extents.
- Four algorithms are proposed, including CuTS, CuTS+, and CuTS*, which use line simplification within a filter-refinement framework.
- Error bounds over simplified trajectories are used so filtering does not eliminate actual convoys.
- CuTS* shows the best performance in experiments with real datasets.
- CuTS+ performs well when trajectories contain few objects and long histories.
A.1 Proof of Lemma 1
The proof proceeds by contradiction: it assumes an equation, derives intermediate inequalities, and concludes the lemma when the assumed relation yields a contradiction.
- The proof begins by assuming the stated equation for the Figure 7 example.
- Locations on simplified trajectory segments are introduced for the relevant points in the argument.
- The argument combines inequalities using the triangle inequality to establish the required relation.
- The resulting contradiction proves Lemma 1.
A.2 Proof of Lemma 2
The supplied proof passage states that the remainder of the argument follows directly from Lemma 1 after the preceding inequality conditions are established.
- The proof considers the condition under which the displayed equation is satisfied.
- It then states that the next equation must also hold under that condition.
- The remaining proof follows directly from Lemma 1.
A.3 Proof of Lemma 3
The proof continues the established reasoning from Lemma 1 while referring to locations in simplified trajectories.
- The proof refers to a location l′ in a simplified trajectory o′.
- The argument introduces an additional stated relation after discussing the relevant locations.
- The remainder of the proof follows the same logic as the proof of Lemma 1.
B.1 MC vs. CMC
The experiment compares moving-cluster results with convoy results and shows that MC2 can produce both false positives and false negatives. These discrepancies arise because MC2 does not directly enforce all convoy-query conditions, including lifetime.
- MC2 reports convoy-like results when consecutive clusters retain at least threshold θ of their common objects.
- Figure 19 is used to assess MC2 convoy discovery quality through false positives and false negatives.
- MC2 reports more convoys than CMC because it lacks the lifetime constraint k.
- For the larger Cattle dataset, the actual-convoy proportion was especially low and false positives were especially high.
- False positives and false negatives generally increased with θ in the reported comparisons.