Computational complexity of itemset frequency satisfiability

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.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Privacy-preserving data mining, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.439-450, May 15-18, 2000, Dallas, Texas, United States
• 3: Yves Bastide , Rafik Taouil , Nicolas Pasquier , Gerd Stumme , Lotfi Lakhal, Mining frequent patterns with counting inference, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.66-75, Dec. 2000 [doi>10.1145/380995.381017]
• 4: Roberto J. Bayardo, Jr., Efficiently mining long patterns from databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.85-93, June 01-04, 1998, Seattle, Washington, United States
• 5: T. Calders, Deducing bounds on the support of itemsets. In Database Support for Data Mining Applications, LNCS 2682, Springer, to appear 2004.
• 6: Toon Calders , Bart Goethals, Mining All Non-derivable Frequent Itemsets, Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, p.74-85, August 19-23, 2002
• 7: V. Chvátal. Recognizing intersection patterns. Annals of Discrete Mathematics - Combinatorics 79, 8(I):249--251, 1980.
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: George Georgakopoulos , Dimitris Kavvadias , Christos H. Papadimitriou, Probabilistic Satisfiability, Journal of Complexity, v.4 n.1, p.1-11, March 1988 [doi>10.1016/0885-064X(88)90006-4]
• 10: Jochen Hipp , Ulrich Güntzer , Gholamreza Nakhaeizadeh, Algorithms for association rule mining — a general survey and comparison, ACM SIGKDD Explorations Newsletter, v.2 n.1, p.58-64, June, 2000 [doi>10.1145/360402.360421]
• 11: Thomas Lukasiewicz, Probabilistic logic programming with conditional constraints, ACM Transactions on Computational Logic (TOCL), v.2 n.3, p.289-339, July 2001 [doi>10.1145/377978.377983]
• 12: H. Mannila and H. Toivonen. Multiple uses of frequent sets and condensed representations. In Proc. KDD Int. Conf. Knowledge Discovery in Databases, 1996.
• 13: T. Mielikäinen. On inverse frequent set mining. In Workshop on Privacy Preserving Data Mining, 2003.
• 14: Nils J. Nilsson, Probabilistic logic, Artificial Intelligence, v.28 n.1, p.71-88, Feb. 1986 [doi>10.1016/0004-3702(86)90031-7]
• 15: C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.