Closed itemset mining using difference update

Abstract

Embodiments are directed to, for a database comprising a set of transactions, with each transaction including an itemset comprising one or more individual items, obtaining a set of all closed frequent itemsets by checking frequencies of transaction sets, wherein a given itemset, I, is frequent where at least some threshold number (μ) of transactions contain I, and wherein the given itemset I is closed wherein it is impossible to add any item to I without changing the frequency thereof.

1 . A method comprising:
 checking, by a computing device, frequencies of itemsets within transactions; and   obtaining, by the computing device, a set of all closed frequent itemsets based on the checking the frequencies of the itemsets within the transactions, wherein a frequency of an itemset among the itemsets, is based on a number of the transactions that include the itemset, the itemset is frequent where at least a threshold number of the transactions includes the itemset, and the itemset is closed when it is impossible to add any item to the itemset without changing the frequency thereof, the obtaining including comparing the frequencies of pairs of the itemsets based on corresponding hash values.   
     
     
         2 . The method of  claim 1 , further comprising:
 checking if a candidate itemset appears in a number of the transactions greater than the threshold number.   
     
     
         3 . The method of  claim 2 , further comprising:
 disregarding the candidate itemset for inclusion in the set of all closed frequent itemsets when the checking indicates that the candidate itemset appears in fewer than the threshold number of the transactions.   
     
     
         4 . The method of  claim 3 , further comprising:
 disregarding a second candidate itemset that is a descendant of the candidate itemset for inclusion in the set of all closed frequent itemsets when the checking indicates that the candidate itemset appears in fewer than the threshold number of the transactions.   
     
     
         5 . The method of  claim 2 , further comprising:
 checking if the candidate itemset is closed responsive to determining that the candidate itemset appears in a number of transactions greater than the threshold number.   
     
     
         6 . The method of  claim 5 , further comprising:
 checking if the candidate itemset is closed by checking if the candidate itemset has a hash value that is present in a hash table.   
     
     
         7 . The method of  claim 6 , further comprising:
 determining that the hash value is not present in the hash table, and   responsive to determining that the hash value is not present in the hash table, adding the hash value to the hash table and the candidate itemset to a linked list of itemsets corresponding to the closed frequent itemsets.   
     
     
         8 . The method of  claim 6 , further comprising:
 determining that the hash value is present in the hash table,   responsive to determining that the hash value is present in the hash table, determining whether the candidate itemset can be merged with an itemset included in a linked list corresponding to the closed frequent itemsets, and   responsive to determining that the candidate itemset can be merged with an itemset included in the linked list, merging the candidate itemset with the itemset included in the linked list to obtain a merged itemset.   
     
     
         9 . The method of  claim 8 , further comprising:
 removing the itemset included in the linked list from the linked list, and   adding the merged itemset to the linked list.   
     
     
         10 . The method of  claim 9 , further comprising:
 adding a hash value corresponding to the merged itemset to the hash table; and   linking the hash value corresponding to the merged itemset to the merged itemset in the linked list.