False Positive or False Negative

This chapter addresses the issue of mining frequent patterns from transactional data streams—the problem of frequent data stream pattern mining (FDPM). While most existing algorithms in mining frequent items for data streams using false-positive oriented approaches to control the error on the estimated frequency of mined patterns and memory requirement, a new paradigm in FDPM is explored—the false-negative oriented approach. That is, the data mining process is controlled by limiting the probability of a frequent pattern that is missed in the result, but all mined patterns are frequent. The chapter introduces both frequent item and item-set mining algorithms using the Chernoff bound. The bound enables pruning infrequent patterns from the continuously arriving transactions with the guarantee of the required recall rate of frequent patterns.