An algorithm based on bit vector decomposition and hash linklist for mining frequent patterns in data streams

Most of algorithms based on bit vector for mining frequent pattern always produce candidate itemsets and scan the same data repeatedly; this increases the running time and the space consumption. In this paper, an algorithm BVDAHL based on bit vector decomposition and hash linklist for mining frequent patterns on data streams which solves the above issues, is proposed. The itemsets (transactions) whose corresponding number of 1 is k, denoted as k-one itemsets (k-one transactions). The arrival transactions are converted into bit vectors, and permutations and combinations are used to decompose converted results, then the decomposed itemsets are stored in the hash linklist. In hash function, according to the position of 1 of bit vector to compute the address, if the transaction has same address and same content that already exists in data domain, then the value adds one in count domain, otherwise the pointer in pointer domain points to the next node directly, it is no need to deal with conflict. Afterwards the property of anti-monotonic will be used to prune the k+1-one transactions in bit vector table if there exists infrequent k-one itemsets that decomposed by such k+1-one transactions. Then the algorithm repeats the above processes until the transaction in bit vector table can not be decomposed. Finally we will receive the frequent itemsets by comparing the obtained value of count domain in hash linklist with minSup. Experiment results show that BVDAHL is very efficiency and scalable.