Compressed prefix trees and estDec+ method for finding frequent itemsets over data streams

• US 20070198548A1
• Filed: 11/27/2006
• Published: 08/23/2007
• Est. Priority Date: 11/28/2005
• Status: Active Grant

• Current Assignee: Industry Academic Cooperation Foundation
• Original Assignee: Industry Academic Cooperation Foundation
• Inventors: Lee, Won
• Granted Patent: US 7,610,284 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

Disclosed a relates to a method for finding specific information by analyzing a large amount of data set and a method for finding frequent itemsets in a data mining system realized using the same. The mining in a data stream defined as an indefinite set of data continuously generated is directed to a method for finding valuable knowledge effectively from such data and, recently, various mining methods have been proposed. When considering the characteristics of the data stream in which data elements are indefinitely generated at high speed, these mining methods has an important requirement in that the memory usage required for the performance of the mining process be restricted within an available range. The present invention provides an effective data structure in finding frequent itemsets over data streams and finds necessary information using the data structure. The data structure proposed in the present invention is defined as a compressed prefix tree structure, and the compressed prefix tree merges or splits nodes during the mining operation by comparing the prefix tree structure applied to the conventional data mining to manage a plurality of items in a single node, thus dynamically and flexibly adjusting the tree size. Such dynamic adjustment function dynamically merges and splits nodes in the prefix tree, if the variation of itemsets that are most likely to be frequent itemsets due to the variation of the data stream, thus maximizing the accuracy of the mining result in a restricted memory space, i.e., the accuracy of frequent itemsets found. Moreover, the present invention provides a method for optimizing the memory usage that ensures an optimum mining result within an available memory range using the compressed prefix tree structure.

Claims

1. A method for finding frequent itemsets using a compressed prefix tree structure that manages information on an indefinite data set composed of transactions generated continuously in an application domain and information on itemsets generated in the transactions of the indefinite data set with a single node in a restricted memory space.

2. The method for finding frequent itemsets as recited in claim 1,

wherein the compressed prefix tree comprises four entries including an item list, a parent item list, a maximum frequency count that is a frequency count of a minimum itemset that the first item of the item list indicates, and a minimum frequency count that is a frequency count of a maximum itemset that the last item of the item list indicates.

3. The method for finding frequent itemsets as recited in claim 1 or 2,

wherein the compressed prefix tree further comprises:

a first step of adjusting the size of the restricted memory space to make the most use of the restricted memory space and reducing errors;

a second step of updating a frequency count of an itemset generated in a transaction of a data stream and monitored; and

a third step of inserting an itemset, which is not managed and likely to be a frequent itemset as the itemset appears in many transactions repeatedly, into a new itemset.

4. The method for finding frequent itemsets as recited in claim 3,

wherein the first step varies the size of the restricted memory space to make the most use of the restricted memory space, thus reducing errors generated in the process of estimating a frequency count of a merged itemset.

5. The method for finding frequent itemsets as recited in claim 3,

wherein the second step finds a node based on a depth first finding method, updates the maximum frequency count of the node when a transaction is generated in the minimum itemset of the node, and updates the minimum frequency count of the node when a transaction is generated in the maximum itemset of the node.

6. The method for finding frequent itemsets as recited in claim 5,

wherein the second step further comprises the steps of:

merging two independent nodes, if a support difference is less than a predefined merging gap threshold, to update a frequency count of an itemset in a newly generated transaction in a data stream; and

splitting nodes, if a support difference in a plurality of itemsets managed in a single node exceeds the merging gap threshold.

7. The method for finding frequent itemsets as recited in claim 6,

wherein the step of merging nodes defines a merging threshold having a value greater than a minimum support to preclude a node that indicates an itemset having a support less than the merging threshold.

8. The method for finding frequent itemsets as recited in claim 6,

wherein the step of splitting nodes further comprises the step of estimating a frequency count of an itemset other than a minimum itemset and a maximum itemset, if a node indicates at least three different itemsets, using a maximum frequency count, a minimum frequency count and an estimation function.

9. The method for finding frequent itemsets as recited in claim 8,

wherein the estimation function estimates a frequency count, assuming that the decreased amount of the frequency count according to the increase in length of an itemset is fixed.

10. The method for finding frequent itemsets as recited in claim 8,

wherein the estimation function estimates a frequency count, assuming that the decreased amount of the frequency count according to the increase in length of an itemset becomes smaller as much as the length of the itemset is increased.