Search publications, data, projects and authors
Streaming Algorithms for Pattern Discovery over Dynamically Changing Event Sequences

Textual materials

KeywordsTriple Keywords
Dramatic plots
Plots (Drama, novel, etc.)
Context (Linguistics)
Grammar, Comparative and general--Context
Situation (Linguistics)
World literature
Western literature (Western countries)


Discovering frequent episodes over event sequences is an important data mining task. In many applications, events constituting the data sequence arrive as a stream, at furious rates, and recent trends (or frequent episodes) can change and drift due to the dynamical nature of the underlying event generation process. The ability to detect and track such the changing sets of frequent episodes can be valuable in many application scenarios. Current methods for frequent episode discovery are typically multipass algorithms, making them unsuitable in the streaming context. In this paper, we propose a new streaming algorithm for discovering frequent episodes over a window of recent events in the stream. Our algorithm processes events as they arrive, one batch at a time, while discovering the top frequent episodes over a window consisting of several batches in the immediate past. We derive approximation guarantees for our algorithm under the condition that frequent episodes are approximately well-separated from infrequent ones in every batch of the window. We present extensive experimental evaluations of our algorithm on both real and synthetic data. We also present comparisons with baselines and adaptations of streaming algorithms from itemset mining literature.

Report a bug

Under construction

We're in Beta!

The GoTriple platform is still in Beta and we keep adding new features everyday. Check the project's website to see what's new and subscribe to our Mailing List.