Method and apparatus for finding maximal frequent itemsets over data streams

• US 8,150,873 B2
• Filed: 10/27/2008
• Issued: 04/03/2012
• Est. Priority Date: 10/26/2007
• Status: Active Grant

• Current Assignee: Won Suk Lee
• Original Assignee: Industry Academic Cooperation Foundation
• Inventors: Lee, Wong Suk
• Primary Examiner(s): Liang, Vei-Chung
• Application Number:
  US12/258,645
• Publication Number:
  US 20090112863A1
• Time in Patent Office: 1,254 Days
• Field of Search: None
• US Class Current: 707/776
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries

Abstract

A method and apparatus to find maximal frequent itemsets over data streams. A prefix tree manages itemsets and appearance frequencies of the itemsets, and each of nodes of the prefix tree has information about an appearance frequency, a maximum lifetime, and a mark indicating whether the corresponding itemset is a maximal frequent itemset. The method includes: receiving transaction T_k generated at a current point in time; updating the information owned by each node corresponding to the itemset of the transaction T_k among the nodes of the prefix tree; adding each node that is not managed in the prefix tree among nodes corresponding to the itemset of the transaction T_k, to the prefix tree and setting the information on the added nodes; and finding maximal frequent itemsets by visiting each node of the prefix tree that has the mark indicating the maximal frequent itemset and checking whether the corresponding itemset is frequent.

Claims

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_k generated at a current point in time;

(b) updating the information owned by each node corresponding to the itemset of the transaction T_k among the nodes of the prefix tree;

(c) adding each node, which is not managed in the prefix tree among nodes corresponding to the itemset of the transaction T_k, to the prefix tree, and setting the information on the added nodes; and

(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_k, among the nodes of the prefix tree, to indicate the maximal frequent itemset only when a maximum error generated in a process of estimating a support of the maximal frequent itemset is within a maximum error threshold, and

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_k, whose support according to the appearance frequency is equal to or more than a minimum support having a predetermined value.

2. The method of claim 1, wherein the step (b) includes pruning each node of the prefix tree whose support of the corresponding itemset is smaller than a significant support having a predetermined value.

3. The method of claim 1, wherein, in adding each node to the prefix tree, the step (c) estimates the appearance frequency of the itemset of the transaction T_k and adds each node whose support according to the estimated appearance frequency is equal to or larger than a significant support having a predetermined value, to the prefix tree.

4. The method of claim 3, wherein the step (c) includes:

(c1) in connection with a transaction T_k generated by excluding items having smaller support than the significant support among items included in the transaction T_k, estimating the appearance frequency of the itemsets, which are not managed in the prefix tree, among the itemsets included in the transaction T_k and adding the corresponding nodes to the prefix tree when the support according to the estimated appearance frequency is equal to or more than the significant support; and

(c2) when a maximum error generated in the step (c1) of the itemsets corresponding to the added nodes is within a maximum error threshold having a predetermined value, setting each mark of the added nodes so as to indicate the maximal frequent itemset and setting each maximum lifetime of the added nodes.

5. The method of claim 4, wherein the step (c) further includes updating each mark so as not to indicate the maximal frequent itemset in connection with the nodes corresponding to subsets of the itemset corresponding to the node whose mark is set so as to indicate the maximal frequent itemset at the step (c2) and updating the maximum lifetime.

6. The method of claim 1, wherein the step (b) updates each mark so as to indicate the maximal frequent itemset only for the predetermined number of nodes in the order of length of the corresponding itemsets among the nodes corresponding to the maximal frequent itemset.

7. A non-transitory recording medium readable by a computer recording a program for running a method for finding maximal frequent itemsets over data streams, 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_k generated at a current point in time;

(b) updating the information owned by each node corresponding to the itemset of the transaction T_k among the nodes of the prefix tree;

(c) adding each node, which is not managed in the prefix tree among nodes corresponding to the itemset of the transaction T_k, to the prefix tree, and setting the information on the added nodes; and

(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_k, among the nodes of the prefix tree, to indicate the maximal frequent itemset only when a maximum error generated in a process of estimating a support of the maximal frequent itemset is within a maximum error threshold, and

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_k, whose support according to the appearance frequency is equal to or more than a minimum support having a predetermined value.

8. An apparatus for finding maximal frequent itemsets over data streams including continuously generated transactions including:

a memory for storing a prefix tree which manages itemsets included in previously generated transactions and appearance frequencies of the itemsets, wherein 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;

an information updating unit configured to update the information owned by each node corresponding to an itemset of a transaction T_k generated at a current point in time among the nodes of the prefix tree;

an information setting unit configured to add each node which is not managed in the prefix tree among nodes corresponding to the itemset of the transaction T_k, to the prefix tree, and to set the information on the added nodes; and

a maximal frequent itemsets finding unit configured to find maximal frequent itemsets by visiting each node of the prefix tree which has the mark indicating the maximal frequent itemset and to check whether the corresponding itemset is frequent,

wherein the information updating unit allows the mark owned by the node corresponding to the maximal frequent itemset, which belongs to subsets of the itemset of the transaction T_k, among the nodes of the prefix tree, to indicate the maximal frequent itemset only when a maximum error generated in a process of estimating a support of the maximal frequent itemset is within a maximum error threshold, and

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_k, whose support according to the appearance frequency is equal to or more than a minimum support having a predetermined value.

9. The apparatus of claim 8, wherein the information updating unit is configured to prune each node of the prefix tree whose support of the corresponding itemset is smaller than a significant support having a predetermined value.

10. The apparatus of claim 8, wherein the information setting unit is configured to estimate the appearance frequency of the itemset of the transaction T_k and to add each node whose support according to the estimated appearance frequency is equal to or larger than a significant support having a predetermined value, to the prefix tree.

11. The apparatus of claim 10, wherein the information setting unit estimates the appearance frequency of the itemsets, which are not managed in the prefix tree, among the itemsets included in a transaction T_k which is generated by excluding items having smaller support than the significant support among items included in the transaction T_k, and adds the corresponding nodes to the prefix tree when the support according to the estimated appearance frequency is equal to or more than the significant support, when a maximum error generated at time of estimating the appearance frequency of the itemsets corresponding to the added nodes is within a maximum error threshold having a predetermined value, and sets each mark of the added nodes so as to indicate the maximal frequent itemset and setting each maximum lifetime of the added.

12. The apparatus of claim 11, wherein the information setting unit updates each mark so as not to indicate the maximal frequent itemset in connection with the nodes corresponding to subsets of the itemset corresponding to the node whose mark is set so as to indicate the maximal frequent itemset and updates the maximum lifetime.

13. The apparatus of claim 8, wherein the information updating unit updates each mark so as to indicate the maximal frequent itemset only for the predetermined number of nodes in the order of length of the corresponding itemsets among the nodes corresponding to the maximal frequent itemsets T_k-max.