TL;DR
This paper introduces a novel, highly efficient algorithm for discovering frequent "episodes" (ordered sequences of events) in continuous data streams. By redefining episode frequency based on non-overlapping occurrences, their algorithm achieves significantly better time and space complexity than previous methods, making it a more practical tool for analyzing large-scale event data.
What Problem Does This Paper Address?
In many real-world scenarios, data arrives as a continuous stream of events, each with a timestamp. Examples include network alarms, web navigation logs, or manufacturing plant fault reports. A key task in analyzing such data is "frequent episode discovery," which aims to find recurring patterns or sequences of events that occur "often enough." The challenge lies in efficiently defining and counting these episodes, especially in massive, high-velocity data streams. Traditional methods often struggle with computational complexity, particularly as the length of the episodes or the data stream increases. This paper tackles this by proposing a new algorithm that is orders of magnitude faster and more memory-efficient than existing approaches.
Methods
The core innovation of this paper lies in its new definition of episode frequency and a corresponding algorithm.
- Non-Overlapped Occurrences: Instead of counting every instance an episode appears (which can lead to overlapping events being counted multiple times), the authors define frequency based on non-overlapping occurrences. Two occurrences are non-overlapping if the events constituting one do not fall between the events of the other. The frequency is then the size of the largest set of such non-overlapping occurrences.
- Efficient Counting Algorithm (Algorithm 1 for Serial Episodes): This algorithm uses a single automaton per candidate episode. When an automaton reaches its final state (signifying a complete episode occurrence), its frequency is incremented, and a new automaton for that episode is only initialized when the next event matching the episode's first event type appears. This "one-automaton-at-a-time" approach inherently counts non-overlapping occurrences and drastically reduces memory usage compared to methods that might need multiple automata per episode.
- Algorithm for Parallel Episodes (Algorithm 2): This algorithm extends the non-overlapping concept to parallel episodes, where event order doesn't matter, only their presence. It uses a
waits()list to track partial occurrences and efficiently updates counts.
The algorithms are designed to process the event stream in a single pass, making them suitable for streaming data.
Datasets
The paper uses synthetic data generated for evaluation. This data is created by embedding specific temporal patterns (episodes) into a stream with varying levels of "noise" (random events). This approach allows the authors to control the presence and frequency of target episodes and assess how well their algorithm discovers them. No specific real-world datasets are mentioned for evaluation.
Key Insights and Ideas
- The Power of Non-Overlapping: Redefining frequency to count only non-overlapping occurrences is not just a theoretical nicety; it's the key to unlocking significant algorithmic efficiency. It simplifies the counting process and avoids the computational overhead of managing overlapping instances.
- Single Automaton Efficiency: The insight that a single automaton per episode is sufficient for counting non-overlapping occurrences is crucial. This dramatically reduces the space complexity from O(N|C|) (where N is episode size, C is candidate set) to O(|C|), a substantial improvement.
- Theoretical Connection to Generative Models: The authors highlight that their non-overlapping definition has theoretical advantages, including a formal connection to learning generative models (like Hidden Markov Models) for the data. This can aid in assessing the statistical significance of discovered episodes without needing separate training data.
- Universality of the Approach: The non-overlapping definition is applicable to episodes with any partial order, including serial (ordered) and parallel (unordered) events, suggesting a unified framework.
Key Results
- Time and Space Complexity: The proposed algorithm for serial episodes achieves a time complexity of O(n|C|) and space complexity of O(|C|), where 'n' is the length of the data stream and '|C|' is the number of candidate episodes. This is a significant improvement over previous methods which had complexities dependent on the episode size 'N' (e.g., O(nN|C|)).
- Empirical Speedup: Simulation experiments show substantial speedups. For instance, Table 3 indicates speed-up factors of around 70-80x compared to a windows-based algorithm (Algorithm W) when dealing with larger episode sizes. Table 5 shows speed-ups of up to 49x for longer data sequences.
- Qualitative Similarity: The discovered frequent episodes are qualitatively similar to those found by previous methods, suggesting the new definition doesn't miss important patterns.
- Algorithm 2 Efficiency: While Algorithm 2 for parallel episodes has the same asymptotic complexity as its windows-based counterpart (O(n|C|)), it's noted as the first algorithm for non-overlapping parallel episode frequency counting.
Limitations and Future Work
- General Partial Orders: While the non-overlapping definition is theoretically applicable to general partial orders, the paper notes that designing efficient algorithms for these cases requires further work. This involves developing efficient candidate generation strategies that exploit the anti-monotonicity of non-overlapping episode frequencies.
- Expiry Time Constraints: The current algorithms don't explicitly consider the "spread" of events within an occurrence. The authors suggest that incorporating expiry time constraints (an upper bound on the time difference between events in an occurrence) is a natural extension. This would require modifications to the algorithms, potentially increasing complexity slightly but still remaining efficient.
- No Real-World Datasets: The evaluation relies solely on synthetic data. Testing on diverse real-world datasets would further validate the algorithm's practical performance.
Summary updated