Complete Closed Time Intervals-Related Patterns Mining

Omer David Harel, Robert MoskovitchAAAI 2021 · DOI

Abstract

Mining frequent patterns from temporal data is crucial for domains like healthcare and IoT. However, existing state-of-the-art algorithms often suffer from a "completeness flaw," where they fail to identify all frequent patterns because they only consider the first occurrence of a pattern within a timeline. This paper introduces TIRPClo, a novel algorithm that ensures complete discovery of closed Time Intervals-Related Patterns (TIRPs). By employing a unique sequence representation and an "entities spawning projection" strategy, TIRPClo captures every instance of a pattern. Experimental results on real-world datasets demonstrate that TIRPClo not only fixes the completeness issue—discovering up to 90% more patterns than previous methods—but also achieves significant speedups of 10x to 100x.

Introduction

In many modern data-driven fields, information is represented as Symbolic Time Intervals (STIs). For instance, in medical records, an STI might represent the duration a patient takes a specific drug. In smart homes, it could be the interval a motion sensor is active. Analyzing these intervals to find recurring relationships, known as Time Intervals-Related Patterns (TIRPs), is vital for discovering complex temporal dependencies.

A significant challenge in this field is mining "Closed" TIRPs—compact representations that summarize all frequent patterns without redundancy. While tools like CCMiner have been developed for this purpose, they possess a critical "completeness problem." These algorithms typically stop searching after finding the first instance of a pattern in a sequence. This oversight leads to undercounting the "vertical support" (the number of unique entities exhibiting a pattern), causing the algorithm to discard truly frequent patterns as infrequent.

The Completeness Problem and TIRPClo

The authors identify that ignoring subsequent instances of a pattern within a single timeline prevents the discovery of larger, more complex patterns that those instances might belong to. To address this, they propose TIRPClo, a sequence-based algorithm designed for both efficiency and completeness.

TIRPClo introduces several key innovations:

  1. Non-Ambiguous Sequence Representation: It transforms intervals into "tieps" (time-interval-end-points), such as $A^+$ for a start and $A^-$ for a finish. Unlike previous methods, TIRPClo uses a deterministic representation that strictly maintains chronological order and distinguishes between relations like "before" and "meets" using special markers.
  2. Entities Spawning Projection: This is the core mechanism for ensuring completeness. During database projection, the algorithm "spawns" multiple projections for every instance of a tiep within a record. This ensures that recurring instances are not missed.
  3. Tieps-Index: A memory-efficient hash map provides $O(1)$ access to specific instances of interval endpoints across the database, significantly boosting performance.
Comparison of TIRPClo's sequence representation with other state-of-the-art methods.

Experimental Evaluation

The algorithm was tested on four diverse real-world datasets: American Sign Language (ASL), two Diabetes medical history datasets, and a Smart-home sensor dataset. The Smart-home dataset is particularly challenging due to high "horizontal support," where events repeat frequently within a single timeline.

The results highlight the severity of the completeness issue in existing tools. In the Smart-home dataset, previous "incomplete" methods missed over 90% of frequent closed TIRPs. In the Diabetes datasets, more than two-thirds of patterns were missed at certain support thresholds.

Beyond completeness, TIRPClo demonstrates superior efficiency. At high support thresholds, it is at least 10x faster than CCMiner. At lower thresholds (20-30%), where the search space expands, the speedup reaches factors of 50x to 100x or more.

Runtime performance of TIRPClo compared to CCMiner across four datasets.

Conclusion

TIRPClo represents a significant advancement in temporal pattern mining. By solving the completeness problem, it ensures that researchers do not miss critical insights hidden in repeating temporal sequences. Its combination of a robust sequence representation and efficient indexing allows it to outperform existing state-of-the-art methods by orders of magnitude. Future work will focus on extending this complete discovery approach to all frequent TIRPs and further optimizing performance for extremely dense datasets.

Summary updated

BibTeX
@inproceedings{harel2021complete,
  author = {Omer David Harel and Robert Moskovitch},
  title = {{Complete Closed Time Intervals-Related Patterns Mining}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i5.16531},
}
Figure