Automata Based Skipping for Timed Pattern Matching

17 concepts8 papers1 proposal

When monitoring real-time systems—such as autonomous vehicles, medical devices, or high-frequency trading platforms—we often need to search through massive execution logs to find specific behaviors or anomalies. These logs are not simple strings; they are sequences of "timed words," where each discrete event is bound to a precise, continuous timestamp.

Finding a pattern like "Event A followed by Event B within 2 seconds" traditionally requires a linear scan through the entire log. As noted by Étienne André et al. in Offline timed pattern matching under uncertainty, processing these logs linearly becomes computationally prohibitive as trace lengths grow. To make real-time monitoring practical, we need search algorithms that can achieve sub-linear performance by skipping irrelevant data entirely.

The Intuition of String Skipping

To understand how we can skip data in a continuous-time log, it helps to look at classic string matching. In standard text search, algorithms like Knuth-Morris-Pratt (KMP) or Boyer-Moore avoid checking every single character. For instance, Qi Wu demonstrates how a pre-computed jump table based on pattern prefixes allows a search engine to skip redundant comparisons during character mismatches.

If you are searching for the word CHAIR and encounter a mismatch at the first letter, you don't need to backtrack; you simply slide the search window forward. If you know the internal structure of the pattern, you can determine exactly how far you can safely shift the window without missing a potential match.

Translating Strings to Timed Automata

How do we apply this skipping logic when the data contains continuous time constraints instead of discrete characters? The key insight is to represent the target pattern as a timed automaton—a state machine that tracks both event transitions and clock variables.

Instead of shifting the search window by a fixed number of characters, we shift it based on the structural properties and timing constraints of the automaton. In A Boyer-Moore Type Algorithm for Timed Pattern Matching, Takumi Akazaki et al. adapted suffix-based skip logic to this domain. When the algorithm evaluates a segment of the log and encounters a mismatch at the end of the pattern window, a suffix-based skip function calculates the maximum safe distance to advance.

This safe distance is determined by the minimum length of valid runs within the finite automaton. If a segment of the log fails to match the end of the pattern, the algorithm mathematically proves that no valid match could start within the skipped region, allowing the engine to jump forward rather than checking every intermediate timestamp.

Hybrid and Bidirectional Skipping

To maximize efficiency, the matching engine can analyze both ends of the search window simultaneously. Masaki Waga et al. introduced a hybrid skipping strategy in Efficient Online Timed Pattern Matching by Automata-Based Skipping by adapting the Franek-Jennings-Smyth (FJS) string-matching algorithm. This approach utilizes zone-based abstractions of timed automata to combine prefix and suffix analysis.

Traditional Linear Scan:
[ Window 1 ] -> Check every event
  [ Window 2 ] -> Check every event
    [ Window 3 ] -> Check every event

Automata-Based Skipping:
[ Window 1 ] -> Mismatch detected via Prefix/Suffix analysis
               \_______(Safe Jump Distance)______/
                                                 [ Window 2 ]

Why does this hybrid approach work so well? By identifying mismatches at either the beginning or the end of a potential match window, the algorithm can trigger an immediate forward jump. If the system detects that the timing constraints cannot possibly be satisfied based on the current state and zone abstractions, it bypasses large segments of the event log. This bidirectional skipping results in a twofold increase in processing speed for real-time data streams.

Handling Uncertainty and Scaling Up

The power of automata-based skipping becomes even more apparent when dealing with complex or uncertain specifications. In many real-world scenarios, the exact timing constraints of a system are unknown. Étienne André et al. addressed this in Parametric Timed Pattern Matching, where the goal is to find not just when a pattern occurs, but under what parameters (e.g., finding an unknown deadline $p$). Even with parametric uncertainty, the authors developed dedicated online algorithms that leverage the specification's structure to determine safe jump distances.

As detailed by Étienne André et al. in Online Parametric Timed Pattern Matching with Automata-Based Skipping, traditional state-space exploration tools suffer from severe bottlenecks because they restart the search from the immediate next event after a mismatch. By pre-calculating skip distances directly from the internal structure of the specification automaton, their algorithm bypasses massive data segments where a match is mathematically impossible, achieving orders-of-magnitude speedups over general model-checking frameworks.

This paradigm has been implemented in high-performance tools like MONAA. In MONAA: A Tool for Timed Pattern Matching with Automata-Based Acceleration, Masaki Waga et al. explain that while early skipping mechanisms relied on simplified state abstractions, granular timing analysis allows the tool to pre-compute highly optimized skip tables that maintain a constant memory footprint. More recently, Masaki Waga et al. extended this skipping philosophy to Hyper pattern matching, analyzing the structure of target patterns to skip redundant comparisons across multiple execution traces simultaneously.

By turning the structural and temporal constraints of an automaton into a mathematical roadmap for jumping through data, automata-based skipping transforms real-time log monitoring from an expensive linear chore into an efficient, sub-linear search.

Key Foundational Work

A Boyer-Moore Type Algorithm for Timed Pattern Matching (2016) — contributed 3 concept elements to this direction.
Efficient Online Timed Pattern Matching by Automata-Based Skipping (2017) — contributed 3 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 8 papers
  2. Version 1 · 2026-10-04 · 9 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_bidirectional_pattern_skipping_7cdd2900,
  title = {bidirectional pattern skipping},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bidirectional-pattern-skipping/rdr_7cdd290014d84668849f58475ebd5a21},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_bidirectional_pattern_skipping_7cdd2900_v2,
  title = {bidirectional pattern skipping},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bidirectional-pattern-skipping/rdr_7cdd290014d84668849f58475ebd5a21/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake