Abstract
Mining frequent itemsets has been widely studied over the last decade. Past research focuses on mining frequent itemsets for static transaction databases. It is challenging to extend the technique to the new data stream environment. This environment has the following characteristics: The length of the data stream is infinite, the data arrival rate is high and only limited memory can be used. Because of these characteristics, when we process a data stream, the following restrictions should be obeyed. These include a short response time, the inability to store the complete data stream and no backtracking over data streams is allowed. Under these restrictions, the main difficulty of mining frequent itemsets lies on the way to continuously discover the complete set of the frequent itemsets. In this paper, we propose a new approach for mining frequent itemsets in the time-sensitive sliding window model over data streams with no false alarm or no false dismissal guarantees. A time-sensitive sliding window is a variation of the sliding window, which uses time as the basic counting unit. Our approach consists of a frequent itemset storage structure to capture all possible frequent itemsets, and a discounting table with adaptable sizes to provide approximate counts of the expired data. By constructing and maintaining the storage structure and the discounting table, the complete set of frequent itemsets can therefore be mined. Experiment results demonstrate that the execution time of our approach is small in different minimum support thresholds, different discounting table sizes and different data sets.