Frequent itemset counting using clustered prefixes and index support

• US 8,352,476 B2
• Filed: 05/19/2011
• Issued: 01/08/2013
• Est. Priority Date: 08/18/2003
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Li, Wei, Huang, Jiansheng, Mozes, Ari
• Primary Examiner(s): ALAM, SHAHID AL
• Application Number:
  US13/111,874
• Publication Number:
  US 20110225166A1
• Time in Patent Office: 600 Days
• Field of Search: 707/745, 707/705, 707/714, 707/724, 707/769, 707/713, 707/803, 707/716, 707/723, 707/727
• US Class Current: 707/745
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/284 Relational databases

Abstract

Techniques are provided for (2) extending SQL to support direct invocation of frequent itemset operations, (3) improving the performance of frequent itemset operations by clustering itemset combinations to more efficiently use previously produced results, and (4) 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 said at least one phase;

processing said candidate combinations to determine whether said candidate combinations satisfy a frequency criteria associated with said frequent itemset operation, wherein the step of processing the candidate combinations includes generating bitmaps for said candidate combinations, wherein the step of processing said candidate combinations to determine whether said candidate combinations satisfy said frequency criteria further comprises the steps of;

creating a bitmap for each item in a particular combination of said candidate combinations;

creating a particular bitmap that represents said particular combination by using the bitmap created for each item;

determining how many item groups include said particular combination based on said particular bitmap for said particular combination; and

determining whether said particular combination satisfies said frequency criteria by determining whether the number of item groups, determined for said particular combination, satisfy a threshold specified in said frequency criteria; and

storing a set of bitmaps that are generated during said at least one phase;

during a subsequent phase of said plurality of phases, performing the steps of;

retrieving bitmaps, from said set of bitmaps, from storage; and

using the retrieved bitmaps to generate bitmaps for candidate combinations of said subsequent phase;

wherein the steps of the method are performed by one or more computing devices.

2. The method of claim 1 wherein:

storing said set of bitmaps includes storing said set of bitmaps in an index on said storage; and

using the retrieved bitmaps includes using bitmaps retrieved from said index.

3. The method of claim 2, further comprising the step of storing said index on non-volatile memory.

4. The method of claim 3, further comprising the step of:

during said subsequent phase of said plurality of phases, retrieving the bitmaps from said index into volatile memory.

5. The method of claim 2, wherein the step of storing said set of bitmaps includes using a combination associated with a bitmap as an index key for determining where, within said index, to place an entry for said bitmap.

6. The method of claim 5, wherein the step of creating said particular bitmap comprises performing one or more AND operations over those bitmaps which are created for each item in said particular combination.

7. The method of claim 5, wherein each value in said particular bitmap indicates whether said particular combination exists or does not exist in a given item group.

8. The method of claim 5, wherein:

during said at least one phase of said plurality of phases, further performing the steps of;

creating a first bitmap that represents a first combination of said candidate combinations; and

creating a second bitmap that represents a second combination of said candidate combinations;

during said subsequent phase of said plurality of phases, further performing the step of creating a third bitmap that represents a third combination of said subsequent phase based on said first bitmap and said second bitmap, wherein said third combination includes more items than said first combination and more items than said second combination.

9. The method of claim 8, wherein the step of creating said third bitmap comprises performing an AND operation over said first bitmap and said second bitmap.

10. The method of claim 1, wherein:

said at least one phase is a phase associated with N-item combinations; and

said set of bitmaps includes bitmaps associated with all N-item combinations that satisfy said frequency criteria.

11. A non-transitory computer-readable storage medium storing one or more sequences of instructions comprising instructions which, when executed by one or more processors, cause:

performing a 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 instructions that cause;

determining candidate combinations that are to be evaluated during said at least one phase;

processing said candidate combinations to determine whether said candidate combinations satisfy a frequency criteria associated with said frequent itemset operation, wherein processing the candidate combinations includes generating bitmaps for said candidate combinations, wherein the instructions that cause processing said candidate combinations to determine whether said candidate combinations satisfy said frequency criteria further comprise instructions which, when executed by the one or more processors, cause;

creating a bitmap for each item in a particular combination of said candidate combinations;

creating a particular bitmap that represents said particular combination by using the bitmap created for each item;

determining how many item groups include said particular combination based on said particular bitmap for said particular combination; and

determining whether said particular combination satisfies said frequency criteria by determining whether the number of item groups, determined for said particular combination, satisfy a threshold specified in said frequency criteria; and

storing a set of bitmaps that are generated during said at least one phase;

during a subsequent phase of said plurality of phases, performing instructions that cause;

retrieving bitmaps, from said set of bitmaps, from storage; and

using the retrieved bitmaps to generate bitmaps for candidate combinations of said subsequent phase.

12. The non-transitory computer-readable storage medium of claim 11, wherein:

the instructions that cause storing said set of bitmaps include instructions which, when executed by the one or more processors, cause storing said set of bitmaps in an index on said storage; and

the instructions that cause using the retrieved bitmaps include instructions which, when executed by the one or more processors, cause using bitmaps retrieved from said index.

13. The non-transitory computer-readable storage medium of claim 12, wherein the one or more sequences of instructions further comprise instructions which, when executed by the one or more processors, cause storing said index on non-volatile memory.

14. The non-transitory computer-readable storage medium of claim 13, wherein the one or more sequences of instructions further comprise instructions which, when executed by the one or more processors, cause:

during said subsequent phase of said plurality of phases, retrieving the bitmaps from said index into volatile memory.

15. The non-transitory computer-readable storage medium of claim 12, wherein the instructions that cause storing said set of bitmaps include instructions which, when executed by the one or more processors, cause using a combination associated with a bitmap as an index key for determining where, within said index, to place an entry for said bitmap.

16. The non-transitory computer-readable storage medium of claim 15, wherein the instructions that cause creating said particular bitmap comprise instructions which, when executed by the one or more processors, cause performing one or more AND operations over those bitmaps which are created for each item in said particular combination.

17. The non-transitory computer-readable storage medium of claim 15, wherein each value in said particular bitmap indicates whether said particular combination exists or does not exist in a given item group.

18. The non-transitory computer-readable storage medium of claim 15, wherein:

the instructions performed during said at least one phase of said plurality of phases further comprise instructions which, when executed by the one or more processors, cause;

creating a first bitmap that represents a first combination of said candidate combinations; and

creating a second bitmap that represents a second combination of said candidate combinations;

the instructions performed during said subsequent phase of said plurality of phases further comprise instructions which, when executed by the one or more processors, cause creating a third bitmap that represents a third combination of said subsequent phase based on said first bitmap and said second bitmap, wherein said third combination includes more items than said first combination and more items than said second combination.

19. The non-transitory computer-readable storage medium of claim 18, wherein the instructions that cause creating said third bitmap comprise instructions which, when executed by the one or more processors, cause performing an AND operation over said first bitmap and said second bitmap.

20. The non-transitory computer-readable storage medium of claim 11, wherein:

said at least one phase is a phase associated with N-item combinations; and

said set of bitmaps includes bitmaps associated with all N-item combinations that satisfy said frequency criteria.