Methods for mining frequent items in data streams: an overview
Methods for mining frequent items in data streams: an overview
复制标题
挖掘数据流中频繁项的方法：概述
DOI：
10.1007/s10115-009-0267-2
复制
发表时间：
2011-01-01
影响因子：
2.7
通讯作者：
Han, Jiawei
中科院分区：
文献类型：
--
作者：
Liu, Hongyan;Lin, Yuan;Han, Jiawei
在许多现实应用中，网页点击数据、股票行情数据、传感器网络数据、电话通话记录、流量监控数据等信息都以数据流的形式出现。数据流的在线监测已成为一项重要的研究工作。对于具有广泛应用的流挖掘和数据管理系统来说，估计这些流上的项目频率是一项重要的聚合和汇总技术。本文回顾了从数据流中识别频繁项的方法的最新进展。它描述了频繁项挖掘任务的不同类型的模型。对于收银机和旋转门等通用模型，我们将现有算法分为基于采样、基于计数和基于哈希的类别。描述了每种算法的处理技术和数据概要结构，并通过评估措施进行了比较。因此，作为通用数据流模型的扩展，引入了四种更具体的模型，包括时间敏感模型、分布式模型、层次和多维模型以及倾斜数据模型。介绍了每种模型算法的特点和局限性，并讨论了有待研究和改进的开放问题。
In many real-world applications, information such as web click data, stock ticker data, sensor network data, phone call records, and traffic monitoring data appear in the form of data streams. Online monitoring of data streams has emerged as an important research undertaking. Estimating the frequency of the items on these streams is an important aggregation and summary technique for both stream mining and data management systems with a broad range of applications. This paper reviews the state-of-the-art progress on methods of identifying frequent items from data streams. It describes different kinds of models for frequent items mining task. For general models such as cash register and Turnstile, we classify existing algorithms into sampling-based, counting-based, and hashing-based categories. The processing techniques and data synopsis structure of each algorithm are described and compared by evaluation measures. Accordingly, as an extension of the general data stream model, four more specific models including time-sensitive model, distributed model, hierarchical and multi-dimensional model, and skewed data model are introduced. The characteristics and limitations of the algorithms of each model are presented, and open issues waiting for study and improvement are discussed.