System and method for quickly mining association rules in databases

Claim 3

The method of claim 1, wherein the method iteratively repeats selected steps, and each itemset in the next set of candidate large itemsets is compared either to the itemsets in the database or to a previous set of candidate large itemsets.

Claim 4

The method of claim 1, wherein each transaction is characterized by a unique transaction identifier, and candidate large itemsets in the next set of candidate large itemsets are associated with one of the transaction identifiers.

Claim 5

The method of claim 1, wherein determining and outputting are iteratively repeated, and in a first iteration the selected subsets of the itemsets in the next forward set of large itemsets each contain one item.

Claim 6

The method of claim 4, wherein in a first iteration the selected subsets each contain one item, and in a second iteration the selected subsets are supersets only of those subsets found in the first iteration to have satisfied the minimum confidence constraint.

Claim 7

A computer program product for use with a computer system, a central processing unit and means coupled to the central processing unit for storing a database to identify association rules in itemsets in transactions which are stored in the database, each itemset characterized by one or more items, comprising: a data storage device including a computer usable medium having computer readable program means for identifying association rules in itemsets in transactions which are stored in a database, the computer usable code means having: computer readable code means for entering an itemset into a set of large itemsets when the number of times the itemset is present in the database exceeds a predefined minimum support value; computer readable code means for concatenating itemsets in the set of large itemsets in accordance with a predetermined concatenation regime to generate a next set of candidate large itemsets; computer readable code means for comparing each itemset in the next set of candidate large itemsets to the itemsets in the database to determine the number of times the candidate large itemset is present in the database; computer readable code means for entering a candidate large itemset into a next forward set of large itemsets only when the number of times the candidate large itemset is present in the database is greater than the minimum support value; computer readable code means for, at least for some of the itemsets in the next forward set of large itemsets, determining the number of times selected subsets of the itemsets appear in the database; and computer readable code means for outputting an association rule when the ratio of the number of times a selected subset having a plurality of items appears in the database to the number of times the associated itemset appears in the database exceeds a predetermined minimum confidence value and thereby satisfies a minimum confidence constraint.

Claim 8

A computer program product for use with a computer system, a central processing unit and means coupled to the central processing unit for storing a database to identify association rules in itemsets in transactions which are stored in the database, each itemset characterized by one or more items, comprising: a data storage device including a computer usable medium having computer readable program means for identifying association rules in itemsets in transactions which are stored in a database, the computer usable code means having: computer readable code means for entering an itemset into a set of large itemsets when the number of times the itemset is present in the database exceeds a predefined minimum support value; computer readable code means for concatenating itemsets in the set of large itemsets in accordance with a predetermined concatenation regime to generate a next set of candidate large itemsets; computer readable code means for comparing each itemset in the next set of candidate large itemsets to the itemsets in the database to determine the number of times the candidate large itemset is present in the database; computer readable code means for entering a candidate large itemset into a next forward set of large itemsets only when the number of times the candidate large itemset is present in the database is greater than the minimum support value; computer readable code means for, at least for some of the itemsets in the next forward set of large itemsets, determining the number of times selected subsets of the itemsets appear in the database; and computer readable code means for outputting an association rule when the ratio of the number of times a selected subset having a plurality of items appears in the database to the number of times the associated itemset appears in the database exceeds a predetermined minimum confidence value and thereby satisfies a minimum confidence constraint.

Claim 9

The computer program product of claim 6, wherein the computer usable code means includes computer readable code means for iteratively repeats selected functions, and each itemset in the next set of candidate large itemsets is compared by the computer readable code means for comparing either to the itemsets in the database or to a previous set of candidate large itemsets.

Claim 10

The computer program product of claim 6, wherein each transaction is characterized by a unique transaction identifier, and candidate large itemsets in the next set of candidate large itemsets are associated with one of the transaction identifiers.

Claim 11

The computer program product of claim 6, wherein the computer code means for determining and outputting iteratively operate, and in a first iteration the selected subsets of the itemsets in the next forward set of large itemsets each contain one item.

Claim 12

The computer program product of claim 9, wherein in a first iteration the selected subsets each contain one item, and in a second iteration the selected subsets are supersets only of those subsets found in the first iteration to have satisfied the minimum confidence constraint.

Claim 15

The method of claim 11, wherein identifying large itemsets comprises: constructing a multi-level hashing data structure containing the large itemsets and entering an itemset into a set of large itemsets when the number of times the itemset is present in the database exceeds a predefined minimum support value; concatenating itemsets in the set of large itemsets in accordance with a predetermined concatenation regime to generate a next set of candidate large itemsets; comparing each itemset in the next set of candidate large itemsets to the itemsets in the database to determine the number of times the candidate large itemset is present in the database; and entering a candidate large itemset into a next forward set of large itemsets only when the number of times the candidate large itemset is present in the database is greater than the minimum support value.

Claim 16

The method of claim 12, wherein discovering association rules includes: for at least some of the itemsets in the next forward set of large itemsets, determining the number of times selected subsets of the itemsets appear in the database.

Claim 17

The method of claim 13, wherein the method iteratively repeats selected steps, and comparing includes comparing each itemset in the next set of candidate large itemsets either to the itemsets in the database or to a previous set of candidate large itemsets.

Claim 18

The method of claim 13, wherein each transaction is characterized by a unique transaction identifier, and candidate large itemsets in the next set of candidate large itemsets are associated with one of the transaction identifiers.

Claim 19

The method of claim 13, wherein the discovering step is iteratively repeated, and in a first iteration the selected subsets of the itemsets in the next forward set of large itemsets each contain one item.

Claim 20

The method of claim 16, wherein in a first iteration the selected subsets each contain one item, and in a second iteration the selected subsets are supersets only of those subsets found in the first iteration to have the user-defined confidence.

Claim 21

A database mining system for discovering association rules in itemsets stored in a database, each itemset including a plurality of items, the system comprising: means for entering an itemset into a set of large itemsets when the number of times the itemset is present in the database exceeds a predefined minimum support value; means for concatenating itemsets in the set of large itemsets in accordance with a predetermined concatenation regime to generate a next set of candidate large itemsets; means for comparing each itemset in the next set of candidate large itemsets to the itemsets in the database to determine the number of times the candidate large itemset is present in the database; means for entering a candidate large itemset into a next forward set of large itemsets when the number of times the candidate large itemset is present in the database is greater than the minimum support value; means for entering at least some of the itemsets in the next forward set of large itemsets, determining the number of times selected subsets of the itemsets appear in the database; and means for outputting an association rule when the ratio of the number of times a selected subset having a plurality of items appears in the database to the number of times the associated itemset appears in the database exceeds a predetermined minimum confidence value and thereby satisfies a minimum confidence constraint.

Claim 22

A database mining system for discovering association rules in itemsets stored in a database, each itemset including a plurality of items, the system comprising: means for entering an itemset into a set of large itemsets when the number of times the itemset is present in the database exceeds a predefined minimum support value; means for concatenating itemsets in the set of large itemsets in accordance with a predetermined concatenation regime to generate a next set of candidate large itemsets; means for comparing each itemset in the next set of candidate large itemsets to the itemsets in the database to determine the number of times the candidate large itemset is present in the database; means for entering a candidate large itemset into a next forward set of large itemsets when the number of times the candidate large itemset is present in the database is greater than the minimum support value; means for entering at least some of the itemsets in the next forward set of large itemsets, determining the number of times selected subsets of the itemsets appear in the database; and means for outputting an association rule when the ratio of the number of times a selected subset having a plurality of items appears in the database to the number of times the associated itemset appears in the database exceeds a predetermined minimum confidence value and thereby satisfies a minimum confidence constraint.

Claim 23

A computer-based system for discovering purchasing tendencies of consumers by identifying association rules between itemsets of transactions and subsets of the itemsets, the subsets including one or more items, comprising: a multi-level hash tree data structure accessible by the computer for electronically storing the itemsets; a large itemset generator accessing the database for determining a first number of times an itemset appears in the database and for designating the itemset as a large itemset when the first number of times exceeds a minimum support value; and an association rule discoverer accessing the large itemset generator for determining a second number of times at least one subset having a plurality of items of an itemset appears in the database, the association rule discoverer outputting an association rule representative of purchasing tendencies of consumers when the ratio of the first number of times to the second number of times equals a predetermined minimum confidence value.

Claim 24

A computer-based system for discovering purchasing tendencies of consumers by identifying association rules between itemsets of transactions and subsets of the itemsets, the subsets including one or more items, comprising: a multi-level hash tree data structure accessible by the computer for electronically storing the itemsets; a large itemset generator accessing the database for determining a first number of times an itemset appears in the database and for designating the itemset as a large itemset when the first number of times exceeds a minimum support value; and an association rule discoverer accessing the large itemset generator for determining a second number of times at least one subset having a plurality of items of an itemset appears in the database, the association rule discoverer outputting an association rule representative of purchasing tendencies of consumers when the ratio of the first number of times to the second number of times equals a predetermined minimum confidence value.