kDCI: on using direct count up to the third iteration.
Claudio Lucchese, Salvatore Orlando, Raffaele Perego · 2004
In Apriori-like algorithms, one of the most consuming operation during the frequent itemset mining process is the candidate search. At each iteration k the whole dataset D has to be scanned, and for each transaction t in the database, every of its subsets of length k is generated and searched within the candidates. If a candidate is matched, it means that the transaction subsumes the candidate, and therefore its support can be incremented by one. This search is very time demanding even if appropriate data structures are used to gain a logarithmic cost. In [3, 2] we introduced a direct count technique which allows constant time searches for candidates of length 2. Given the set of n frequent single items, candidates of length 2 are stored using an upper triangular matrix n× n DC2 with ( n2 ) cells, such that DC2(i, j) stored the support of the 2-itemset {ij}. As shown in [1] the direct count procedure can be extended to the third iteration using an n×n×n matrix DC3 with ( n3 ) cells, where DC3(i, j, l) is the support of the 3-itemset {ijl}. We thus introduced such technique in the last version of kDCI, which is level-wise hybrid algorithm. kDCI stores the dataset with an horizontal format to disk during the first iterations. After some iteration the dataset may become small enough (thanks to anti-monotone frequency pruning) to be stored in the main memory in a vertical format, and after that the algorithm goes on performing tid-lists intersections to retrieve itemsets supports, and searches among candidates are not needed anymore. Usually the dataset happens to be small enough at most at the fourth iteration.