Spatio-temporal frequent pattern mining (SFPM) is the process of discovering interesting,
useful and non-trivial patterns from large spatial or spatio-temporal datasets. For example,
analysis of crime datasets may reveal frequent patterns such as partially ordered subsets of
different crime types in the vicinity of bars. SFPM is important for societal applications
such as public safety and can help decision makers design important strategies for mitigat-
In a typical public safety scenario, users provide several inputs including, a collection
of crime reports, a suitable spatial or spatio-temporal neighborhood definition and inter-
estingness thresholds. Given these inputs, SFPM discovers patterns that satisfy the inter-
estingness criterion specified by the user. However, SFPM in the context of public safety
presents multiple challenges. First, spatio-temporal temporal datasets possess unique prop-
erties (e.g. partial order and heterogenity) that highlight the need for new and alternative
pattern semantics. Second, most SFPM scenarios often require a delicate balance between
finding statistically meaningful patterns and achieving computational scalability. Third,
the number of plausible patterns in many spatio-temporal datasets may be exponential in
the cardinality of the set of event types.
Existing research in spatial and spatio-temporal data mining(STDM) is not designed to
account for semantics of spatio-temporal datasets such as partial order and heterogenity. In
addition, existing STDM techniques do not adequately balance the potentially conflicting
requirements of computational scalability and statistical interpretation.
In contrast, this thesis explores two novel pattern families that are designed to model
unique semantics of spatio-temporal datasets, namely, cascading spatio-temporal patterns (CSTPs) and regional co-location patterns (RCPs). CSTPs and RCPs are specifically de-
signed to address semantics of spatio-temporal data such as spatio-temporal partial order
and spatial heterogenity respectively. This thesis explores the discovery of CSTPs and RCPs
from large spatio-temporal crime datasets in detail and makes the following contributions:
(a) We design new interest measures for these pattern families that are statistically inter-
pretable and possess attractive computational properties for the design of computationally
efficient algorithms; (b) We propose novel pattern mining algorithms for discovering a cor-
rect and complet set of patterns; (c) We present performance evaluations of the proposed
algorithms using experiments with real and synthetic datasets and provide algebraic cost
models that analyze worst case costs of different computational approaches; and (d) We
present case studies using these pattern families to validate the real world applicability of
Experimental results show that different SFPM algorithms which exploit special seman-
tics of spatio-temporal datasets (e.g. positive autocorrelation) and special computational
properties of interest measures enhance computational savings. Case studies demonstrate
the real world applicability of proposed SFPM techniques via interesting, potentially useful
and non-trivial patterns discovered from crime datasets.
University of Minnesota Ph.D. dissertation. June 2012. Major: Computer Science. Advisor:Professor. Shashi Shekhar. 1 computer file (PDF); v, 108 pages.
Spatio-temporal frequent pattern mining for public safety:concepts and techniques..
Retrieved from the University of Minnesota Digital Conservancy,
Content distributed via the University of Minnesota's Digital Conservancy may be subject to additional license and use restrictions applied by the depositor.