Traditional sequential pattern mining treats time as a binary constraint: event $B$ either happens after event $A$, or it does not. While this ordinal perspective ($A \rightarrow B \rightarrow C$) captures the chronological flow of events, it discards a critical dimension of real-world data: how much time elapsed between them?
Consider a medical scenario where a patient takes a medication and later experiences a side effect. If the side effect occurs three hours later, it indicates an acute reaction; if it occurs three months later, it is likely an unrelated event. As Qazi et al. point out in Discovering Temporal Patterns from Insurance Interaction Data, the specific duration between events often serves as a more powerful predictor of outcomes than the mere occurrence or order of the events themselves.
The Core Mechanism: Temporally Annotated Sequences
To capture these dynamics, researchers have shifted from mining simple ordered sequences to mining Temporally Annotated Sequences (TASs). First formalized by Pedreschi et al. in Efficient Mining of Temporally Annotated Sequences, this paradigm shifts time from a background search constraint to an intrinsic part of the pattern itself. Instead of discovering a pattern like $\langle A, B \rangle$, a TAS algorithm extracts $\langle A \xrightarrow{\Delta t_1} B \rangle$, where $\Delta t_1$ represents the typical time interval between the events.
By integrating event sequences with explicit time intervals, algorithms can predict not only what event will happen next, but also when it will happen, as demonstrated by the authors of Generalized Features: Their Application to Classification.
Ordinal Sequence: [Event A] -------------------------> [Event B]
(Time is just an arrow)
Temporally Annotated: [Event A] -------- Δt = 3 days --------> [Event B]
(Time is a measurable distance)
The Challenge of Real-World Sequences: Gaps and Interleaving
When we move from clean, synthetic data to real-world event streams, patterns rarely occur in isolation. Unrelated or redundant actions frequently interleave with the target behavior. If an algorithm requires strict, immediate succession, it will fail to find meaningful long-term structures.
To solve this, temporal sequence mining algorithms must permit temporal gaps between elements. For instance, in complex strategic environments like real-time strategy games, Michael Leece utilized a sequence mining framework that allows for variable gaps to successfully discover high-level strategic patterns despite the noise of low-level micro-actions (Sequential Pattern Mining in StarCraft: Brood War for Short and Long-Term Goals). Similarly, in computer vision, Wang et al. leveraged variable temporal gaps between key skeletal poses to make action recognition invariant to variations in human execution speed (Mining 3D Key-Pose-Motifs for Action Recognition).
However, allowing arbitrary gaps introduces a risk: the model might mistakenly link two entirely coincidental events simply because they occur in the same broad temporal vicinity. To prevent this type of overfitting, Vreeken et al. introduced explicit penalties for temporal gaps within a Minimum Description Length (MDL) framework (The long and the short of it: summarising event sequences with serial episodes). By penalizing excessively large or irregular gaps, the model ensures that discovered episodes represent genuine structural dependencies rather than background noise.
Beyond Simple Gaps: Rich Temporal Dimensions
Representing temporal patterns effectively requires looking beyond a single interval value. Real-world processes exhibit complex temporal relationships like event containment, partial overlaps, or varying durations. Ho et al. note in Efficient Temporal Pattern Mining in Big Time Series Using Mutual Information that traditional sequence mining fails when confronted with these sophisticated behaviors.
To address this expressiveness gap, Zheng et al. proposed a General Similarity Measurement (GSM) in Matching State-Based Sequences with Rich Temporal Aspects that characterizes sequences across three non-redundant dimensions:
- State Order: The chronological sequence of states.
- State Duration: How long each individual state lasts.
- Gap Duration: The precise time elapsed between states.
Furthermore, moving from broad time windows to exact temporal offsets allows for highly precise logistics and planning. Zhu et al. demonstrate in Targeted Mining Precise-positioning Episode Rules that a fixed-gap approach can pinpoint the exact timing of subsequent target events. Conversely, instead of looking for fixed intervals, Sontheim et al. model the deviation from the norm, creating a "temporal deviation signature" vector that captures whether a specific sequence execution was faster or slower than average (Temporal Deviations on Event Sequences).
Why It Works: Applications and Predictive Power
Why go through the mathematical trouble of tracking these intervals? Because the temporal spacing of actions carries latent information about the underlying intent, system state, or physical constraints that ordinal data completely hides.
In deep learning, incorporating these intervals directly resolves representation bottlenecks. For example, Xu et al. developed TimelyGPT (TimelyGPT: Recurrent Convolutional Transformer for Long Time-series Representation) to model irregular longitudinal patient trajectories, proving that the specific timing of clinical observations is just as informative as the clinical data itself. Similarly, Kwon et al. introduced RetainEX in RetainVis: Visual Analytics with Interpretable and Interactive Recurrent Neural Networks on Electronic Medical Records, demonstrating that explicitly feeding time intervals into recurrent neural networks significantly boosts health risk prediction accuracy.
This predictive lift spans multiple domains:
- Behavioral Computing: Cao et al. show that sequence classifiers optimized to account for temporal gaps yield far more precise models of human intent and time-sensitive behaviors (Special issue on behavior computing).
- Anomaly Detection: Jiang et al. demonstrate that smart home security systems can detect subtle anomalies—such as a resident taking unusually long to move from the bedroom to the bathroom—by augmenting event sequences with inter-event intervals (Effective Anomaly Detection in Smart Home by Integrating Event Time Intervals).
- Social Signal Synthesis: Janssoone et al. utilize temporal association rules to capture the precise timing and sequence of multimodal social signals, enabling conversational agents to exhibit realistic interpersonal stances (Using Temporal Association Rules for the Synthesis of Embodied Conversational Agents with a Specific Stance).
Ultimately, by treating time as a continuous, measurable distance rather than a simple ordering mechanism, these approaches transform sequence mining from a tool that merely tracks what happened into a framework that understands how things unfold.
Key Foundational Work
Efficient Mining of Temporally Annotated Sequences (2006) — contributed 4 concept elements to this direction.
Generalized Features: Their Application to Classification (2002) — contributed 3 concept elements to this direction.