Frequent itemset counting using clustered prefixes and index support

• US 7,962,526 B2
• Filed: 08/18/2003
• Issued: 06/14/2011
• Est. Priority Date: 08/18/2003
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Mozes, Ari, Huang, Jiansheng, Li, Wei
• Primary Examiner(s): ALAM, SHAHID AL
• Application Number:
  US10/643,629
• Publication Number:
  US 20050044062A1
• Time in Patent Office: 2,857 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/6, 707/687, 707/803, 706/47
• US Class Current: 707/803
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/284 Relational databases

Abstract

Techniques are provided for (1) extending SQL to support direct invocation of frequent itemset operations, (2) improving the performance of frequent itemset operations by clustering itemset combinations to more efficiently use previously produced results, and (3) making on-the-fly selection of the occurrence counting technique to use during each phase of a multiple phase frequent itemset operation. When directly invoked in an SQL statement, a frequent itemset operation may receive input from results of operations specified in the SQL statement, and provide its results directly to other operations specified in the SQL statement. By clustering itemset combinations, resources may be used more efficiently by retaining intermediate information as long as it is useful, and then discarding it to free up volatile memory. Dynamically selecting an occurrence counting technique allows a single frequent itemset operation to change the occurrence counting technique that it is using midstream, based on cost considerations and/or environmental conditions.

Claims

1. A method for performing a frequent itemset operation, the method comprising the steps of:

performing the frequent itemset operation in a plurality of phases, wherein each phase is associated with combinations that have a particular number of items;

during at least one phase of the plurality of phases, performing the steps of determining candidate combinations that are to be evaluated during the phase;

grouping the candidate combinations into clusters, wherein each cluster corresponds to a common combination of items, and wherein all candidate combinations in a given cluster include the common combination of items associated with the cluster;

processing said candidate combinations, based on said clusters, to determine whether the candidate combinations satisfy a frequency criteria associated with said frequent itemset operation; and

storing, in a computer-readable medium, data that indicates which candidate combinations satisfy the frequency criteria associated with said frequent itemset operation.

2. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 1.

3. The method of claim 1, wherein the step of grouping the candidate combinations into clusters includes the step of establishing an ordering for said candidate combinations by sorting the candidate combinations relative to each other based on the items within each of the candidate combinations.

4. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 3.

5. The method of claim 3, wherein the step of processing the candidate combinations based on the clusters includes processing the candidate combinations in a sequence based on said ordering.

6. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 5.

7. The method of claim 1, wherein the step of grouping the candidate combinations into clusters includes hashing the candidate combinations into buckets based on the items that the candidate combination contain.

8. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 7.

9. The method of claim 1, wherein the step of processing the candidate combinations includes generating bitmaps for the candidate combinations, and determining how many item groups of an item group population include each candidate combination based on the bitmap for the candidate combination.

10. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 9.

11. The method of claim 9, wherein the step of processing the candidate combinations includes, for each cluster, performing the steps of:

generating a bitmap for a particular combination that is a subcombination of all combinations in the cluster;

using the bitmap for the particular combination to generate bitmaps for all combinations in the cluster;

using the bitmap generated for each combination in the cluster to determine how many item groups include the combination; and

after all combinations in the cluster have been processed, discarding from volatile memory the bitmap for the particular combination.

12. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 11.

13. The method of claim 1, wherein the step of processing the candidate combinations includes generating bitmaps for the candidate combinations as the candidate combinations are processed in a sequence, the method further comprising the steps of:

generating one or more intermediary bitmaps for use in generating of a bitmap for a current candidate combination; and

after generating the bitmap for the current candidate combination, retaining in volatile memory only those intermediary bitmaps that are base bitmaps of a next candidate combination in said sequence; and

if any intermediate bitmaps are retained, then using one or more of the intermediary bitmaps to generate a bitmap for the next candidate combination in said sequence.

14. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 13.