关键词: Chernoff Bound，数据流，频繁项集

Abstract: A data stream is fast, unlimited and dynamic, these characteristics constraint the computational resources and storages when mining frectuent itemsets. This paper addressed this problem and proposed a simple and effective algorithm AFIoDS, AFIoDS is an approximate algorithm based on sliding window model, which splits stream data into batches and maintains them with 2-tuple lists;thus,a false negative result can be obtained using a probabilistic parameterbased on chernoff bound. The approximation will be changed dynamically to guarantee the mining frequent itemsets are error controllable. Plus, a compression of frequent itemsets, the closed frequent itemsets, arc employed to represent the results of each batch for further memory saving. Our experimental results on 3 real world data show that without precision reduction, AFIoDS achieves a faster speed and a much reduced memory cost in comparison with the statcof-thcart algorithms.

Key words: Chernoff bound, Data stream, Frequent itemset