Fun at a Department Store: Data Mining Meets Switching Theory

In this paper we introduce new algebraic forms, SOP+ and DSOP+, to represent functions f : f0; 1gn ! N, based on arithmetic sums of products. These expressions are a direct generalization of the classical SOP and DSOP forms. We propose optimal and heuristic algorithms for minimal SOP+ and DSOP+ synthesis. We then show how the DSOP+ form can be exploited for Data Mining applications. In particular we propose a new compact representation for the database of transactions to be used by the LCM algorithms for mining frequent closed itemsets.