Method and apparatus for dynamically counting large itemsets

• US 6,185,559 B1
• Filed: 05/09/1997
• Issued: 02/06/2001
• Est. Priority Date: 05/09/1997
• Status: Expired due to Fees

• Current Assignee: Hitachi America Limited (Hitachi, Ltd.)
• Original Assignee: Hitachi America Limited (Hitachi, Ltd.)
• Inventors: Brin, Sergey, Tsur, Shalom, Ramkumar, G D
• Primary Examiner(s): HO, RUAY L
• Application Number:
  US08/853,757
• Time in Patent Office: 1,369 Days
• Field of Search: 707/1-10, 707/100-104, 707/200-206
• US Class Current: 707/758
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

The present invention is directed to a data mining method and apparatus that dynamically initiates the counting of sets of items (itemsets) at any time during the pass over the records of a database and terminates the counting at the same location in the next pass. In this manner, the present invention begins to count itemsets early and finishes counting early while keeping the number of different itemsets which are being counted in any pass relatively low.

Claims

1. A method for selectively retrieving records that contain recognizable items from a plurality of records collectively stored seriatim in an electronic database, wherein said method comprises:

reading each record in the electronic database in a substantially sequential flow;

detecting each record that contains a first recognized item;

incrementing a first register to keep track of the records identified as containing said first recognized item;

continuously comparing the number of records in the first register to a preset value to determine if a first threshold has been reached;

reading each record that has been previously identified as containing a first recognized item, wherein the reading of said records containing a first recognized item begins at any record that has been previously identified as containing a first recognized item, and continues in a substantially sequential flow;

detecting in said records containing a first recognized item those records that also contain a second recognized item;

incrementing a second register to keep track of the records identified as containing a set having both of said first and said second recognized items;

continuously comparing the number of records in the second register to a preset value to determine if a second threshold has been reached; and

repeating the above recited steps for sets having a plurality of recognized items until all recognized sets of items having a record count exceeding preset thresholds are detected.

2. A method for selectively retrieving records that contain recognizable items according to claim 1, said method further comprises detecting the last record in the collection of sequentially stored records and recirculating to the first record of the sequentially stored records to continue reading records identified as containing recognized items until each identified record from the collection of sequentially stored records has been read once.

3. A method for selectively retrieving records that contain recognizable items according to claim 2, said method further comprises analyzing the sets of items detected in the records stored in the electronic database to formulate probability rules that are indicative of the frequency association between different items in the plurality of records.

4. A method for selectively retrieving records that contain recognizable items according to claim 2, wherein the identifying and recording of sets of items further comprises storing said register values for each recognized item in a hash tree data structure.

5. A method for selectively retrieving records that contain recognizable items according to claim 1, wherein the detecting of records containing recognized items is performed concurrently by a plurality of processors, each of said processors provided for detecting a separate recognized set of items as it reads a record.

6. A method for selectively retrieving records that contain recognizable items according to claim 5, said method further comprises consolidating among said processors the number of records containing recognized sets of items, by updating each of said processors with the data related to the sets of items detected in the records with the data related to the sets of items detected by each of the other of said processors.

7. A method for selectively retrieving records that contain recognizable items according to claim 6, said method further comprises determining the recognized sets of items to be detected in the records read, after consolidating the data related to the sets of items detected by said plurality of processors.

8. A method of dynamically searching a collection of data records to detect records having sets of items (itemsets) and to form association rules corresponding to the itemsets detected, said method comprising the steps of:

a. reading data records in a seriatim manner;

b. incrementing a separate counter for each itemset detected in a record;

c. reading records that have already been detected as containing an itemset in step a, starting with any record having a first itemset and continuing in a sequential manner through records identified as having a first item set;

d. generating new itemsets;

e. incrementing separate counters for each itemset detected in a record;

f. returning to the beginning of any unread records after reading the last record in the collection of data records;

g. repeating steps a through f until every itemset has been counted; and

h. creating association rules from the itemsets counted in steps a through g.

9. A method of searching a collection of data records according to claim 8, further comprising the step of classifying each itemset detected in a record as a suspected small itemset.

10. A method of searching a collection of data records according to claim 9, further comprising the step of comparing the count of a suspected small itemset to a predetermined threshold, and changing the classification of an itemset designated suspected small to suspected large after the count of a suspected small itemset exceeds the predetermined threshold.

11. A method of searching a collection of data records according to claim 10, further comprising the step of changing a suspected small itemset designation or a suspected large itemset designation to a confirmed small itemset designation or a confirmed large itemset designation, respectively, after every itemset in the collection of records has been counted.

12. A method of searching a collection of data records according to claim 8, further comprising the step of creating a hash tree data array having a plurality of nodes and branches, each path along different branches to a node corresponding to an itemset, wherein the itemset count for each itemset is stored with the corresponding node, such that each of the itemsets and its corresponding count is identified in the hash tree array.

13. A method of searching a collection of data records according to claim 8, wherein the collection of data records is partitioned into separate pluralities of records, and the plurality of records are read individually and concurrently by a plurality of processors.

14. A method of searching a collection of data records according to claim 13, further comprising the step of consolidating itemset counts among the processors the number of records detected as having at least one itemset, by updating each of said processors with the hash tree data array related to the itemsets detected in the records read by each of the other processors.

15. A method of searching a collection of data records according to claim 14, wherein the step of consolidating and updating the plurality of processors comprises performing a parallel vector sum of the hash tree data arrays corresponding to each of the processors in the plurality of processors.

16. A method of searching a collection of data records according to claim 14, further comprising the step of generating new itemsets to be detected based on preselected items or on the count of individual items found in the records already read, after performing the consolidation of the hash tree data arrays related to the itemsets already detected by said plurality of processors.

17. A method of searching a collection of data records according to claim 16, wherein the step of generating new itemsets further comprises generating supersets which include a plurality of itemsets having at least one common item among the itemsets.

18. A programmable general purpose computer apparatus for dynamically searching a file of records collectively stored in an electronic database, wherein said records contain at least one item, the search dynamically determining sets of items (itemsets) and searching for the generated itemsets among the records by starting at any record and reading the records in a sequential flow until all records before and after the initial record in the file are read, said apparatus comprising:

a processor means for performing decision making, control operations and data manipulation;

an array of memory storage means having address inputs and data inputs and outputs, for storing said records in different locations within said memory storage means during the search;

an address generation means having address outputs coupled to the address inputs of said memory storage means, for generating addresses to access different locations within said memory storage means; and

an interface means having address inputs connected to the address outputs of said address generation unit.

19. A programmable general purpose computer apparatus for searching a file of records according to claim 18, further comprising a plurality of counters, wherein each of said counters stores a count of a separate itemset detected by said processor means.

20. A programmable general purpose computer apparatus for searching a file of records according to claim 18, further comprising a plurality of processor means coupled together by a switching means, and a plurality of external storage devices individually coupled to each of said processors, wherein records of said electronic database are stored in said external storage devices.