Adaptive Frequency Counting over Bursty Data Streams

Abstract

We investigate the problem of frequent itemset mining over a data stream with bursty traffic. In many modern applications, data arrives at a system as a continuous stream of transactions. In many cases, the arrvial rate of transactions fluctuates wildly. Traditional stream mining algorithms, such as Lossy Counting (LC), were generally designed to handle data streams with steady data arrival rates. We show that LC suffers significant loss of accuracy when the data stream is bursty. We propose the Adaptive Frequency Counting algorithm (AFC) to handle bursty data. AFC has a feedback mechanism that dynamically adjusts the mining speed to cope with the changing data arrival rate. Through extensive experiments, we show that AFC outperforms LC under bursty traffics in terms of the accuracy of the set of freqeunt itemsets. © 2007 IEEE.