Introduction
With the proliferation of GPS-enabled devices, analyzing movement patterns has become a critical task across various domains, from urban planning to meteorology. A key challenge in this field is discriminative sub-trajectory mining: identifying specific path segments that distinguish one group of trajectories from another. For instance, one might seek to identify the specific segments of a hurricane's path that indicate it will intensify into a "strong" storm versus remaining "weak."
However, two significant hurdles impede this process. First, the Multiple Testing Problem arises when searching through billions of possible sub-trajectories; many patterns may appear discriminative purely by chance, leading to scientifically unreliable "false positive" discoveries. Second, the Computational Explosion required to establish statistical significance—often involving thousands of random permutations—makes brute-force search impossible for large-scale datasets.
Methodology: The SDSM Algorithm
To address these challenges, we propose the Statistically Discriminative Sub-trajectory Mining (SDSM) algorithm. SDSM introduces a rigorous statistical framework to trajectory mining while maintaining computational efficiency. It utilizes an Average-top-K-max Distance metric, which compares sub-trajectories by averaging their $K$ largest pointwise distances, making the process resilient to minor outliers.
Statistical Rigor
The algorithm utilizes Fisher’s Exact Test (FET) to evaluate the association between a sub-trajectory and a specific group. To control the Family-Wise Error Rate (FWER) and prevent false discoveries, SDSM employs the Westfall-Young (WY) permutation method. This involves shuffling group labels thousands of times to establish a robust baseline for significance.
Efficient Search via Tree-based Pruning
The "secret sauce" of SDSM is its tree-based pruning strategy. The authors mathematically demonstrate that the lower bound of a p-value increases monotonically as a sub-trajectory is extended. By organizing sub-trajectories into a hierarchical tree structure, the algorithm can "prune" entire branches. If a short segment fails to meet a certain significance threshold, none of its longer extensions can possibly be significant, allowing the search to bypass billions of redundant calculations.
Experimental Evaluation
The SDSM algorithm was evaluated on three real-world datasets:
- Hurricane Dataset: 639 Atlantic hurricane trajectories categorized by intensity.
- Vehicle Dataset: 381 trajectories of buses and trucks in Athens, Greece.
- Car Dataset: A massive industrial dataset of 1,000,000 trajectories (representing over 16 billion potential sub-trajectories) categorized by driving hours.
Key Results
- Performance: SDSM achieved a 10x to 60x speedup over standard Westfall-Young implementations on smaller datasets. Crucially, it successfully processed the 1-million-trajectory Car dataset in a realistic timeframe, a task where baseline methods failed entirely.
- Interpretability: In the hurricane data, SDSM identified specific East-to-West then South-to-North curved paths unique to strong hurricanes. In the vehicle data, it isolated road segments used almost exclusively by heavy trucks.
Discussion and Future Work
SDSM shifts the focus of trajectory mining from simple frequency to statistical significance, ensuring that discovered patterns are both meaningful and reliable. While highly effective for binary classification, future work includes extending the framework to multi-class problems and incorporating semantic location data. Additionally, while the current distance metric is robust, exploring domain-specific metrics remains an open area for research.
Summary updated