Efficient data-structures and parallel algorithms for association rules discovery

摘要

Discovering patterns or frequent episodes in transactions is an important problem in data mining for the purpose of infering deductive rules from them. Because of the huge size of the data to deal with, parallel algorithms have been designed for reducing both the execution time and the number of repeated passes over the database in order to reduce, as much as possible, I/O overheads. In this paper, we introduce approaches for the implementation of two basic algorithms for association rules discovery (namely Apriori and Eclat). Our approaches combine efficient data structures to code different key information (line indexes, candidates) and we exhibit how to introduce parallelism for processing such data-structures.