RASP: Robust Mining of Frequent Temporal Sequential Patterns under Temporal Variations

Hyunjin Choo, Minho Eom, Gyuri Kim, Young-Gyu Yoon, Kijung ShinEDBT 2025 · OpenReview

Introduction

In domains such as neuroscience, high-frequency trading, and e-commerce, researchers seek to identify Temporal Sequential Patterns (TSPs)—sequences of events where the specific time intervals between occurrences are critical. For example, a pattern might be defined as "Event A occurs, followed by Event B after 10ms, and Event C after another 5ms."

However, real-world data is rarely precise. Measurement errors and inherent system variability introduce "jitter," where a 10ms gap may appear as 9ms or 11ms. Existing mining tools often struggle with this noise, either requiring rigid exact matches or becoming computationally overwhelmed when attempting to account for variations. Furthermore, most tools require manual tuning of frequency thresholds; an incorrect setting can lead to either missed patterns or system crashes due to memory exhaustion.

The RASP Framework

The RASP (Robust and resource-Adaptive mining of temporal Sequential Patterns) algorithm addresses these challenges through three primary innovations designed for efficiency and robustness.

1. Relaxed Matching and Duplication

To handle temporal noise, RASP introduces "relaxed" TSPs. Instead of requiring exact time gaps, the algorithm allows for a predefined tolerance level ($\tau$). It employs a "duplicated matching" strategy, where a single sequence of events can contribute to the frequency counts of multiple potential relaxed patterns. This ensures that the underlying signal is captured even when obscured by noise.

The windowing mechanism in RASP allows for robust pattern matching across overlapping temporal segments.

2. Resource-Adaptive Tuning

RASP eliminates the need for users to guess frequency thresholds. Instead, users provide a memory budget (the maximum number of patterns to store). As the algorithm processes data, it automatically adjusts the frequency threshold to prune less significant patterns, ensuring the system never exceeds its RAM limits.

3. Efficient Data Structures

Patterns are stored in a prefix-tree (forest) structure. By allowing patterns with shared prefixes and time gaps to share memory, RASP significantly reduces its storage footprint, enabling the processing of much larger datasets than previous methods.

Experimental Evaluation

The researchers evaluated RASP against state-of-the-art competitors (CAD, SPADE, and MIPER) using a variety of datasets:

  • Synthetic Neuronal Activity: Controlled data to test noise and distractor events.
  • E-commerce: User clickstream data.
  • Precipitation: 15-minute interval weather data from South Korea.
  • Traffic: Volume data from road sensors in Melbourne.
  • Stock Market: Daily price fluctuations for 101 major stocks.

Key Results

RASP demonstrated significant improvements in both performance and reliability:

  • Superior Accuracy: In high-variation scenarios, RASP achieved up to 342% greater accuracy (measured by NDCG@5) than its closest competitors.
  • Massive Speedups: RASP consistently outperformed other methods by up to 854×. In large-scale tests involving over 1,000 events, RASP completed tasks in seconds, while other methods either timed out after 27 hours or ran out of memory.
  • Scalability: Unlike competitors that showed exponential growth in resource consumption, RASP’s running time scales predictably with data volume and time spans.
Performance comparison showing RASP's superior accuracy and speed compared to state-of-the-art methods in both stable and noisy conditions.

Conclusion and Future Work

RASP represents a significant step forward in making temporal pattern mining practical for real-world, noisy data. By shifting the burden of optimization from the researcher to the algorithm, it provides a hardware-aware solution that is both faster and more accurate than existing tools.

Future work may focus on reducing pattern redundancy by incorporating "closedness" or "maximality" constraints, ensuring that sub-patterns of larger frequent sequences are filtered out to provide even more concise results.

Summary updated

BibTeX
@inproceedings{choo2025rasp,
  author = {Hyunjin Choo and Minho Eom and Gyuri Kim and Young-Gyu Yoon and Kijung Shin},
  title = {{RASP: Robust Mining of Frequent Temporal Sequential Patterns under Temporal Variations}},
  booktitle = {EDBT},
  year = {2025},
  url = {https://openreview.net/forum?id=MGJwIhFHJU},
}
Figure