Discovery of frequent episodes in event sequences

Heikki Mannila, Hannu Toivonen, and A. Inkeri Verkamo: Discovery of frequent episodes in event sequences. Report C-1997-15, Department of Computer Science, University of Helsinki, February 1997. 45 pages. <http://www.cs.helsinki.fi/TR/C-1997/15>

Full paper: gzip'ed Postscript file
Metadata: XML file

Abstract

Sequences of events describing the behavior and actions of users or systems can be collected in several domains. We consider the problem of discovering frequently occurring episodes in such sequences. An episode is defined to be a collection of events that occur relatively close to each other in a given partial order. Once such episodes are known, one can produce rules for describing or predicting the behavior of the sequence. We give efficient algorithms for the discovery of all frequent episodes from a given class of episodes, and present extensive experimental results. The methods are in use in telecommunication alarm management.

Index Terms

Categories and Subject Descriptors:
H.3.1 Content Analysis and Indexing
F.2.2 Nonnumerical Algorithms and Problems
I.2.6 Learning
C.2.3 Network Operations

General Terms: Algorithms, Experimentation

Additional Key Words and Phrases: Knowledge Discovery, Data Mining, Event Sequences, Frequent Episodes, Sequence Analysis