Computational complexity of queries based on itemsets

DOI10.1016/J.IPL.2006.02.003MaRDI QIDQ844194zbMATH OpenOpenAlexFDO

Authors Nikolaj Tatti

Publication date 18 January 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.00633

zbMATH Keywords

computational complexitydata miningitemset

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Database theory (68P15)

Abstract: We investigate determining the exact bounds of the frequencies of conjunctions based on frequent sets. Our scenario is an important special case of some general probabilistic logic problems that are known to be intractable. We show that despite the limitations our problems are also intractable, namely, we show that checking whether the maximal consistent frequency of a query is larger than a given threshold is NP-complete and that evaluating the Maximum Entropy estimate of a query is PP-hard. We also prove that checking consistency is NP-complete.

Recommendations

• Itemset frequency satisfiability: complexity and axiomatization
• The complexity of satisfying constraints on databases of transactions
• Constraint-Based Mining and Inductive Databases
• The dichotomy of probabilistic inference for unions of conjunctive queries
• The complexity of evaluating relational queries

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• scientific article; zbMATH DE number 3241743 (Why is no real title available?)
• Axiomatization of frequent itemsets
• Best Possible Inequalities for the Probability of a Logical Function of Events
• Database Support for Data Mining Applications
• I-divergence geometry of probability distributions and minimization problems
• Itemset frequency satisfiability: complexity and axiomatization
• Phase transitions of PP-complete satisfiability problems. (Abstract)
• Probabilistic logic programming with conditional constraints
• Probabilistic satisfiability
• The computational complexity of probabilistic inference using Bayesian belief networks

Cited in

(10)

• Computing supports of conjunctive queries on relational tables with functional dependencies
• Itemset frequency satisfiability: complexity and axiomatization
• Comparing apples and oranges: measuring differences between exploratory data mining results
• Approximate Query Complexity
• Computational properties of metaquerying problems
• The complexity of satisfying constraints on databases of transactions
• scientific article; zbMATH DE number 1114037 (Why is no real title available?)
• On the complexity of package recommendation problems
• Constraint-Based Mining and Inductive Databases
• What to expect from a set of itemsets?

This page was built for publication: Computational complexity of queries based on itemsets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q844194)