Discovering interesting subpaths with statistical significance from spatiotemporal datasets

Yiqun Xie, Xun Zhou, Shashi Shekhar

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


Given a path in a spatial or temporal framework, we aim to find all contiguous subpaths that are both interesting (e.g., abrupt changes) and statistically significant (i.e., persistent trends rather than local fluctuations). Discovering interesting subpaths can provide meaningful information for a variety of domains including Earth science, environmental science, urban planning, and the like. Existing methods are limited to detecting individual points of interest along an input path but cannot find interesting subpaths. Our preliminary work provided a Subpath Enumeration and Pruning (SEP) algorithm to detect interesting subpaths of arbitrary length. However, SEP is not effective in avoiding detections that are random variations rather than meaningful trends, which hampers clear and proper interpretations of the results. In this article, we extend our previous work by proposing a significance testing framework to eliminate these random variations. To compute the statistical significance, we first show a baseline Monte-Carlo method based on our previous work and then propose a Dynamic Search-and-Prune (D-SAP) algorithm to improve its computational efficiency. Our experiments show that the significance testing can greatly suppress the noisy detections in the output and D-SAP can greatly reduce the execution time.

Original languageEnglish (US)
Article number2
JournalACM Transactions on Intelligent Systems and Technology
Issue number1
StatePublished - Jan 9 2020

Bibliographical note

Publisher Copyright:
© 2020 Association for Computing Machinery.


  • Interesting sub-paths
  • Spatial
  • Statistical significance
  • Temporal


Dive into the research topics of 'Discovering interesting subpaths with statistical significance from spatiotemporal datasets'. Together they form a unique fingerprint.

Cite this