A Framework for Mining Sequential Patterns from Spatio-Temporal Event Data Sets

摘要

Given a large spatio-temporal database of events, where each event consists of the following fields: event-ID, time, location, event-type, mining spatio-temporal sequential patterns is to identify significant event type sequences. Such spatio-temporal sequential patterns are crucial to investigate spatial and temporal evolutions of phenomena in many application domains. Recent literatures have explored the sequential patterns on transaction data and trajectory analysis on moving objects. However, these methods can not be directly applied to mining sequential patterns from a large number of spatio-temporal events. Two major research challenges are still remaining: (i) the definition of significance measures for spatio-temporal sequential patterns to avoid spurious ones; (ii) the algorithmic design under the significance measures which may not guarantee the downward closure property. In this paper, we propose a sequence index as the significance measure for spatio-temporal sequential patterns, which is meaningful due to its interpretability using spatial statistics. We propose a novel algorithm called Slicing-STS-Miner to tackle the algorithmic design challenges using the spatial sequence index which does not preserve the downward closure property. We compare the proposed algorithm with a simple algorithm called STS-Miner that utilizes the weak monotone property of the sequence index. Performance evaluations using both synthetic and real world datasets shows that the Slicing-STS-Miner is an order of magnitude faster than STS-Miner for large datasets.