Statistically Discriminative Sub-trajectory Mining

Vo Nguyen Le Duy, Takuto Sakuma, Taiju Ishiyama, Hiroki Toda, Kazuya Nishi, Masayuki Karasuyama, Yuta Okubo, Masayuki Sunaga, Yasuo Tabei, Ichiro TakeuchiarXiv 2019 · arXiv

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.

Visualizing discriminative sub-trajectories in hurricane paths.

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.

The tree-based pruning mechanism used to navigate the search space efficiently.

Experimental Evaluation

The SDSM algorithm was evaluated on three real-world datasets:

  1. Hurricane Dataset: 639 Atlantic hurricane trajectories categorized by intensity.
  2. Vehicle Dataset: 381 trajectories of buses and trucks in Athens, Greece.
  3. 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

Abstract

We study the problem of discriminative sub-trajectory mining. Given two groups of trajectories, the goal of this problem is to extract moving patterns in the form of sub-trajectories which are more similar to sub-trajectories of one group and less similar to those of the other. We propose a new method called Statistically Discriminative Sub-trajectory Mining (SDSM) for this problem. An advantage of the SDSM method is that the statistical significance of the extracted sub-trajectories are properly controlled in the sense that the probability of finding a false positive sub-trajectory is smaller than a specified significance threshold alpha (e.g., 0.05), which is indispensable when the method is used in scientific or social studies under noisy environment. Finding such statistically discriminative sub-trajectories from massive trajectory dataset is both computationally and statistically challenging. In the SDSM method, we resolve the difficulties by introducing a tree representation among sub-trajectories and running an efficient permutation-based statistical inference method on the tree. To the best of our knowledge, SDSM is the first method that can efficiently extract statistically discriminative sub-trajectories from massive trajectory dataset. We illustrate the effectiveness and scalability of the SDSM method by applying it to a real-world dataset with 1,000,000 trajectories which contains 16,723,602,505 sub-trajectories.
BibTeX
@misc{duy2019statistically,
  author = {Vo Nguyen Le Duy and Takuto Sakuma and Taiju Ishiyama and Hiroki Toda and Kazuya Nishi and Masayuki Karasuyama and Yuta Okubo and Masayuki Sunaga and Yasuo Tabei and Ichiro Takeuchi},
  title = {{Statistically Discriminative Sub-trajectory Mining}},
  year = {2019},
  eprint = {1905.01788},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1905.01788},
}
Figure