Direct Count & Intersect

Orlando S., Perego R., Palmerini P., Silvestri S.

Pattern Mining  DCI  Direct Count  Intersect 

DCI is a hybrid, multi-strategy algorithm for solving the Frequent Set Counting problem. Similarly to Apriori, DCI employs a level-wise technique to identify frequent sets. At iteration k, candidate k-itemsets are determined, and their support discovered by counting itemset occurrences within the transaction database. DCI uses an innovative method for storing candidate itemsets and counting their support, and by exploiting effective pruning techniques which reduce the size of the dataset as execution progresses. Moreover, as soon as the pruned dataset becomes small enough to fit into the main memory, DCI builds on the fly a vertical transaction database, and starts using an efficient intersection-based technique to determine the support of larger itemsets. The most important innovation in DCI resides on a novel counting inference strategy, based on a previously known result by Basted et al. which introduced the concept of key-pattern.