Under consideration for publication in Knowledge and Information Systems A General Streaming Algorithm for Pattern Discovery

Abstract. Discovering frequent patterns over event sequences is an important data mining problem. Existing methods typically require multiple passes over the data, ren-dering 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 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 mak-ing 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