False Positive or False Negative: Mining Frequent Item sets from High Speed Transactional Data Streams Jeffrey Xu Yu, Zhihong Chong, Hongjun Lu, and Aoying Zhou   View Paper (PDF)   Return to RESEARCH SESSION 5:STREAM MINING Abstract The problem of finding frequent items has been recently studied over high speed data streams. However, mining frequent item sets from transactional data streams has not been well addressed yet in terms of its bounds of memory consumption. The main difficulty is due to the nature of the exponential explosion of item sets. Given a domain of Iunique items, the possible number of item sets can be up to2**I-1. When the length of data streams approaches to a very large number N, the possibility of an item set to be frequent becomes larger and difficult to track with limited memory. However, the real killer of effective frequent item set mining is that most of existing algorithms are false-positive oriented. That is, they control memory consumption in the counting processes by an error parameter e, and allow items with support below the specified minimum support s but above s-e counted as frequent ones. Such false-positive items increase the number of false-positive frequent item sets exponentially, which may make the problem computationally intractable with bounded memory consumption. In this paper, we developed algorithms that can effectively mine frequent item(set)s from high speed transactional data streams with a bound of memory consumption. While our algorithms are false-negative oriented, that is, certain frequent item sets may not appear in the results, the number of false-negative item sets can be controlled by a predefined parameter so that desired recall rate of frequent item sets can be guaranteed. We developed algorithms based on Chernoff bound. Our extensive experimental studies show that the proposed algorithms have high accuracy, require less memory, and consume less CPU time. They significantly outperform the existing false-positive algorithms. ©2005 Association for Computing Machinery