PaperlayerView exact revision on arXiv

Source-linked AI summary

Spatio-Temporal Data Mining: A Survey of Problems and Methods

Gowtham Atluri, Anuj Karpatne, Vipin Kumar

arXiv:1711.04710v2cs.LGcs.AIcs.CVcs.DB

TL;DR

Spatio-temporal data introduces spatial and temporal dependencies, heterogeneity, and diverse analytical challenges beyond classical data mining. This paper surveys STDM by organizing data types, properties, and methods across six major problem categories.

  • Problem

    Spatio-temporal data mining must address spatial and temporal dependencies and non-stationarity that challenge classical data-mining assumptions.

  • Method

    The paper develops a foundation and taxonomy of spatio-temporal data, then surveys methods for clustering, predictive learning, change detection, frequent pattern mining, anomaly detection, and relationship mining.

  • Results

    The survey organizes diverse spatio-temporal data-mining problems and methods into a common overarching structure spanning six major categories.

  • Takeaways & Limitations

    The framework supports comparison across spatio-temporal applications and can help connect methods and ideas across disparate research domains.

  • Takeaways & Limitations

    The effectiveness of existing approaches for handling heterogeneity and sparsity in spatio-temporal patterns remains to be investigated.

Abstract

from arXiv · show

Large volumes of spatio-temporal data are increasingly collected and studied in diverse domains including, climate science, social sciences, neuroscience, epidemiology, transportation, mobile health, and Earth sciences. Spatio-temporal data differs from relational data for which computational approaches are developed in the data mining community for multiple decades, in that both spatial and temporal attributes are available in addition to the actual measurements/attributes. The presence of these attributes introduces additional challenges that needs to be dealt with. Approaches for mining spatio-temporal data have been studied for over a decade in the data mining community. In this article we present a broad survey of this relatively young field of spatio-temporal data mining. We discuss different types of spatio-temporal data and the relevant data mining questions that arise in the context of analyzing each of these datasets. Based on the nature of the data mining problem studied, we classify literature on spatio-temporal data mining into six major categories: clustering, predictive learning, change detection, frequent pattern mining, anomaly detection, and relationship mining. We discuss the various forms of spatio-temporal data mining problems in each of these categories.

1 INTRODUCTION

Spatio-temporal data combines measurements with spatial and temporal information, creating dependencies and heterogeneous structures that challenge classical data-mining assumptions. The survey organizes STDM data types, representations, similarities, and methods across six major problem categories.

  • ST data and its challenges: Spatio-temporal data records measurements together with the locations and times at which they were collected across many application domains.Examples include neuroimaging, climate science, epidemiology, transportation, and social sciences.
  • ST data and its challenges: Spatial and temporal dependencies violate the independent-and-identically-distributed assumption used by many classical data-mining methods.Ignoring these dependencies can reduce accuracy and interpretability.
  • ST data and its challenges: STDM supports varied definitions of objects, features, and similarities because spatial and temporal information enable novel problem formulations.The paper contrasts these choices with traditional mining of distinct objects having well-defined features.
  • Survey scope and organization: Its overarching structure is intended to connect research across application domains, expose open questions, and guide formulation choices for researchers and practitioners.The paper also links classical data-mining literature with challenges specific to ST data.
  • Survey scope and organization: The survey builds a taxonomy of ST data types, instance representations, and similarity measures, then reviews methods for six common mining problems.The categories are clustering, predictive learning, frequent pattern mining, anomaly detection, change detection, and relationship mining.

2 APPLICATIONS

Spatio-temporal data is collected across scientific, public-health, environmental, agricultural, social, and transportation applications. These datasets support analysis of domain-specific processes, patterns, impacts, and risks.

  • Scientific applications: Climate datasets combine atmospheric and oceanic observations, gridded reanalysis, and climate-model simulations to study future adverse conditions.The stated purpose includes informing adaptation and mitigation actions in a timely manner.
  • Scientific applications: Neuroscience datasets record continuous neural activity with spatial resolutions that differ substantially across fMRI, EEG, and MEG technologies.The passage contrasts measurements from millions of fMRI locations with measurements from tens of EEG locations.
  • Environmental and agricultural applications: Environmental and agricultural datasets use spatially distributed sensors and repeated high-resolution imagery to monitor quality, disease, crop-yield factors, and their inter-relationships.Agricultural imagery is collected at regular intervals ranging from daily to weekly and at resolutions from 0.25m to 1m.
  • Health and social applications: Healthcare and epidemiological records associate diagnoses with patients, locations, and time points to represent disease processes as spatio-temporal data.The passage mentions cancers, diabetes, and infectious diseases as application examples.
  • Health and social applications: Social-media posts and taxi trajectories provide place-and-time data for studying collective experience, epidemic spread, and how urban populations move.Taxi records include pickup and drop-off locations, times, and GPS positions during rides.
  • Other applications: Heliophysics and crime datasets combine event or incident types with observation times and locations to study patterns and policy effects.Examples include solar events, reported crimes, crime patterns, and the effects of law-enforcement policies.

3 DATA

Spatio-temporal data has diverse types and representations, creating multiple ways to formulate mining problems and methods. The paper therefore introduces generic properties, data types, instance definitions, and similarity methods.

  • Data types and representations: The diversity of spatial and temporal attributes leads to multiple formulations of spatio-temporal data-mining problems and methods.
  • Data types and representations: The paper first describes generic ST-data properties and basic data types found across applications.
  • Data types and representations: It then explains common ways to define and represent ST data instances and compute similarities among them.

3.1 Properties

Spatio-temporal observations are correlated across nearby locations and times, and their distributions can vary across space and time. These properties create challenges for classical methods and require ST-aware analysis.

  • Auto-correlation: Nearby spatial and temporal observations are correlated, producing spatial coherence and temporal smoothness rather than independent measurements.Examples include consistent nearby surface temperatures and smoothly changing traffic activity.
  • Auto-correlation: Classical methods that assume independence can perform poorly on ST data, including producing salt-and-pepper errors.
  • Evaluation implications: ST predictions may be useful when their estimated locations or times fall near, rather than exactly on, ground-truth labels.The passage uses crime events as an example of this evaluation issue.
  • Heterogeneity: ST data can be heterogeneous across space and time, so observations from different seasons, climate regimes, or brain regions may require different models.Examples include seasonal vegetation cycles, climate regime shifts, and region-specific neural responses.

3.2 Data Types

Spatio-temporal data is organized into event, trajectory, point reference, and raster types, distinguished by how spatial locations and times are observed. These types support different representations, including fixed or moving reference sites and regular or irregular spatial and temporal grids.

  • Data types: Four common ST data types are event, trajectory, point reference, and raster data.Events record discrete occurrences; trajectories record moving bodies; point reference data samples continuous fields at moving sites; rasters measure fields at fixed grid cells.
  • Event data: Events are discrete occurrences characterized by a point location and time, including crimes, disease outbreaks, accidents, fires, and social-media activity.Event locations may be represented with Euclidean coordinates or distances on a spatial road network.
  • Trajectory data: Trajectories represent paths traced by moving bodies through space over time, such as taxi routes or animal migrations.Sensors mounted on moving bodies commonly transmit periodic location observations.
  • Point reference data: Point reference data measures a continuous spatio-temporal field at reference sites whose locations change over space and time.Weather balloons and buoy sensors provide examples, and the observations can be used to reconstruct the field at arbitrary locations and times.
  • Raster data: Raster data records a continuous or discrete spatio-temporal field at fixed spatial locations and time points.Locations and timestamps may each be regular or irregular, and interpolation or aggregation can convert rasters to common resolutions or other ST data types.

3.3 Data Instances

ST data can be modeled through multiple instance categories, with each choice producing different mining formulations. Common instances include points, trajectories, time series, spatial maps, and complete ST rasters, each supporting distinct analytical questions and feature representations.

  • Instance definitions: A data instance is the basic unit operated on by a mining algorithm, but ST data permits multiple instance definitions for one data type.These alternatives form building blocks for a broad range of STDM problems and methods.
  • ST points: ST points represent discrete observations with spatial, temporal, and additional variables, supporting clustering, pattern discovery, anomaly detection, and prediction questions.Point collections can also be summarized with interaction statistics such as spatio-temporal extensions of Ripley’s K function.
  • Trajectories: Trajectories are temporally ordered location sequences that can be clustered, mined for frequent location subsequences, or represented with generative-model parameters.They may also be treated as point collections or time series of spatial identifiers.
  • Time series: Time-series instances arise from raster observations at each spatial cell or from trajectories represented as multidimensional sequences.Questions include temporal similarity, motifs, short-term deviations, future prediction, and relationships among spatially separated series.
  • Spatial maps and ST rasters: Spatial-map instances treat all raster locations at one timestamp as a map, while complete ST rasters retain measurements across all locations and times.Maps can be represented with image segments; rasters can use tensors, space-time subspaces, or networks linking locations by time-series similarity.

3.4 Similarity Among Instances

Similarity measures underpin clustering, classification, pattern discovery, and relationship mining, but ST instances require measures adapted to their spatial and temporal structure. The survey describes alignment-aware, feature-based, lag-aware, regional, and network-based alternatives.

  • Overview: Similarity among ST instances is central to clustering, classification, pattern discovery, and relationship mining, and its definition varies by instance type.The effectiveness of methods built on proximity measures depends on capturing these forms of similarity.
  • Trajectory similarity: Trajectory similarity can use co-location frequency, longest common subsequence, Fréchet distance, dynamic time warping, edit distance, or feature-based representations.These measures compare shared locations, subsequences, geometric paths, temporal alignment, edits, or extracted features.
  • Time-series similarity: Time-series similarity ranges from Euclidean distance and correlation to dynamic time warping, Fréchet distance, motifs, shapelets, and lag-optimized correlation.Lag-aware comparison translates one series across candidate time lags and selects the lag producing maximum similarity.
  • Time-varying similarity: Similarity structure may vary across time, motivating methods that identify relevant time windows while clustering time series.This addresses cases where relationships among series change as the underlying activity changes.
  • Map and raster similarity: Spatial-map similarity can use corresponding-location distances, smaller foreground regions, or network-based node, link, and representation features.These alternatives address geo-registration misalignment and compare structural properties of ST rasters.

4.1 Clustering

ST clustering must account for spatial contiguity, temporal structure, changing densities, and potentially short-lived or moving relationships. The survey covers clustering objectives and methods for points, trajectories, time series, spatial maps, dynamic regions, and raster datasets.

  • Clustering: Clustering ST data requires handling spatial and temporal structure rather than treating instances as ordinary feature vectors.For raster locations, ignoring spatial information can produce fragmented, difficult-to-interpret clusters and salt-and-pepper errors.
  • Clustering Points: ST-point clustering targets either unusually dense space-time hot-spots or groups sharing similar non-spatial attributes.Applications include disease outbreaks, social movements, crime, Twitter, geo-tagged photos, traffic accidents, and epidemiological data.
  • Clustering Points: ST-DBSCAN separates spatial distance from temporal and non-ST attributes, using separate thresholds to control the desired density.Heterogeneous space and time, varying cluster densities, and sampling bias remain challenges.
  • Clustering Trajectories: Trajectory clustering groups paths over their full duration, while TRACLUS finds short-duration similarity by partitioning trajectories into MDL-based line segments before DBSCAN-based grouping.Moving-cluster methods allow bodies to join or leave groups as they move through space and time.
  • Clustering Time Series: Time-series clustering seeks spatially coherent locations with similar temporal activity, using traditional clustering or methods that directly enforce contiguity.Contiguity constraints avoid the non-contiguous clusters that can result from post-processing traditional methods.
  • Maps and dynamic ST clusters: Spatial-map clustering groups timestamps with similar maps, while dynamic ST clustering identifies coherent subregions whose measurements vary across space and time.Dynamic clusters can capture phenomena affecting only subsets of locations during subsets of time points.
  • ST rasters: Clustering complete ST rasters groups datasets with similar space-time behavior, including climate-model simulations and neuroimaging data.The objective is applied when entire raster datasets are treated as individual instances.

4.2 Predictive Learning

Predictive learning in spatio-temporal applications maps inputs to outputs whose forms may differ across data instances, locations, and times. The section organizes prediction problems by whether inputs and outputs use temporal series, spatial maps, or entire ST rasters.

  • Predictive learning maps input features to output variables, which may represent different types of spatio-temporal data instances.
  • Raster prediction can estimate a continuous or categorical output at every location using the time series observed at each location.
  • Another formulation predicts a scalar at one raster time-step from the spatial map observed at that same time-step.
  • Entire ST rasters can serve as inputs for scalar prediction, such as classifying whether an fMRI scan indicates a mental disorder.
  • Directly vectorizing ST rasters requires aligned grids and can create millions of features from relatively few fMRI instances, encouraging derived features or tensor learning.
  • Predicting responses at particular locations and times from observations in other ST neighborhoods supports applications such as land-cover classification.
  • Temporal forecasting uses present and past conditions, while spatial methods incorporate spatial autocorrelation; spatio-temporal models can incorporate both.

4.3 Frequent Pattern Mining

Frequent pattern mining in ST data covers co-occurrences, event sequences, trajectory sequences, time-series motifs, and network structures. Spatial and temporal dependence creates challenges involving timing, redundancy, heterogeneity, sparsity, and spurious spatial links.

  • Frequent pattern mining discovers patterns recurring across instances, with ST data supporting several formulations involving spatial and temporal components.
  • Co-occurrence patterns identify event types appearing in close spatial and temporal proximity, such as bar closing and drunk driving.
  • Apriori-based methods use a spatio-temporal co-occurrence coefficient, while later filter-and-refine methods address large event databases.
  • Sequential ST patterns model event types that can trigger subsequent events, but require meaningful non-spurious measures and efficient search over exponentially many candidates.
  • Trajectory sequences capture locations or regions visited by multiple objects in the same order, optionally requiring similar durations between consecutive locations.
  • Fixed-time-gap trajectory patterns, flocks, and convoys represent increasingly explicit temporal constraints on moving objects.
  • ST motif discovery must address spatial autocorrelation, which can produce redundant near-duplicate patterns; evolving motifs can reveal phenomena moving across regions.
  • Structural pattern discovery faces heterogeneous pattern presentations and sparse data, while network analyses must filter spatial-neighbor edges to avoid misleading long-range dependencies.

4.4 Anomaly Detection

Anomaly detection in ST data identifies rare instances, points, trajectories, groups, and bursts that diverge from normal spatial or temporal behavior. Methods use similarity, neighborhood structure, spatial scans, tracking, or joint models of normal activity.

  • ST anomalies are rare instances that differ markedly from most data, including unusual trajectories and changing flood or drought frequencies.
  • Point anomalies can be defined as ST points breaking the normal autocorrelation structure within neighborhoods defined jointly by space and time.
  • When neighborhood properties are heterogeneous, detection can model each point’s local expected value and variance instead of assuming homogeneous neighborhoods.
  • Trajectory anomalies can be detected through spatial distances among trajectories or through deviations as moving objects switch between local cohorts.
  • Group anomalies in rasters appear as spatially contiguous regions with anomalous values persisting across a short time interval.
  • Some raster methods separately detect spatial and temporal outlier properties before merging them, while other approaches jointly model spatial and temporal information.
  • Ocean-eddy detection identifies spatial extrema and stitches them through time with multiple-hypothesis object tracking.
  • Spatio-temporal bursts are short-duration increases in location time series, including earthquake-related Twitter query activity mined by STEM.

4.5 Change Detection

ST change detection identifies when system behavior deviates from its past, with applications including climate-phase transitions and brain-state switching. The section extends time-series change detection by incorporating spatial context and varied spatial and temporal extents.

  • Change detection identifies the time point when system behavior significantly deviates from its past behavior.
  • Applications include detecting El Nino-to-La Nina transitions and switching between planning and cognition states in brain imaging.
  • Time-series methods detect intervals with homogeneous properties, including periodic changes after accounting for noise and seasonal variability.
  • Raster change detection must consider spatial context, including contextual changes where a time series deviates from similar series in its local context.
  • A general taxonomy allows changed regions to be points, line-segments, polygons, or networks and changed durations to be time points or intervals.
  • The suitability of video-based change-detection approaches for remote sensing and MRI ST data remains to be explored.

4.6 Relationship Mining

Relationship mining in spatio-temporal data seeks spatial regions and their relationships jointly, while accounting for changing strengths, time windows, and lags. The survey highlights tensor and pattern-mining approaches for discovering these structures.

  • Long-range relationships: Long-range relationships compare distant groups of contiguous locations, requiring simultaneous discovery of both regions and their relationships.Independent region discovery can miss relationships whose regions cross cluster boundaries.
  • Long-range relationships: Tensor decomposition can discover regions and relationships among them simultaneously in brain fMRI data.The resulting network appears highly similar to the default-mode network in resting-state fMRI scans.
  • Dynamic relationships: Dynamic relationships require identifying both interacting regions and the time windows in which their relationship strength changes.Correlations involving the Posterior Cingulate region have been shown to vary over time.
  • Lagged and causal relationships: Lagged relationships represent interactions in which one region’s influence reaches another after a time delay.Their additional degrees of freedom can produce spurious detections unless multiple-hypothesis corrections are carefully performed.
  • Lagged and causal relationships: Granger-style causality defines a cause as a variable that predicts an effect better than an autoregressive model of the effect alone.The approach generalizes to multivariate time series by studying all variables’ effects on a target variable.

5 CONCLUSIONS AND FUTURE WORK

The survey organizes diverse spatio-temporal data-mining research and identifies emerging directions including dynamic representations, multimodal integration, granularity, and theory-guided analysis. It also notes that comprehensive empirical evaluation across the field remains missing.

  • Scope and evaluation: The survey covers only a small fraction of the vast, fast-growing STDM literature while providing a common structure for diverse research.The authors position this structure as a foundation for future reviews with broader empirical comparisons.
  • Scope and evaluation: Comprehensive evaluation of STDM methods across the full breadth of problems and methods is missing.Existing evaluations are limited to specific topics such as trajectory pattern mining and time-series data mining.
  • Emerging directions: Dynamic edges are an emerging representation for ST raster data, complementing work that has focused mainly on static edges.Spatial-temporal varying graphs have been explored for climate-science applications.
  • Emerging directions: Multimodal STDM integrates datasets such as fMRI and MEG or multiple climate variables to construct brain-activity images or climate-system models.These modalities may differ in spatial and temporal resolution or represent inter-related variables at common resolutions.
  • Emerging directions: Most existing STDM work overlooks the granularity at which clusters, patterns, or anomalies should be searched.Future work should characterize current limitations and develop methods addressing this resolution problem.
  • Emerging directions: Theory-guided data science incorporates physics- or theory-based models into STDM for physical-science processes with complex dynamics and sparse observations.This direction combines data-science methods with scientific knowledge to support scientific discovery.
  • Outlook: The authors anticipate significant growth of the relatively young STDM field over the next decade.
Loading 1711.04710v2…