Computational complexity of itemset frequency satisfiability
- 14 June 2004
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 143-154
- https://doi.org/10.1145/1055558.1055580
Abstract
Computing frequent itemsets is one of the most prominent problems in data mining. We introduce a new, related problem, called FREQSAT: given some itemset-interval pairs, does there exist a database such that for every pair the frequency of the itemset falls in the interval? It is shown in this paper that FREQSAT is not finitely axiomatizable and that it is NP-complete. We also study cases in which other characteristics of the database are given as well. These characteristics can complicate FREQSAT even more. For example, when the maximal number of duplicates of a transaction is known, FREQSAT becomes PP-hard. We describe applications of FREQSAT in frequent itemset mining algorithms and privacy in data mining.Keywords
This publication has 8 references indexed in Scilit:
- Probabilistic logic programming with conditional constraintsACM Transactions on Computational Logic, 2001
- Mining frequent patterns with counting inferenceACM SIGKDD Explorations Newsletter, 2000
- Algorithms for association rule mining — a general survey and comparisonACM SIGKDD Explorations Newsletter, 2000
- Privacy-preserving data miningPublished by Association for Computing Machinery (ACM) ,2000
- Efficiently mining long patterns from databasesPublished by Association for Computing Machinery (ACM) ,1998
- Mining association rules between sets of items in large databasesPublished by Association for Computing Machinery (ACM) ,1993
- Probabilistic satisfiabilityJournal of Complexity, 1988
- Probabilistic logicArtificial Intelligence, 1986