A Contribution to the Use of Decision Diagrams for Loading and Mining Transaction Databases

Issue title: Special issue ISMIS'05

Article type: Research Article

Authors: Salleb-Aouissi, Ansaf | Vrain, Christel

Affiliations: CCLS – Center for Computational Learning Systems, Columbia University, 475 Riverside Dr., New York, NY 10115, USA. E-mail: Ansaf@ccls.columbia.edu | LIFO – Laboratoire d'Informatique Fondamentale d'Orléans, Université d'Orléans, B.P. 6759, 45067 Orléans Cedex 2 – France. E-mail: Christel.Vrain@univ-orleans.fr

Abstract: In this paper, we mainly address the problem of loading transaction datasets into main memory and estimating the density of such datasets. We propose BOOLLOADER, an algorithm dedicated to these tasks; it relies on a compressed representation of all the transactions of the dataset. For sake of efficiency, we have chosen Decision Diagrams as the main data structure to the representation of datasets into memory. We give an experimental evaluation of our algorithm on both dense and sparse datasets. Experiments have shown that BOOLLOADER is efficient for loading some dense datasets and gives a partial answer about the nature of the dataset before time-consuming pattern extraction tasks. We further investigate the use of Algebraic Decision Diagrams by studying the feasibility of current Data Mining operations, as for instance computing the support of an itemset and even mining frequent itemsets.

Keywords: Transaction dataset, boolean function, decision diagram, density, frequent itemset

Journal: Fundamenta Informaticae, vol. 78, no. 4, pp. 575-594, 2007