Paper Info
Title
A fast algorithm for finding frequent episodes in event streams
Abstract
Frequent episode discovery is a popular framework for mining data available as a long sequence of events. Art episode is essentially a short ordered sequence of event types and the frequency of an episode is some suitable measure of how often the episode occurs in the data sequence. Recently, we proposed a new frequency measure for episodes based on the notion of non-overlapped occurrences of episodes in the event sequence, and showed that, such a definition, in addition to yielding computationally efficient algorithms, has some important theoretical properties in connecting frequent episode discovery with HMM learning. This paper presents some new algorithms for frequent episode discovery under this non-overlapped occurrences-based frequency definition. The algorithms presented here are better (by a factor of N, where N denotes the size of episodes being discovered) in terms of both time and space complexities when compared to existing methods for frequent episode discovery. We show through some simulation experiments, that our algorithms are very efficient. The new algorithms presented here have arguably the least possible orders of space and time complexities for the task of frequent episode discovery.
Year
DOI
Venue
2007
10.1145/1281192.1281238
KDD
Keywords
Field
DocType
fast algorithm,frequent episode,event stream,time complexity,simulation experiment,space complexity,electrical engineering
Data mining,Computer science,Algorithm,Artificial intelligence,Event sequence,Hidden Markov model,Temporal data mining,Machine learning
Conference
Citations 
PageRank 
References 
68
2.59
8
Authors
3
Name
Order
Citations
PageRank
Srivatsan Laxman142121.65
P. S. Sastry274157.27
K. P. Unnikrishnan329923.21