DSM-FI: an efficient algorithm for mining frequent itemsets in data streams

Hua-Fu Li, Man-Kwan Shan, Suh-Yin Lee

Research output: Contribution to journalArticlepeer-review

41 Scopus citations

Abstract

Online mining of data streams is an important data mining problem with broad applications. However, it is also a difficult problem since the streaming data possess some inherent characteristics. In this paper, we propose a new single-pass algorithm, called DSM-FI (data stream mining for frequent itemsets), for online incremental mining of frequent itemsets over a continuous stream of online transactions. According to the proposed algorithm, each transaction of the stream is projected into a set of sub-transactions, and these sub-transactions are inserted into a new in-memory summary data structure, called SFI-forest (summary frequent itemset forest) for maintaining the set of all frequent itemsets embedded in the transaction data stream generated so far. Finally, the set of all frequent itemsets is determined from the current SFI-forest. Theoretical analysis and experimental studies show that the proposed DSM-FI algorithm uses stable memory, makes only one pass over an online transactional data stream, and outperforms the existing algorithms of one-pass mining of frequent itemsets.
Original languageEnglish
Pages (from-to)79-97
Number of pages9
JournalKnowledge and Information Systems
Volume17
Issue number1
DOIs
StatePublished - Oct 2008

Fingerprint Dive into the research topics of 'DSM-FI: an efficient algorithm for mining frequent itemsets in data streams'. Together they form a unique fingerprint.

Cite this