System and method for parallel mining of association rules in databases

Claim 2

A digital multiprocessor comprising a plurality of processing systems, each processing system including a respective local database having distributed therein data from a transaction database of itemsets purchased in consumer transactions, each processing system including: means for determining the number of times a candidate itemset appears in the associated local database to establish a local count for the candidate itemset; means for using the local count to determine whether the number of times a candidate itemset appears in the transaction database exceeds a predefined minimum support value; means for entering a candidate itemset into a set of large itemsets when the number of times exceeds a predetermined minimum support value, such that the set of large itemsets can be designated as frequently occurring itemsets in transactions; means for determining, for at least some of the itemsets in the set of large itemsets the number of times selected subsets of the itemsets appear in the transaction database; means for outputting an association rule when the ratio of the number of times a selected subset appears in the transaction database to the number of times the associated itemset appears in the transaction database exceeds a predetermined minimum confidence value and thereby satisfies a minimum confidence constraint; and means for exchanging the local count with the other processing systems such that each processing system determines whether the number of times a candidate itemset appears in the transaction database exceeds the predefined minimum support value.

Claim 3

The digital multiprocessor of claim 1, wherein each processing system includes means for generating a global set G of large itemsets and partitioning the global set G among the n processing systems such that a local set G i comprising approximately G/n large itemsets is distributed to each system, and each system establishes the local count using the local set G i .

Claim 4

The digital multiprocessor of claim 1, wherein each processing system further comprises: means for generating the candidate itemsets by concatenating itemsets in the set of large itemsets in accordance with a predetermined concatenation regime, each of the processing systems being associated with a respective set of 1/n candidate large itemsets; means for receiving remote portions of the transaction database from the other processing systems; and means for establishing the local counts by alternatingly determining the number of times one or more of the 1/n candidate large itemsets appear in the respective local database and in the remote portions of the transaction database.

Claim 5

The digital multiprocessor of claim 3, wherein each processing system further comprises: means for establishing n-1 receive buffers for receiving the remote portions of the transaction database; and means for establishing the local counts by determining the number of times one or more of the 1/n candidate large itemsets appear in the remote portions of the transaction database when a receive buffer is full and otherwise determining the number of times one or more of the 1/n candidate large itemsets appear in the respective local database.

Claim 6

The digital multiprocessor of claim 4, wherein each processing system further comprises: means for entering a candidate itemset into a local set of large itemsets when the respective local count exceeds a predetermined minimum support value; means for transmitting the local set of large itemsets to the other processing systems; means for receiving from the other processing systems respective remote sets of large itemsets; and means for determining the sum of the local set and the remote sets to establish a global set of large itemsets.

Claim 7

A computer-implemented method for identifying frequently recurring itemsets in transactions which are stored in a transaction database, the transaction database being distributed among a first local database associated with a first digital processing system and at least a second local database associated with a second digital processing system, comprising: (a) determining the number of times a candidate itemset appears in the first local database to establish a local count for the candidate itemset; (b) exchanging the local counts with the at least second processing system; (c) using the local count to determine whether the number of times a candidate itemset appears in the transaction database exceeds a predefined minimum support value; (d) entering a candidate itemset into a set of large itemsets when the number of times exceeds a predetermined minimum support value; (e) for at least some of the itemsets in the set of large itemsets, determining the number of times selected subsets of the itemsets appear in the transaction database; and (f) outputting an association rule when the ratio of the number of times a selected subset appears in the transaction database to the number of times the associated itemset appears in the transaction database exceeds a predetermined minimum confidence value and thereby satisfies a minimum confidence constraint.

Claim 8

A computer-implemented method for identifying frequently recurring itemsets in transactions which are stored in a transaction database, the transaction database being distributed among a first local database associated with a first digital processing system and at least a second local database associated with a second digital processing system, comprising: (a) determining the number of times a candidate itemset appears in the first local database to establish a local count for the candidate itemset; (b) exchanging the local counts with the at least second processing system; (c) using the local count to determine whether the number of times a candidate itemset appears in the transaction database exceeds a predefined minimum support value; (d) entering a candidate itemset into a set of large itemsets when the number of times exceeds a predetermined minimum support value; (e) for at least some of the itemsets in the set of large itemsets, determining the number of times selected subsets of the itemsets appear in the transaction database; and (f) outputting an association rule when the ratio of the number of times a selected subset appears in the transaction database to the number of times the associated itemset appears in the transaction database exceeds a predetermined minimum confidence value and thereby satisfies a minimum confidence constraint.

Claim 9

The computer implemented method of claim 6, wherein the transaction database is distributed among n processing systems, further comprising: generating the candidate itemsets by concatenating itemsets in the set of large itemsets in accordance with a predetermined concatenation regime, each of the processing systems being associated with a respective set of 1/n candidate large itemsets; establishing n-1 receive buffers; receiving remote portions of the transaction database from the other processing systems in respective receive buffers; and establishing the local counts by determining the number of times one or more of the 1/n candidate large itemsets appear in the remote portions of the transaction database when a receive buffer is full, and otherwise determining the number of times one or more of the 1/n candidate large itemsets appear in the respective local database.

Claim 10

The computer implemented method of claim 6, wherein the transaction database is distributed among n processing systems, and wherein the method includes generating a global set G of large itemsets and partitioning the global set G among the n processing systems such that a local set G i comprising approximately G/n large itemsets is distributed to each system, and each system establishes the local count using the local set G i .

Claim 13

The system of claim 9, wherein each processing system includes means for entering a candidate itemset into a set of large itemsets when the number of times the candidate large itemset appears in the transaction database exceeds a predetermined minimum support value.

Claim 14

The system of claim 10, wherein the rule generator determines, for at least some of the itemsets in the set of large itemsets, the number of times selected subsets of the itemsets appear in the transaction database, and wherein the rule generator outputs an association rule when the ratio of the number of times a selected subset appears in the transaction database to the number of times the associated itemset appears in the transaction database exceeds a predetermined minimum confidence value and thereby satisfies a minimum confidence constraint.

Claim 15

The system of claim 11, wherein each processing system includes means for exchanging the local counts with the other processing systems such that each processing system determines whether the number of times a candidate itemset appears in the transaction database exceeds the predefined minimum support value.

Claim 16

The system of claim 11, wherein the transaction database is distributed among n processing systems and each processing system further comprises: means for generating the candidate itemsets by concatenating itemsets in the set of large itemsets in accordance with a predetermined concatenation regime each of the processing systems being associated with a respective set of 1/n candidate large itemsets; means for establishing n-1 receive buffers for receiving respective remote portions of the transaction database from the other processing systems; means for establishing the local counts by determining the number of times one or more of the 1/n candidate large itemsets appear in the remote portions of the transaction database when a receive buffer is full, and otherwise determining the number of times one or more of the 1/n candidate large itemsets appear in the respective local database; means for entering a candidate itemset into a local set of large itemsets when the respective local count exceeds a predetermined minimum support value; means for transmitting the local set of large itemsets to the other processing systems; means for receiving from the other processing systems respective remote sets of large itemsets; and means for determining the sum of the local set and the remote sets to establish a global set of large itemsets.

Claim 17

The system of claim 11, wherein the transaction database is distributed among n processing systems, and each processing system further comprises: means for generating a global set G of large itemsets and partitioning the global set G among the n processing systems such that a local set G i comprising approximately G/n large itemsets is distributed to each processing system, and each processing system establishes the local count using the local set G i .

Claim 18

A computer program device comprising: a computer program storage device readable by a first digital processing system; and a program means on the program storage device and including instructions executable by the digital processing system for performing method steps for identifying frequently recurring itemsets in transactions which are stored in a transaction database, the transaction database being distributed among a first local database associated with the first digital processing system and at least a second local database associated with a second digital processing system, the method steps comprising: determining the number of times a candidate itemset appears in the first local database to establish a local count for the candidate itemset; using the local count to determine whether the number of times a candidate itemset appears in the transaction database exceeds a predefined minimum support value; entering a candidate itemset into a set of large itemsets when the number of times exceeds a predetermined minimum support value, such that the set of large itemsets can be designated as frequently occurring itemsets in transactions; for at least some of the itemsets in the set of large itemsets, determining the number of times selected subsets of the itemsets appear in the transaction database; outputting an association rule when the ratio of the number of times a selected subset appears in the transaction database to the number of times the associated itemset appears in the transaction database exceeds a predetermined minimum confidence value and thereby satisfies a minimum confidence constraint; and after establishing the local count, exchanging the local counts with the at least second processing system such that each processing system determines whether the number of times a candidate itemset appears in the transaction database exceeds the predefined minimum support value.

Claim 19

A computer program device comprising: a computer program storage device readable by a first digital processing system; and a program means on the program storage device and including instructions executable by the digital processing system for performing method steps for identifying frequently recurring itemsets in transactions which are stored in a transaction database, the transaction database being distributed among a first local database associated with the first digital processing system and at least a second local database associated with a second digital processing system, the method steps comprising: determining the number of times a candidate itemset appears in the first local database to establish a local count for the candidate itemset; using the local count to determine whether the number of times a candidate itemset appears in the transaction database exceeds a predefined minimum support value; entering a candidate itemset into a set of large itemsets when the number of times exceeds a predetermined minimum support value, such that the set of large itemsets can be designated as frequently occurring itemsets in transactions; for at least some of the itemsets in the set of large itemsets, determining the number of times selected subsets of the itemsets appear in the transaction database; outputting an association rule when the ratio of the number of times a selected subset appears in the transaction database to the number of times the associated itemset appears in the transaction database exceeds a predetermined minimum confidence value and thereby satisfies a minimum confidence constraint; and after establishing the local count, exchanging the local counts with the at least second processing system such that each processing system determines whether the number of times a candidate itemset appears in the transaction database exceeds the predefined minimum support value.

Claim 20

The program storage device of claim 15, wherein the transaction database is distributed among n processing systems, and wherein the method steps include generating a global set G of large itemsets and partitioning the global set G among the n processing systems such that a local set G i comprising approximately G/n large itemsets is distributed to each system, and each system establishes the local count using the local set G i .

Claim 21

The program storage device of claim 15, wherein the transaction database is distributed among n processing systems, and the method steps further comprise: generating the candidate itemsets by concatenating itemsets in the set of large itemsets in accordance with a predetermined concatenation regime, each of the processing systems being associated with a respective set of 1/n candidate large itemsets; receiving remote portions of the transaction database from the other processing systems; and establishing the local counts by alternatingly determining the number of times one or more of the 1/n candidate large itemsets appear in the respective local database and in the remote portions of the transaction database.

Claim 22

The program storage device of claim 17, wherein the method further comprises: establishing n-1 receive buffers for receiving the remote portions of the transaction database; and establishing the local counts by determining the number of times one or more of the 1/n candidate large itemsets appear in the remote portions of the transaction database when a receive buffer is full, and otherwise determining the number of times one or more of the 1/n candidate large itemsets appear in the respective local database.

Claim 23

The program storage device of claim 18, wherein the method steps further comprise: entering a candidate itemset into a local set of large itemsets when the respective local count exceeds a predetermined minimum support value; transmitting the local set of large itemsets to the other processing systems; receiving from the other processing systems respective remote sets of large itemsets; and determining the sum of the local set and the remote sets to establish a global set of large itemsets.