\input zb-basic
\input zb-ioport
\iteman{io-port 05264287}
\itemau{Calders, Toon}
\itemti{Itemset frequency satisfiability: complexity and axiomatization.}
\itemso{Theor. Comput. Sci. 394, No. 1-2, 84-111 (2008).}
\itemab
Summary: Computing frequent itemsets is one of the most prominent problems in data mining. We study the following related problem, called FREQSAT, in depth: given some itemset-interval pairs, does there exist a database such that for every pair the frequency of the itemset falls into the interval? This problem is shown to be $\bold {NP}$-complete. The problem is then further extended to include arbitrary Boolean expressions over items and conditional frequency expressions in the form of association rules. We also show that, unless $\bold {P}$ equals $\bold {NP}$, the related function problem -- find the best interval for an itemset under some frequency constraints -- cannot be approximated efficiently. Furthermore, it is shown that FREQSAT is recursively axiomatizable, but that there cannot exist an axiomatization of finite arity.
\itemrv{~}
\itemcc{}
\itemut{data mining; frequent itemset; complexity}
\itemli{doi:10.1016/j.tcs.2007.11.003}
\end