Finding frequent items in data streams
Citations Over TimeTop 1% of 2008 papers
Abstract
The frequent items problem is to process a stream of items and find all items occurring more than a given fraction of the time. It is one of the most heavily studied problems in data stream mining, dating back to the 1980s. Many applications rely directly or indirectly on finding the frequent items, and implementations are in use in large scale industrial systems. However, there has not been much comparison of the different methods under uniform experimental conditions. It is common to find papers touching on this topic in which important related work is mischaracterized, overlooked, or reinvented. In this paper, we aim to present the most important algorithms for this problem in a common framework. We have created baseline implementations of the algorithms, and used these to perform a thorough experimental study of their properties. We give empirical evidence that there is considerable variation in the performance of frequent items algorithms. The best methods can be implemented to find frequent items with high accuracy using only tens of kilobytes of memory, at rates of millions of items per second on cheap modern hardware.
Related Papers
- → A New Approach for Maximal Frequent Sequential Patterns Mining Over Data Streams(2011)13 cited
- → Online data stream Mining of Recent Frequent Itemsets based on Sliding Window model(2008)8 cited
- → Mining Closed Regular Patterns in Data Streams(2013)1 cited
- Review of association rules mining in data streams(2010)
- → Mining unusual data over data streams(2010)