Discovering interesting sub-paths in spatiotemporal datasets: A summary of results

Xun Zhou, Shashi Shekhar, Pradeep Mohan, Stefan Liess, Peter K Snyder

Research output: Chapter in Book/Report/Conference proceedingConference contribution

21 Scopus citations

Abstract

Given a spatiotemporal (ST) dataset and a path in its embedding spatiotemporal framework, the goal is to to identify all interesting sub-paths defined by an interest measure. Sub-path discovery is of fundamental importance for understanding climate changes, agriculture, and many other application. However, this problem is computationally challenging due to the massive volume of data, the varying length of sub-paths and non-monotonicity of interestingness throughout a sub-path. Previous approaches find interesting unit sub-paths (e.g., unit time interval) or interesting points. By contrast, we propose a Sub-path Enumeration and Pruning (SEP) approach that finds collections of long interesting sub-paths. Two case studies using climate change datasets show that SEP can find long interesting sub-paths which represent abrupt climate change. We provide theoretical analyses of correctness, completeness and computational complexity of the proposed approach. We also provide experimental evaluation of two traversal strategies for enumerating and pruning candidate sub-paths.

Original languageEnglish (US)
Title of host publication19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2011
Pages44-53
Number of pages10
DOIs
StatePublished - 2011
Event19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2011 - Chicago, IL, United States
Duration: Nov 1 2011Nov 4 2011

Publication series

NameGIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems

Other

Other19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2011
Country/TerritoryUnited States
CityChicago, IL
Period11/1/1111/4/11

Keywords

  • climate change
  • interesting sub-path
  • spatiotemporal data mining

Fingerprint

Dive into the research topics of 'Discovering interesting sub-paths in spatiotemporal datasets: A summary of results'. Together they form a unique fingerprint.

Cite this