A fast algorithm for frequent itemset mining using Patricia* structures

摘要: Efficient mining of frequent itemsets from a database plays an essential role in many data tasks such as association rule mining. Many algorithms use prefix-tree to represent and mine by constructing recursively conditional prefix-trees the prefix-tree. A (conditional) can be stored various structures. The construction traversal costs prefix-trees, or rather their storage structures, take large proportion whole cost for algorithms. PatriciaMine algorithm employs Patricia trie store shows good performance. In this study, we introduce efficient Patricia* structure storing is more compact contiguous than corresponding trie, thus former are less those latter. Previous prefix-tree-based adopt similar procedure, which most nodes repeatedly accessed when processed. paper presents novel procedure node accesses greatly reduced. We propose PatriciaMine* that combination with proposed procedure. Experimental show outperforms not only but also several fast algorithms, FPgrowth* dEclat, databases.