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

TLDR

Mining spatio‑temporal sequential patterns from large event databases—each event comprising ID, time, location, and type—is essential for studying spatial and temporal evolution in many domains, yet existing methods for transaction data or moving‑object trajectories cannot be directly applied to such large spatio‑temporal event sets. The study aims to define a significance measure—a spatial sequence index—to avoid spurious spatio‑temporal patterns and to design an algorithm that can mine such patterns without relying on downward closure. The authors introduce Slicing‑STS‑miner, an algorithm that uses the spatial sequence index to mine patterns without downward closure, and benchmark it against a baseline STS‑miner that relies on a weak monotone property. Experiments on synthetic and real data demonstrate that Slicing‑STS‑miner is an order of magnitude faster than the baseline STS‑miner on large datasets.

Abstract

Given a large spatio-temporal database of events, where each event consists of the fields event ID, time, location, and event type, mining spatio-temporal sequential patterns identifies significant event-type sequences. Such spatio-temporal sequential patterns are crucial to the investigation of spatial and temporal evolutions of phenomena in many application domains. Recent research literature has explored the sequential patterns on transaction data and trajectory analysis on moving objects. However, these methods cannot be directly applied to mining sequential patterns from a large number of spatio-temporal events. Two major research challenges still remain: 1) the definition of significance measures for spatio-temporal sequential patterns to avoid spurious ones and 2) 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 challenge 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 data sets show that the slicing-STS-miner is an order of magnitude faster than STS-Miner for large data sets.