Efficient Vertical Mining of Minimal Rare Itemsets
László Szathmáry, Petko Valtchev, Amedeo Napoli, Robert P. Godin · 2012
Abstract. Rareitemsetsareimportantsortofpatternsthathaveawide range of practical applications, in particular, in analysis of biomedical data. Although mining rare patterns poses specific algorithmic problems, it is yet insufficiently studied. In a previous work, we proposed a levelwise approach for rare itemset mining that traverses the search space bottomup and proceeds in two steps: (1) moving across the frequent zone until the minimal rare itemsets are reached and (2) listing all rare itemsets. As the efficiency of the frequent zone traversal is crucial for the overall performance of the rare miner, we are looking for ways to speed it up. Here,weexaminethebenefitsofdepth-firstmethodsforthattaskassuch methods are known to outperform the levelwise ones in many practical cases. The new method relies on a set of structural results that helps save a certain amount of computation and eventually ensures it outperforms the current levelwise procedure. 1