High performance: closed frequent itemsets mining inspired by emerging computer architectures
Claudio Lucchese · ARCA (Università Ca' Foscari Venezia) · 2008
This thesis is devoted to the design of high performance algorithms for the extraction of closed frequent itemsets from transactional databases. Our interest in high performance algorithms is inspired by emerging computer architectures. We believe that high performance not only means to design fast algorithms but also to find new solutions to challenging problems. We also use our experience in constrained pattern mining to support this claim. We discuss in detail some of the issues related to frequent pattern mining algorithms: computational complexity, data size and the opportunities provided by emerging computer architectures. For each of the three aforementioned issues, we contribute a novel algorithm. DCI-Closed is a new algorithm for mining closed frequent itemsets. This is the only algorithm that can mine efficiently dense datasets without maintaining the running collection of already discovered closed itemsets. OOC-Closed is the first algorithm for mining closed frequent itemsets in secondary memory. Finally, we propose MT-Closed: the first parallel algorithm for mining closed frequent itemsets. The preset trend suggests that emerging computer architectures will become more complex over time, with tenths or hundreds of CPUs, complex cache hierarchies, and probably streaming and pipelined frameworks. With this work, we believe to provide important contributions in the direction of harnessing modern computer architectures and, at the same time, to give new insights on the mining of closed patterns.