Zhou, Xun2015-10-132015-10-132014-05https://hdl.handle.net/11299/174912University of Minnesota Ph.D. dissertation. May 2014. Major: Computer Science. Advisor: Shashi Shekhar. 1 computer file (PDF); xi, 117 pages.Recent years have seen the emergence of many new and valuable datasets such as global climate projection, GPS traces, and tweets. However, these Spatiotemporal Big Data (STBD) poses significant challenges for data analytics due to high data variety and candidate-pattern cardinality. One specific STBD analytics tasks is change footprint pattern discovery. Given a definition of change and a dataset about a spatiotemporal(ST) phenomenon, ST change footprint pattern discovery is the process of identifying the location and/or time of such changes in the data. This problem is of fundamental significance to a variety of applications such as understanding climate change, public safety, environmental monitoring, etc. This thesis formally defines the spatiotemporal change footprint as a new pattern family in STBD analytics, and examined footprint patterns and related discovery techniques across disciplines via a novel taxonomy. Methods for detecting change footprints have emerged from a diverse set of research areas, ranging from time series analysis and remote sensing to spatial statistics. Existing reviews focus on discovery methods for only one or a few types of change footprints. To facilitate sharing of insights across disciplines, we conduct a multi-disciplinary review of ST change patterns and their respective discovery methods. We develop a taxonomy of possible ST change footprints and classified our review findings accordingly. This exercise allows us to identify gaps in the research that we consider ripe for exploration, most notably change pattern discovery in vector ST datasets. To address the research gaps identified in the above analysis, this thesis further explores the computational solutions to the discovery of two specific change footprint patterns, namely, interesting sub-paths (e.g., change intervals) and persistent change windows. Given a spatiotemporal (ST) dataset and a path in its embedding spatiotemporal framework, the goal of the interesting sub-path discovery problem is to identify all interesting sub-paths defined by an interest measure. An important application domain of sub-path discovery is understanding climate change. This thesis formally defines the computational structure of interesting sub-path discovery as a Grid-based Directed Acyclic Graph (G-DAG). We propose a new algorithm, namely, the Row-wise Traversal (after leaf-evaluation) with Column Pruning (RTCP) which brings dramatically down the memory cost for G-DAG traversal in our earlier approaches while also reducing CPU cost. We also provide theoretical analyses of correctness, completeness and computational complexity of the RTCP algorithm. Experimental evaluation on both synthetic and real datasets show that the RTCP algorithm is always the fastest in computational time among all the proposed algorithms. The thesis finally explores a more complicated change footprint pattern, namely, the persistent change window. Given a region comprised of locations that each have a time series, the Persistent Change Windows (PCW) discovery problem aims to find all spatial window and temporal interval pairs that exhibit persistent change of attribute values over time. PCW discovery is important for critical societal applications such as detecting desertification, deforestation, and monitoring urban sprawl. The PCW discovery problem is challenging due to the large number of candidate patterns, the lack of monotonicity, and large datasets of detailed resolution and high volume. Previous approaches in ST change footprint discovery have focused on local spatial footprints for persistent change discovery and may not guarantee completeness. In contrast, we propose a space-time window enumeration and pruning (SWEP) approach that considers zonal spatial footprints when finding persistent change patterns. We provide theoretical analysis of SWEP's correctness, completeness, and space-time complexity. We also present a case study on vegetation data that demonstrates the usefulness of the proposed approach. Experimental evaluation on synthetic data show that the SWEP approach is orders of magnitude faster than the naive approach. The work in this thesis is the first step towards understanding the spatiotemporal change footprint discovery problem, including its formulation, computational challenges and solutions, and applications. In this thesis, we have explored automatic and efficient approaches to discovery raster-based ST change footprints, and applied our techniques on climate data in the context of understanding climate change. We conclude this thesis by exploring potential ST change patterns with new footprints (e.g., geographic feature based footprints), alternative computational paradigms (e.g., parallel and distributed STBD analytics), their challenges and solutions, and other future research directions.enChange detectionData miningSpatiotemporal analyticsThesis or Dissertation