TL;DR
This paper introduces an efficient online method for similarity search on spatial trajectories using a novel lower bounding technique called LBRotation. They also propose presorting strategies based on simple trajectory summaries to significantly improve search speed by reducing the number of expensive distance calculations.
What Problem Does This Paper Address?
Finding similar spatial trajectories within large datasets is a common but computationally challenging task. Traditional methods often rely on Dynamic Time Warping (DTW), a powerful but slow distance measure. While DTW is effective for one-dimensional time series, its application to two-dimensional spatial trajectories (like GPS tracks) is less explored, and existing DTW lower bounding techniques are often offline and not suitable for streaming data. This paper aims to bridge this gap by developing an efficient, online-capable lower bound for DTW on spatial trajectories and enhancing its performance with smart data ordering techniques.
Methods
The core of the paper is the adaptation and improvement of LBRotation, a lower bounding technique originally designed for 2D trajectories. The authors make several key contributions:
- Online LBRotation: They modify LBRotation to work in an online setting, meaning it can process data as it arrives without needing the entire dataset upfront. This is achieved by replacing the Douglas Peucker algorithm for segmentation with an "Opening Window Algorithm" and simplifying the rotation angle calculation.
- Simplified Rotation: Instead of complex least-square fitting, they use a simpler arctangent calculation for segment rotation, which they show doesn't compromise the lower bound's tightness.
- Presorting Strategies: To further boost efficiency, they introduce three presorting strategies:
- Centroid-based: Trajectories are reordered based on the similarity of their spatial centroids (average location).
- Last Point-based: Trajectories are ordered by the proximity of their end points, useful for recent data.
- Geohash Jaccard distance: Trajectories are encoded using Geohash, and their similarity is measured by the Jaccard distance of these sets, which is efficient to index.
These presorting strategies aim to bring "promising" candidates (those likely to be similar) to the front of the dataset, allowing the lower bound to prune more irrelevant trajectories earlier in the search.
Datasets
The authors evaluated their methods on a variety of real-world and synthetic datasets:
- Geolife GPS Trajectories: A large dataset of GPS tracks from 178 users over four years.
- Character Trajectories: Smoothed derivatives of writing trajectories for 20 different letters.
- Prague Ego-Shooter Dataset: Trajectories from a video game, capturing player movement on a specific map.
- Roma Taxi Dataset: GPS trajectories of taxi drivers in Rome.
- Fastest Paths in San Francisco Dataset: A synthetic dataset generated from a street network, representing fastest routes between points.
Key Insights and Ideas
- LBRotation's Adaptability: The paper demonstrates that LBRotation, while originally offline, can be effectively adapted for online scenarios without significant loss in performance. This is crucial for real-time applications.
- Simplicity Wins: Simplifying the rotation calculation in LBRotation (using arctan instead of least squares) proves to be effective and efficient, highlighting that complex methods aren't always necessary.
- Presorting is Powerful: The most significant insight is the substantial impact of presorting. By intelligently reordering the dataset based on simple summaries, the pruning ratio can be dramatically increased, leading to considerable speedups.
- Summary Choice Matters: The effectiveness of presorting depends heavily on the chosen summary. For datasets with short, distinct trajectories (like San Francisco's shortest paths), centroids and last points are effective. For longer, more complex trajectories (like Roma taxis), more sophisticated summaries like Geohash Jaccard distance become more valuable.
Key Results
- Tightness: The LBRotation variants generally achieved good tightness (a measure of how close the lower bound is to the true DTW distance), with minimal differences between segmentation methods (Douglas Peucker vs. Opening Window) and rotation calculations.
- Pruning Ratio and Speedup: Presorting strategies consistently and significantly improved the pruning ratio compared to random ordering. For example, on the San Francisco dataset, presorting achieved pruning ratios close to 99%, leading to speedups of up to 5.8x compared to random ordering. The average speedup across datasets was around 3.25x.
- Dataset Sensitivity: The effectiveness of presorting varied by dataset. Centroid and last point strategies performed well on shorter trajectories, while Geohash Jaccard distance showed promise for longer, more complex datasets like Geolife and Roma.
Limitations and Future Work
- Segmentation Impact: The paper notes that the quality of segmentation can have a severe impact on LBRotation's performance, and while they explored online segmentation, further research into optimal online segmentation for LBRotation is suggested.
- Summary Selection: The authors acknowledge that selecting the "best" summary for presorting is application- and dataset-dependent. Future work could focus on automatically selecting or combining summaries to maximize pruning power.
- Ensemble Summaries: They suggest exploring ensembles of summaries for even better performance.
- Extracting Extreme Behavior: Future research could involve more advanced methods for extracting extreme behaviors from trajectories, beyond simple summaries like centroids or last points, potentially using techniques like convex hull analysis or archetypal analysis.
Summary updated