Journal article
Discovering Interesting Subpaths with Statistical Significance from Spatiotemporal Datasets
ACM transactions on intelligent systems and technology, Vol.11(1), pp.1-24
02/11/2020
DOI: 10.1145/3354189
Abstract
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.
Details
- Title: Subtitle
- Discovering Interesting Subpaths with Statistical Significance from Spatiotemporal Datasets
- Creators
- Yiqun Xie - University of Minnesota -- Twin Cities, Minneapolis, MNXun Zhou - University of Iowa, Iowa City, IAShashi Shekhar - University of Minnesota -- Twin Cities, Minneapolis, MN
- Resource Type
- Journal article
- Publication Details
- ACM transactions on intelligent systems and technology, Vol.11(1), pp.1-24
- DOI
- 10.1145/3354189
- ISSN
- 2157-6904
- eISSN
- 2157-6912
- Grant note
- DOI: 10.13039/100000001, name: National Science Foundation, award: IIS-1566386, 1737633, 1541876, 1029711, IIS-1320580, 09409818; DOI: 10.13039/100000093, name: National Institutes of Health, award: UL1 TR002494, KL2 TR002492, TL1 TR002493; DOI: 10.13039/100000199, name: U.S. Department of Agriculture, award: 2017-51181-27222; DOI: 10.13039/100000005, name: U.S. Department of Defense, award: HM1582-08-1-0017, HM0210-13-1-0005; DOI: 10.13039/100006133, name: Advanced Research Projects Agency - Energy, award: DE-AR0000795
- Language
- English
- Date published
- 02/11/2020
- Academic Unit
- Business Analytics
- Record Identifier
- 9984066344502771
Metrics
20 Record Views