Mixed-Drove Spatio-Temporal Co-occurrence Pattern Mining: A Summary of Results Mete Celik1 Shashi Shekhar1 James P. Rogers2 James A. Shine2 Jin Soung Yoo1 1Department of Computer Science, University of Minnesota, MN, USA {mcelik,shekhar,jyoo}@cs.umn.edu 2U.S. Army ERDC, Topographic Engineering Center, VA, USA {james.p.rogers.II,james.a.shine}@erdc.usace.army.mil Abstract Mixed-drove spatio-temporal co-occurrence patterns (MDCOPs) represent subsets of object-types that are located together in space and time. Discovering MDCOPs is an important problem with many applications such as identifying tactics in battlefields, games, and predator-prey interactions. However, mining MDCOPs is computationally very expensive because the interest measures are computationally complex, datasets are larger due to the archival history, and the set of candidate patterns is exponential in the number of object-types. We propose a monotonic composite interest measure for discovering MDCOPs and a novel MDCOP mining algorithm. Analytical and experimental results show that the proposed algorithm is correct and complete. Results also show the proposed method is computationally more efficient than naïve alternatives. 1. Introduction Mining MDCOPs is important for many spatio-temporal application domains, including the military (battlefield planning and strategy), ecology (tracking species and pollutant movements), homeland defense (looking for significant “events”), and transportation (road and network planning) [5, 9]. MDCOPs frequently occur during sporting events, such as in American football where two teams try to outscore each other by moving a football to the opponent’s end of the field. Various complex interactions occur within one team and across teams to achieve this goal. These interactions involve intentional and accidental MDCOPs, the identification of which may help teams to study their opponent’s tactics. In American football object-types may be defined by the roles of the offensive and defensive players, such as quarterback, running back, wide receiver, kicker, holder, and cornerback. An MDCOP is a subset of object-types, e.g. {kicker, holder}, {wide_receiver, cornerback}. One example MDCOP that occurs quite frequently involve wide receivers and cornerbacks of opposing teams. The objective of a wide receiver is to successfully catch the football thrown by the quarterback, whereas a cornerback attempts to prevent the catch. This interaction creates an MDCOP between these two player roles. Another pattern that may occur within the same team involves the holder and the kicker. Both are required to be together for numerous events within a single game at various locations in the field. Their objective is to kick the football to score a field goal or extra point. Other MDCOPs that frequently occur in football involve commonly used tactics such as a “double reverse,” a “blitz,” or a “fake handoff”. Identifying or mining the MDCOPs and other tactics used by opposing teams is crucial in pre-game preparation. Currently, coaches and players watch videotapes of other games to discover these patterns. A second example of an MDCOP is in ecological predator-prey relationships. Patterns of movements of rabbits and foxes, for example, will tend to be located in the same space at the same time. The rabbit patterns will attempt to move away from the fox patterns, and the fox patterns will attempt to stay with the rabbit patterns, much like the wide receivers and cornerbacks in the American football example. In this case, other This work was partially supported by the US Army Corps of Engineers under contract number W9132V-06-C-0011, the Army High Performance Computing Research Center (AHPCRC) under the auspices of the Department of the Army, Army Research Laboratory (ARL) under contract number DAAD19-01-2-0014, the NSF grant IIS-0208621, and the NSF grant ISS-0431141.CB.2CB.1CB.1WR.1WR.2CB.1WR.1CB.2WR.2WR.1WR.2CB.1CB.2CB.1WR.2WR.1Q.1Q.1Q.1 Q.1Q.1CB.1WR.1CB.2WR.2 time slot t=0 time slot t=1 time slot t=2 time slot t=3 coach sketch (a) (b) (c) (d) (e) Figure 1. An example spatio-temporal dataset to compare related approaches Table 1. Comparison of MDCOP with related work Level Group Time Interval Spatio-temporal Pattern Object Object-type Uniform Mixed Consecutive Discrete Flock Pattern [4, 11] X X X Moving Clusters [8] X X X X Mixed-drove Pattern X X X X factors such as available food and water may also affect the patterns as well. However, discovering MDCOPs is challenging for several reasons: First, the process is computationally very expensive because the interest measures are computationally complex. Second, current interest measures (i.e. the spatial prevalence measure) are not sufficient to mine such patterns, so new composite interest measures to do so must be created and formalized [7, 13]. Third, the set of candidate patterns grows exponentially with the number of object-types. Fourth, since spatio-temporal datasets are huge, computationally efficient algorithms must be developed. We create and formalize a new monotonic composite interest measure to mine interesting and non-trivial MDCOPs out of massive spatio-temporal datasets in a computationally efficient manner. Related Work: Previous studies for mining spatio-temporal co-occurrence patterns can be classified into two categories, namely, mining of uniform groups of moving objects (e.g., flock patterns [4, 11]) and mining of mixed groups of moving objects (e.g., moving clusters [8]). Our problem belongs to the latter one (Table 1). A flock pattern is a moving group of the same kind of object, such as a sheep flock or a bird flock. Gudmundsson et al. proposed algorithms for detection of the flock pattern in spatio-temporal datasets [4]. Since our problem is to mine mixed groups of objects, the proposed algorithms by Gudmundsson et al. to discover flock patterns may not be applicable to our problem. Kalnis et al. defined the problem of discovering moving clusters and proposed clustering-based methods to mine such patterns [8]. In their approach, if there is a large enough number of common objects between clusters in consecutive time slots, such clusters are called moving clusters. Moving cluster patterns can be either uniform or a mixed group of objects [8]. However if there is no overlap between the clusters in consecutive time slots, their proposed algorithms