The problem of finding frequent items has been recently studied over high speed datastreams. However, mining frequent iteinsetsfroIn transactional data streams has not beenwell addressed yet in terms of its bounds ofmemory consumption. The main difficulty isdue to the nature of the exponential explo-sion of itemsets. Given a domain of uniqueitems, the possible number of itemsets can beup to 2i-i. When the length of data stremsapproaches to a very large number N, thepossibility of an itemset to be frequent be-comes larger and difficult to track with lim-ited memory. However. the real killer of ef-fective frequent itemset mining is that mostof existing algorithms are false-positive ori-nted. That is, they control memory con-sumption in the counting processes by an er-ror arameter e, aud allow items with sup-port below the specified minimum support s but above s-e counted as frequent ones. Such false-positive items increase the num- ber of false-positive frequent itemsets expo-nentially, which rn, make the problem com- putationally intractable with bounded mem-ory consumption. In this paper, we developed algorithms that can effectively mine fl'equent item(set)s from high speed transactional datastreams with a bound of memory consump-tion. While our algorithms are false-negative oriented, that is, certain frequent itemsets may not appear in the zesults, the number of false-negative itemsets can be controlled by a predefined parameter so that desired recall rate of frequent itemsets can be guaranteed. We developed algorithms based on Chernoff bound. Our extensive experimental studies