On the Complexity of Mining Association Rules.
Fabrizio Angiulli, Giovambattista Ianni, Luigi Palopoli · 2001
Fabrizio Angiulli 1 , Giovambattista Ianni 2 , and Luigi Palopoli 3 1 ISI-CNR c/o Universita della Calabria, DEIS, Via P. Bucci 41C, Rende, Italy [email protected] 2 Universita della Calabria, DEIS, Via P. Bucci 41C, Rende, Italy [email protected] 3 Universita di Reggio Calabria, DIMET, Loc. Feo di Vito, Reggio Calabria, Italy [email protected] Abstract. In this paper we describe our ongoing research towards establishing the complexity of mining association rules from relational databases. We consider both quantitative, categorical and boolean association rules and various forms of quality indexes, including confidence, support, gain, laplace. The presented results show that all these problems are, generally, computationally hard to solve, even if we are able to single out some interesting tractable special cases.