Abstract
MONAA is a high-performance tool designed for timed pattern matching, a process used to identify specific sequences of events with timing constraints in large data logs. By adapting classic string-matching "skipping" techniques to timed automata, MONAA achieves significant speedups while maintaining a constant memory footprint. This paper presents the methodology behind MONAA, including its use of timed automata and pre-computed skip tables. Evaluation on automatic transmission system logs demonstrates that MONAA significantly outperforms existing state-of-the-art tools, offering linear scalability and high efficiency for both online and offline monitoring tasks.
Introduction
As systems like autonomous cars and industrial robots become more complex, monitoring their behavior for safety and performance is critical. Engineers often need to search through massive "timed words"—logs of events where each entry has a precise timestamp—to find segments that match specific requirements, such as: "The gear must shift from 1st to 4th while engine RPM is high, all within 10 seconds."
Existing tools for timed pattern matching often struggle with the volume of data, exhibiting slow performance or high memory requirements. Furthermore, live systems require "online" monitoring to detect patterns as data arrives, rather than waiting for the system to finish running. MONAA addresses these challenges by providing a scalable, memory-efficient solution.
Methods
MONAA implements a novel "timed FJS algorithm," inspired by classic string-searching algorithms like Knuth-Morris-Pratt (KMP) and Boyer-Moore. These algorithms speed up searches by "skipping" sections of text that cannot possibly contain a match.
To handle the continuous time domain of timed words, MONAA represents search patterns as Timed Automata (TA)—state machines that track time using clocks. Before the search begins, MONAA pre-computes a skip table by analyzing the pattern to determine how many events it can safely skip based on current observations. This process utilizes "zone constructions" to handle continuous timing constraints. MONAA offers two primary interfaces: a command-line tool for general use and a C++ API (libmonaa) that allows developers to hard-code specifications directly into software for maximum performance.
Evaluation
The researchers evaluated MONAA using logs generated from a Simulink model of an automatic transmission system. The input timed words ranged from 708 to over 1.7 million entries. The test specification involved complex gear changes ($g_1$ through $g_4$) and engine rotation speeds ($\omega$) within specific time windows. MONAA was benchmarked against Montre, a state-of-the-art tool for timed regular expression matching, in both online and offline modes.
Key Results and Discussion
Benchmarks demonstrate that MONAA significantly outperforms existing solutions in terms of execution speed and memory stability. For the largest log (1.7M entries), MONAA's command-line tool (using the TA interface) finished in approximately 4.5 seconds, compared to nearly 290 seconds for Montre's online mode. Using the libmonaa API with a hard-coded specification further reduced the execution time to just 1.07 seconds.
A critical advantage of MONAA is its constant memory footprint. While Montre's offline memory usage grew linearly with the log size, reaching over 166 MB for the largest dataset, MONAA's memory usage remained stable between 7 MB and 16 MB regardless of the data volume. This stability makes MONAA ideal for long-term monitoring of real-time systems.
Conclusion
MONAA provides a scalable solution for real-time monitoring of complex systems. While translation overhead from regular expressions to automata is a current bottleneck for very short logs, the tool's linear time complexity and stable memory usage make it ideal for large-scale data processing. Future work includes refining skipping logic with more sophisticated timing analysis and integrating libmonaa into live control loops for real-time safety enforcement.
Summary updated