Abstract | ||
---|---|---|
Discovering frequent episodes over event sequences is an important data mining problem. Existing methods typically require multiple passes over the data, rendering them unsuitable for streaming contexts. We present the first streaming algorithm for mining frequent episodes over a window of recent events in the stream. We derive approximation guarantees for our algorithm in terms of: (i) the separation of frequent episodes from infrequent ones, and (ii) the rate of change of stream characteristics. Our parameterization of the problem provides a new sweet spot in the tradeoff between making distributional assumptions over the stream and algorithmic efficiencies of mining. We illustrate how this yields significant benefits when mining practical streams from neuroscience and telecommunications logs. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1109/ICDM.2012.84 | ICDM |
Keywords | Field | DocType |
new sweet spot,practical stream,multiple pass,distributional assumption,important data mining problem,efficient episode mining,algorithmic efficiency,approximation guarantee,frequent episode,dynamic event streams,event sequence,stream characteristic,streaming algorithms,data mining,approximation algorithms,data streams | Data mining,Approximation algorithm,Data stream mining,Streaming algorithm,Computer science,Artificial intelligence,Rendering (computer graphics),STREAMS,Episode mining,Machine learning | Conference |
ISSN | Citations | PageRank |
1550-4786 | 9 | 0.52 |
References | Authors | |
14 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Debprakash Patnaik | 1 | 191 | 14.89 |
Srivatsan Laxman | 2 | 421 | 21.65 |
Badrish Chandramouli | 3 | 522 | 42.85 |
Naren Ramakrishnan | 4 | 1913 | 176.25 |