The Library
Methods for finding frequent items in data streams
Tools
Cormode, Graham and Hadjieleftheriou, Marios (2010) Methods for finding frequent items in data streams. VLDB Journal - The International Journal on Very Large Data Bases, 19 (1). pp. 3-20. doi:10.1007/s00778-009-0172-z ISSN 1066-8888.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/s00778-009-0172-z
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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | VLDB Journal - The International Journal on Very Large Data Bases | ||||
Publisher: | Springer | ||||
ISSN: | 1066-8888 | ||||
Official Date: | February 2010 | ||||
Dates: |
|
||||
Volume: | 19 | ||||
Number: | 1 | ||||
Page Range: | pp. 3-20 | ||||
DOI: | 10.1007/s00778-009-0172-z | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |