  Inducing association rules is one of the central tasks in data mining
applications. Quantitative association rules induced from databases describe
rich and hidden relationships holding within data that can prove useful for
various application purposes (e.g., market basket analysis, customer profiling,
and others). Even though such association rules are quite widely used in
practice, a thorough analysis of the computational complexity of inducing them
is missing. This paper intends to provide a contribution in this setting. To
this end, we first formally define quantitative association rule mining
problems, which entail boolean association rules as a special case, and then
analyze their computational complexities, by considering both the standard
cases, and a some special interesting case, that is, association rule induction
over databases with null values, fixed-size attribute set databases, sparse
databases, fixed threshold problems.

Computational Complexity