A novel hash-based approach for mining frequent itemsets over data streams requiring less memory space |
| |
Authors: | En Tzu Wang Arbee L P Chen |
| |
Affiliation: | (1) Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, ROC;(2) Department of Computer Science, National Chengchi University, Taipei, Taiwan, ROC |
| |
Abstract: | In recent times, data are generated as a form of continuous data streams in many applications. Since handling data streams
is necessary and discovering knowledge behind data streams can often yield substantial benefits, mining over data streams
has become one of the most important issues. Many approaches for mining frequent itemsets over data streams have been proposed.
These approaches often consist of two procedures including continuously maintaining synopses for data streams and finding
frequent itemsets from the synopses. However, most of the approaches assume that the synopses of data streams can be saved
in memory and ignore the fact that the information of the non-frequent itemsets kept in the synopses may cause memory utilization
to be significantly degraded. In this paper, we consider compressing the information of all the itemsets into a structure
with a fixed size using a hash-based technique. This hash-based approach skillfully summarizes the information of the whole
data stream by using a hash table, provides a novel technique to estimate the support counts of the non-frequent itemsets,
and keeps only the frequent itemsets for speeding up the mining process. Therefore, the goal of optimizing memory space utilization
can be achieved. The correctness guarantee, error analysis, and parameter setting of this approach are presented and a series
of experiments is performed to show the effectiveness and the efficiency of this approach. |
| |
Keywords: | Data stream Data mining Frequent itemset Hash-based approach False positive |
本文献已被 SpringerLink 等数据库收录! |
|