Patent ID: 8150873
Filing Date: 2012-04-03
Classification: G06F

Abstract:
1. A method for finding maximal frequent itemsets over data streams including continuously generated transactions, the method comprising: when itemsets included in previously generated transactions and appearance frequencies of the itemsets are managed by a prefix tree and each of nodes of the prefix tree has information about an appearance frequency of an itemset corresponding to each node, a maximum lifetime which is a maximum point in time that allows the corresponding itemset to remain in a frequent state even if the corresponding itemset does not appear later, and a mark indicating whether the corresponding itemset is a maximal frequent itemset, (a) receiving transaction T (b) updating the information owned by each node corresponding to the itemset of the transaction T (c) adding each node, which is not managed in the prefix tree among nodes corresponding to the itemset of the transaction T (d) finding maximal frequent itemsets by visiting each node of the prefix tree which has the mark indicating the maximal frequent itemset, and checking whether the corresponding itemset is frequent; wherein the step (b) allows the mark owned by the node corresponding to the maximal frequent itemset, which belongs to subsets of the itemset of the transaction T wherein the node corresponding to the maximal frequent itemset is a node whose maximum lifetime is updated from before the current point in time k to after the current point in time k or a node not having children nodes corresponding to the itemset of the transaction T