A general streaming algorithm for pattern discovery

作者：Patnaik Debprakash^*; Laxman Srivatsan; Chandramouli Badrish; Ramakrishnan Naren

来源：Knowledge and Information Systems, 2013, 37(3): 585-610.

DOI：10.1007/s10115-013-0669-z

• Event sequences
• Data streams
• Frequent patterns
• Pattern discovery
• Streaming algorithms
• Approximation algorithms

Discovering frequent patterns 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 patterns over a window of recent events in the stream. We derive approximation guarantees for our algorithm in terms of: (i) the separation of frequent patterns from the 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.

• 出版日期2013-12
• 单位美国弗吉尼亚理工大学(Virginia Tech); Microsoft