An algorithm based on Directed Bit Graph for mining frequent patterns in data stream without candidate generation

作者：Wang Qian^*; Ren Jiadong; He Haitao

来源：ICIC Express Letters, 2013, 7(1): 279-284.

• Bit vector
• Candidate generation
• Data stream
• Database scans
• Directed bit graph
• Frequent pattern
• Growth patterns
• Item sets
• Node units
• Runtimes
• Storage spaces
• Time constraints
• Transaction database

Time constraint supporting, mass candidate itemsets and multiply database scans are usual problems for mining frequent patterns in data streams. In this paper, an algorithm DBG-FPS based on Directed Bit Graph (DBG) for mining Frequent Patterns in data Streams is proposed. DBG-FPS contains two phases. In on line phase, bit vector is used to vertically express the transaction database, and each item is transformed into a bit vector. In off line phase, each DBG node is constructed by an item and its bit vector, counts on the DBG edges are memorized to indicate the number of the corresponding 2-itemsets. Frequent 1-itemsets and 2-itemsets are directly mined according to DBG nodes and edges;frequent 2-itemsets and their bit vectors are recorded by node unit to mine frequent growth patterns. DBG scans the database once without candidate generation and supports time constraint because bits in each vector are sorted by the arriving order of transactions. Experiments show that DBG-FPS is efficient in run time and scalability, and it also has a good performance in storage space.

• 出版日期2013