False-Negative Frequent Items Mining from Data Streams with Bursting

False-negative frequent items mining from a high speed transactional data stream is to find an approximate set of frequent items with respect to a minimum support threshold, s. It controls the possibility of missing frequent items using a reliability parameter δ. The importance of false-negative frequent items mining is that it can exclude false-positives and therefore significantly reduce the memory consumption for frequent itemsets mining. The key issue of false-negative frequent items mining is how to minimize the possibility of missing frequent items. In this paper, we propose a new false-negative frequent items mining algorithm, called Loss-Negative, for handling bursting in data streams. The new algorithm consumes the smallest memory in comparison with other false-negative and false-positive frequent items algorithms. We present theoretical bound of the new algorithm, and analyze the possibility of minimization of missing frequent items, in terms of two possibilities, namely, in-possibility and out-possibility. The former is about how a frequent item can possibly pass the first pruning. The latter is about how long a frequent item can stay in memory while no occurrences of the item comes in the following data stream for a certain period. The new proposed algorithm is superior to the existing false-negative frequent items mining algorithms in terms of the two possibilities. We demonstrate the effectiveness of the new algorithm in this paper.

Authors and Affiliations

1. Fudan University, China

   Zhihong Chong, Zhengjie Zhang & Aoying Zhou

2. Chinese University of Hong Kong, China

   Jeffrey Xu Yu

3. Hong Kong University of Science and Technology, China

   Hongjun Lu

Editors and Affiliations

1. Research Institute of Information Technology, Tsinghua National Laboratory for Information Science and Technology, Department of Computer Science and Technology, Tsinghua University, 100084, Beijing, China

   Lizhu Zhou

2. National University of Singapore, Singapore

   Beng Chin Ooi

3. School of Information, Renmin University of China,  

   Xiaofeng Meng

Reprints and permissions

© 2005 Springer-Verlag Berlin Heidelberg

Policies and ethics