Frequent itemset counting using subsets of bitmaps

• US 7,756,853 B2
• Filed: 08/27/2004
• Issued: 07/13/2010
• Est. Priority Date: 08/18/2003
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Jakobsson, Hakan, Li, Wei, Mozes, Ari W.
• Primary Examiner(s): Ly; Cheyne D
• Application Number:
  US10/927,893
• Publication Number:
  US 20050050077A1
• Time in Patent Office: 2,146 Days
• Field of Search: 707/2, 707/3, 707/102
• US Class Current: 707/713
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases

Abstract

A method and mechanism for performing improved frequent itemset operations is provided. A set of item groups are divided into a plurality of subsets. Each item group is composed of a set of data items. Possible combinations of data items that may frequently appear together in the same item group are referred to as candidate combinations. Candidate combinations comprising a first set of data items are identified, and thereafter the occurrence of each candidate combination in any item group in each subset is counted by comparing item bitmaps, associated with items in the candidate combination, in each subset in turn. The comparison of item bitmaps is performed in volatile memory. A total frequent itemset count that describes the frequency of candidate combinations in items groups across all subsets is obtained. Thereafter, the total frequent itemset count for candidate combinations having a larger number of data items may be determined.

Claims

1. A machine-implemented method, comprising:

assigning each item group, within a set of item groups, to one of a plurality of item group subsets based at least in part on an amount of volatile memory available in a computer system, wherein each item group subset includes one or more entire item groups,

wherein each item group is associated with an item group bitmap that indicates which items, of a set of items, belong in said item group;

determining a set of candidate combinations of two or more items from the set of items;

for each candidate combination of two or more items in said set of candidate combinations, performing the step of;

in each item group subset, comparing an item bitmap associated with an item in the candidate combination with each other item bitmap associated with one or more other items in the candidate combination, to determine a partial frequent itemset count for the candidate combination in the item group subset, wherein the partial frequent itemset count comprises the total number of item groups in the item group subset that contain the candidate combination;

combining the partial frequent itemset counts of the item group subsets to derive a total frequent itemset count for the set of candidate combinations; and

storing said total frequent itemset count in a volatile or non-volatile computer-readable storage medium;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, wherein the step of assigning each item group comprises:

determining how many item group subsets are in the plurality of item group subsets based at least in part on a size associated with each item bitmap.

3. The method of claim 1, wherein the step of assigning each item group comprises:

determining how many item group subsets are in the plurality of item group subsets based at least in part on the square root of a number of item groups within the set of item groups.

4. The method of claim 1, wherein the step of comparing an item bitmap further comprises:

determining that all the item bitmaps of a particular candidate combination cannot be stored simultaneously in volatile memory;

generating a cluster bitmap associated with a set of item bitmaps, wherein each of the set of item bitmaps is associated with one item in the particular candidate combination; and

comparing the cluster bitmap with at least one additional item bitmap associated with an item contained within the particular candidate combination.

5. The method of claim 1, wherein each item group is associated with item group bitmaps of equal size, and wherein each item group subset contains an equal number of item groups.

6. The method of claim 1, wherein the set of candidate combinations is a first set of candidate combinations, wherein the total frequent itemset count comprises a first total frequent itemset count that is associated with the first set of candidate combinations each having a first size, and further comprising:

generating a second total frequent itemset count that is associated with a second set of candidate combinations each having a second size.

7. A non-transitory machine-readable storage medium carrying one or more sequences of instructions, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

assigning each item group, within a set of item groups, to one of a plurality of item group subsets based at least in part on an amount of volatile memory available in a computer system, wherein each item group subset includes one or more entire item groups,

wherein each item group is associated with an item group bitmap that indicates which items, of a set of items, belong in said item group;

determining a set of candidate combinations of two or more items from the set of items;

for each candidate combination of two or more items in the set of candidate combinations, performing the step of;

in each item group subset, comparing an item bitmap associated with an item in the candidate combination with each other item bitmap associated with one or more other items in the candidate combination, to determine a partial frequent itemset count for the candidate combination in the item group subset, wherein the partial frequent itemset count comprises the total number of item groups in the item group subset that contain the candidate combination;

combining the partial frequent itemset counts of the item group subsets to derive a total frequent itemset count for the set of candidate combinations; and

storing said total frequent itemset count in a volatile or non-volatile computer-readable storage medium.

8. The machine-readable storage medium of claim 7, wherein the step of assigning each item group comprises:

determining how many item group subsets are in the plurality of item group subsets based at least in part on a size associated with each item bitmap.

9. The machine-readable storage medium of claim 7, wherein the step of assigning each item group comprises:

determining how many item group subsets are in the plurality of item group subsets based at least in part on the square root of a number of item groups within the set of item groups.

10. The machine-readable storage medium of claim 7, wherein the step of comparing an item bitmap further comprises the steps of:

determining that all the item bitmaps of a particular candidate combination cannot be stored simultaneously in volatile memory;

generating a cluster bitmap associated with a set of item bitmaps, wherein each of the set of item bitmaps is associated with one item in the particular candidate combination; and

comparing the cluster bitmap with at least one additional item bitmap associated with an item contained within the particular candidate combination.

11. The machine-readable storage medium of claim 7, wherein each item group is associated with item group bitmaps of equal size, and wherein each item group subset contains an equal number of item groups.

12. The machine-readable storage medium of claim 7, wherein the set of candidate combinations is a first set of candidate combinations, wherein the total frequent itemset count comprises a first total frequent itemset count that is associated with the first set of candidate combinations each having a first size, and wherein execution of the one or more sequences of instructions by the one or more processors causes the one or more processors to perform the step of:

generating a second total frequent itemset count that is associated with a second set of candidate combinations each having a second size.