Expressing frequent itemset counting operations

• US 8,655,911 B2
• Filed: 08/18/2003
• Issued: 02/18/2014
• 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): LIN, SHEW FEN
• Application Number:
  US10/643,628
• Publication Number:
  US 20050044094A1
• Time in Patent Office: 3,837 Days
• Field of Search: 707/5, 707/6, 707/101, 707/776, 707/730, 707/754
• US Class Current: 707/776
• CPC Class Codes: G06F 16/2448 for particular applications; for extensibility, e.g. user defined types
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries

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:

receiving a database statement that specifies (1) a function name of a table function that identifies which itemsets occur together most frequently in a particular item group population and (2) a plurality of input parameters that are input parameters to the table function;

wherein the plurality of input parameters includes

a parameter for a support threshold that indicates a ratio,

a parameter for a cursor that indicates the particular item group population, and

a parameter for a minimum length that indicates a minimum length for frequent itemsets that are identified by the table function;

wherein the ratio indicates what percentage of transactions, of a particular set of transactions, must contain a given itemset for the given itemset to qualify as a frequent itemset;

in response to receiving the database statement, calling the table function and passing, as input to the table function, values for each of the plurality of input parameters;

wherein results returned by the table function, in response to calling the table function, identify which itemsets occur together most frequently in the particular item group population, excluding all itemsets that (a) include fewer items than the minimum length and (b) do not satisfy the support threshold;

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

2. The method of claim 1, wherein:

the table function is configured to accept input data that is in a particular format;

the particular format of the input data is one of a single-item-per-row format or a multiple-items-per-row format.

3. The method of claim 1, further comprising, in response to calling the table function, transforming rows from a single-item-per-row format into a multiple-items-per-row format.

4. The method of claim 1, wherein the results of calling the table function indicate a total transaction count.

5. The method of claim 1, wherein the results of calling the table function indicate a number of transactions in which a particular frequent itemset occurs.

6. The method of claim 1, wherein the plurality of input parameters includes a maximum length, wherein the results of calling the table function exclude all itemsets that include more items than the maximum length.

7. The method of claim 1, wherein the plurality of input parameters includes a set of one or more included items, wherein the results of calling the table function exclude all itemsets that do not include at least one item in the set of one or more included items.

8. The method of claim 1, wherein the plurality of input parameters includes a set of one or more excluded items, wherein the results of calling the table function exclude all itemsets that include any item in the set of one or more excluded items.

9. The method of claim 1, further comprising, in response to calling the table function:

during a first phase of a multiple phase elimination process;

identifying a first set of itemset candidates and determining whether each itemset in the first set of itemset candidates satisfies one or more frequent itemset criteria associated with the table function;

identifying a second set of itemset candidates, each of which satisfies the one or more frequent itemset criteria associated with the table function, wherein the second set of itemset candidates is a strict subset of the first set of itemset candidates;

during a second phase of the multiple phase elimination process;

identifying the second set of itemset candidates and determining whether each itemset in the second set of itemset candidates satisfies one or more second frequent itemset criteria associated with the table function.

10. The method of claim 1, further comprising, in response to calling the table function, determining whether a particular itemset candidate satisfies the support threshold, wherein determining whether the particular itemset candidate satisfies the support threshold comprises:

creating a single-item bitmap for each possible item of a plurality of possible items;

performing a Boolean AND operation between the single-item bitmaps to create a combination bitmap that represents a candidate combination;

determining, based on the combination bitmap, how many item groups include the candidate combination;

determining, based on a number of item groups that include the candidate combination, whether the candidate combination satisfies the support threshold.

11. The method of claim 1, further comprising:

creating a plurality of cluster bitmaps, wherein each cluster bitmap is associated with a base bitmap and a set of combinations, wherein the set of combinations have the base bitmap in common.

12. The method of claim 1, further comprising, in response to calling the table function:

generating a prefix tree based on a set of candidate combinations for a particular phase of multiple phase counting technique;

wherein the prefix tree is a number of levels deep, wherein the number of levels deep is equal to a number of items in each candidate combination of the set of candidate combinations, wherein each node in the prefix tree is associated with an item;

wherein each leaf node in the prefix tree represents a candidate combination of the set of candidate combinations;

for each item group of multiple item groups in the particular item group populations, traversing the prefix tree to determine a number of occurrences, in the multiple item groups, of each candidate combination in the set of candidate combinations.

13. The method of claim 1, further comprising, after calling the table function:

based on one or more criteria, selecting a candidate itemset counting technique from among a plurality of candidate itemset counting techniques.

14. The method of claim 1, further comprising, after calling the table function and before the results are returned:

during a first phase of the frequent itemset operation, selecting a first candidate itemset counting technique from among a plurality of candidate itemset counting techniques;

during a second phase of the frequent itemset operation, selecting a second candidate itemset counting technique from among the plurality of candidate itemset counting techniques, wherein the second candidate itemset counting technique is different than the first candidate itemset counting technique.

15. One or more non-transitory storage media storing instructions for performing a frequent itemset operation, wherein the instructions, when executed by one or more processors cause:

receiving a database statement that specifies (1) a function name of a table function that identifies which itemsets occur together most frequently in a particular item group population and (2) a plurality of input parameters that are input parameters to the table function;

wherein the plurality of input parameters includes

a parameter for a support threshold that indicates a ratio,

a parameter for a cursor that indicates the particular item group population, and

a parameter for a minimum length that indicates a minimum length for frequent itemsets that are identified by the table function;

wherein the ratio indicates what percentage of transactions, of a particular set of transactions, must contain a given itemset for the given itemset to qualify as a frequent itemset;

in response to receiving the database statement, calling the table function and passing, as input to the table function, values for each of the plurality of input parameters;

wherein results returned by the table function, in response to calling the table function, identify which itemsets occur together most frequently in the particular item group population, excluding all itemsets that (a) include fewer items than the minimum length and (b) do not satisfy the support threshold.

16. The one or more storage media of claim 15, wherein:

the table function is configured to accept input data that is in a particular format;

the particular format of the input data is one of a single-item-per-row format or a multiple-items-per-row format.

17. The one or more storage media of claim 15, wherein the instructions, when executed by the one or more processors, further cause, in response to calling the table function, transforming rows from a single-item-per-row format into a multiple-items-per-row format.

18. The one or more storage media of claim 15, wherein the results of calling the table function indicate a total transaction count.

19. The one or more storage media of claim 15, wherein the results of calling the table function indicate a number of transactions in which a particular frequent itemset occurs.

20. The one or more storage media of claim 15, wherein the plurality of input parameters includes a maximum length, wherein the results of calling the table function exclude all itemsets that include more items than the maximum length.

21. The one or more storage media of claim 15, wherein the plurality of input parameters includes a set of one or more included items, wherein the results of calling the table function exclude all itemsets that do not include at least one item in the set of one or more included items.

22. The one or more storage media of claim 15, wherein the plurality of input parameters includes a set of one or more excluded items, wherein the results of calling the table function exclude all itemsets that include any item in the set of one or more excluded items.

23. The one or more storage media of claim 15, wherein the instructions, when executed by the one or more processors, further cause, in response to calling the table function:

during a first phase of a multiple phase elimination process;

identifying a first set of itemset candidates and determining whether each itemset in the first set of itemset candidates satisfies one or more frequent itemset criteria associated with the table function;

identifying a second set of itemset candidates, each of which satisfies the one or more frequent itemset criteria associated with the table function, wherein the second set of itemset candidates is a strict subset of the first set of itemset candidates;

during a second phase of the multiple phase elimination process;

identifying the second set of itemset candidates and determining whether each itemset in the second set of itemset candidates satisfies one or more second frequent itemset criteria associated with the table function.

24. The one or more storage media of claim 15, wherein the instructions, when executed by the one or more processors, further cause, in response to calling the table function, determining whether a particular itemset candidate satisfies the support threshold, wherein determining whether the particular itemset candidate satisfies the support threshold comprises:

creating a single-item bitmap for each possible item of a plurality of possible items;

performing a Boolean AND operation between the single-item bitmaps to create a combination bitmap that represents a candidate combination;

determining, based on a combination bitmap, how many item groups include the candidate combination;

determining, based on a number of item groups that include the candidate combination, whether the candidate combination satisfies the support threshold.

25. The one or more storage media of claim 15, wherein the instructions, when executed by the one or more processors, further cause:

creating a plurality of cluster bitmaps, wherein each cluster bitmap is associated with a base bitmap and a set of combinations, wherein the set of combinations have the base bitmap in common.

26. The one or more storage media of claim 15, wherein the instructions, when executed by the one or more processors, further cause, in response to calling the table function:

generating a prefix tree based on a set of candidate combinations for a particular phase of multiple phase counting technique;

wherein the prefix tree is a number of levels deep, wherein the number of levels deep is equal to a number of items in each candidate combination of the set of candidate combinations, wherein each node in the prefix tree is associated with an item;

wherein each leaf node in the prefix tree represents a candidate combination of the set of candidate combinations;

for each item group of multiple item groups in the particular item group populations, traversing the prefix tree to determine a number of occurrences, in the multiple item groups, of each candidate combination in the set of candidate combinations.

27. The one or more storage media of claim 15, wherein the instructions, when executed by the one or more processors, further cause, after calling the table function:

based on one or more criteria, selecting a candidate itemset counting technique from among a plurality of candidate itemset counting techniques.

28. The one or more storage media of claim 15, wherein the instructions, when executed by the one or more processors, further cause, after calling the table function and before the results are returned:

during a first phase of the frequent itemset operation, selecting a first candidate itemset counting technique from among a plurality of candidate itemset counting techniques;

during a second phase of the frequent itemset operation, selecting a second candidate itemset counting technique from among the plurality of candidate itemset counting techniques, wherein the second candidate itemset counting technique is different than the first candidate itemset counting technique.