Class relevant pattern mining in output-polynomial time

The set of so-called relevant patterns is a subset of all itemsets particularly suited for pattern-based classifica- Tion tasks. So far, no efficient algorithm has been de- veloped for computing the set of relevant patterns: All existing solutions have a worst-case complexity which is exponential in the size of the input and output. In this paper, we investigate new properties of the relevant pat- Terns and develop, thereupon, the first algorithm whose runtime is polynomial in the size of the input and out- put. As we show in the experimental section, this result is not only of theoretical interest but also of practical importance, often reducing the search space by orders of magnitude.