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.
| Original language | English (US) |
|---|---|
| Article number | 2 |
| Journal | ACM Transactions on Intelligent Systems and Technology |
| Volume | 11 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jan 9 2020 |
Bibliographical note
Funding Information:This material is based on work supported by the National Science Foundation under Grants No. 1901099, 1737633, 1541876, 1029711, IIS-1320580, 0940818, IIS-1218168, and IIS-1566386; the USDOD under Grants No. HM1582-08-1-0017 and HM0210-13-1-0005; the ARPA-E under Grant No. DE-AR0000795; the USDA under Grant No. 2017-51181-27222; the NIH under Grant No. UL1 TR002494, KL2 TR002492, and TL1 TR002493; and the OVPR, U-Spatial, and Minnesota Supercomputing Institute (MSI) at the University of Minnesota. Authors’ addresses: Y. Xie and S. Shekhar, 4-192 Keller Hall, 200 Union Street SE, Department of Computer Science and Engineering, University of Minnesota – Twin Cities, Minneapolis, MN 55455; emails: {xiexx347, shekhar}@umn.edu; X. Zhou, S280 Pappajohn Business Building, Department of Business Analytics, University of Iowa, Iowa City, IA 52242; email: xun-zhou@uiowa.edu. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2020 Association for Computing Machinery. 2157-6904/2020/01-ART2 $15.00 https://doi.org/10.1145/3354189
Funding Information:
This material is based on work supported by the National Science Foundation under Grants No. 1901099, 1737633, 1541876, 1029711, IIS-1320580, 0940818, IIS-1218168, and IIS-1566386; the USDOD under Grants No. HM1582-08-1-0017 and HM0210-13-1-0005; the ARPA-E under Grant No. DE-AR0000795; the USDA under Grant No. 2017-51181-27222; the NIH under Grant No. UL1 TR002494, KL2 TR002492, and TL1 TR002493; and the OVPR, U-Spatial, and Minnesota Supercomputing Institute (MSI) at the University of Minnesota.
Publisher Copyright:
© 2020 Association for Computing Machinery.
Keywords
- Interesting sub-paths
- Spatial
- Statistical significance
- Temporal