Finding Frequent Items in Data Streams
Finding Frequent Items in Data Streams
复制标题
DOI：
10.14778/1454159.1454225
复制
发表时间：
2008-08-01
影响因子：
2.5
通讯作者：
Hadjieleftheriou, Marios
中科院分区：
文献类型：
--
作者：
Cormode, Graham;Hadjieleftheriou, Marios
频繁项问题是处理一个项流，并找到所有超过给定时间部分出现的项。它是数据流挖掘中研究最多的问题之一，可以追溯到20世纪80年代。许多应用程序直接或间接地依赖于查找频繁项，并且在大型工业系统中使用了实现。然而，在统一的实验条件下，对不同方法的比较还不多见。这是常见的发现论文触及这一主题，其中重要的相关工作被错误地描述，忽视，或重新发明。在本文中，我们的目标是在一个共同的框架中提出解决这个问题的最重要的算法。我们已经创建了算法的基线实现，并使用这些算法对其特性进行了彻底的实验研究。我们给出的经验证据表明，在频繁项目算法的性能有相当大的变化。在廉价的现代硬件上，以每秒数百万项的速度，只需使用几十千字节的内存，就可以实现以高精度查找频繁项的最佳方法。
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.