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

Textual materials

<10670/1.igsdg1>
KeywordsTriple Keywords
Drama--Plot
Scenarios
Dramatic plots
Novels
Plots (Drama, novel, etc.)
Fiction--Plots
Context (Linguistics)
Grammar, Comparative and general--Context
Situation (Linguistics)
Literature
World literature
Western literature (Western countries)
Belles-lettres

Abstract

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.

...loading
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.