Mohan, Pradeep2012-08-062012-08-062012-05https://hdl.handle.net/11299/130534University 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 (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- ing crime. 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 SFPM. 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.en-USCascade participation indexCascading spatio-temporal patternsRegional co-location patternsRegional Participation indexSpatial heterogenitySpatio-temporal correlationComputer ScienceThesis or Dissertation