A survey on algorithms for mining frequent itemsets over data streams
A survey on algorithms for mining frequent itemsets over data streams
复制标题
DOI：
10.1007/s10115-007-0092-4
复制
发表时间：
2008-07-01
影响因子：
2.7
通讯作者：
Ng, Wilfred
中科院分区：
文献类型：
--
作者：
Cheng, James;Ke, Yiping;Ng, Wilfred
数据流在欺诈检测和趋势学习等高级应用中的日益突出，导致了对频繁项集（FI）的在线挖掘的研究。与挖掘静态数据库不同，挖掘数据流带来了许多新的挑战。除了数据流的一次扫描特性、无限内存需求和高数据到达率外，项集的组合爆炸也加剧了挖掘任务。FI挖掘问题的高度复杂性阻碍了流挖掘技术的应用。我们认识到，现有的技术是必要的，以设计和开发有效的挖掘算法和数据结构，能够匹配的处理速度的挖掘与数据流的高到达率的关键审查。在一组统一的符号和术语，我们在本文中描述的努力和主要技术挖掘数据流，并提出了一个全面的调查的一些国家的最先进的算法挖掘频繁项集的数据流。我们根据流挖掘技术采用的窗口模型将其分为两类，以便深入了解这些技术如何以及为什么有用。然后，我们进一步分析的算法，根据它们是否是精确的或近似的，对于近似的方法，它们是否是假阳性或假阴性。我们还讨论了各种有趣的问题，包括现有研究的优点和局限性以及未来研究的实质性领域。
The increasing prominence of data streams arising in a wide range of advanced applications such as fraud detection and trend learning has led to the study of online mining of frequent itemsets (FIs). Unlike mining static databases, mining data streams poses many new challenges. In addition to the one-scan nature, the unbounded memory requirement and the high data arrival rate of data streams, the combinatorial explosion of itemsets exacerbates the mining task. The high complexity of the FI mining problem hinders the application of the stream mining techniques. We recognize that a critical review of existing techniques is needed in order to design and develop efficient mining algorithms and data structures that are able to match the processing rate of the mining with the high arrival rate of data streams. Within a unifying set of notations and terminologies, we describe in this paper the efforts and main techniques for mining data streams and present a comprehensive survey of a number of the state-of-the-art algorithms on mining frequent itemsets over data streams. We classify the stream-mining techniques into two categories based on the window model that they adopt in order to provide insights into how and why the techniques are useful. Then, we further analyze the algorithms according to whether they are exact or approximate and, for approximate approaches, whether they are false-positive or false-negative. We also discuss various interesting issues, including the merits and limitations in existing research and substantive areas for future research.