Mining top-K frequent itemsets from data streams

被引：66

作者：

Wong, Raymond Chi-Wing ^{[1
]}

Fu, Ada Wai-Chee ^{[1
]}

机构：

[1] Chinese Univ Hong Kong, Dept Comp Sci & Engn, Shatin, Hong Kong, Peoples R China

来源：

DATA MINING AND KNOWLEDGE DISCOVERY | 2006年 / 13卷 / 02期

关键词：

data mining algorithm; data stream; top K frequent itemset mining; sliding window; Chernoff bound; probabilistic algorithm;

D O I：

10.1007/s10618-006-0042-x

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 [模式识别与智能系统]; 0812 [计算机科学与技术]; 0835 [软件工程]; 1405 [智能科学与技术];

摘要：

Frequent pattern mining on data streams is of interest recently. However, it is not easy for users to determine a proper frequency threshold. It is more reasonable to ask users to set a bound on the result size. We study the problem of mining top K frequent itemsets in data streams. We introduce a method based on the Chernoff bound with a guarantee of the output quality and also a bound on the memory usage. We also propose an algorithm based on the Lossy Counting Algorithm. In most of the experiments of the two proposed algorithms, we obtain perfect solutions and the memory space occupied by our algorithms is very small. Besides, we also propose the adapted approach of these two algorithms in order to handle the case when we are interested in mining the data in a sliding window. The experiments show that the results are accurate.

引用

页码：193 / 217

页数：25