The complexity of mining maximal frequent itemsets and maximal frequent patterns

ABSTRACT

Mining maximal frequent itemsets is one of the most fundamental problems in data mining. In this paper we study the complexity-theoretic aspects of maximal frequent itemset mining, from the perspective of counting the number of solutions. We present the first formal proof that the problem of counting the number of distinct maximal frequent itemsets in a database of transactions, given an arbitrary support threshold, is #P-complete, thereby providing strong theoretical evidence that the problem of mining maximal frequent itemsets is NP-hard. This result is of particular interest since the associated decision problem of checking the existence of a maximal frequent itemset is in P.We also extend our complexity analysis to other similar data mining problems dealing with complex data structures, such as sequences, trees, and graphs, which have attracted intensive research interests in recent years. Normally, in these problems a partial order among frequent patterns can be defined in such a way as to preserve the downward closure property, with maximal frequent patterns being those without any successor with respect to this partial order. We investigate several variants of these mining problems in which the patterns of interest are subsequences, subtrees, or subgraphs, and show that the associated problems of counting the number of maximal frequent patterns are all either #P-complete or #P-hard.

REFERENCES

• 1: Ramesh C. Agarwal , Charu C. Aggarwal , V. V. V. Prasad, Depth first generation of long patterns, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.108-118, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347114]
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 4: T. Asai, K. Abe, S. Kawasoe, H. Arimura, H. Satamoto, and S. Arikawa. Efficient substructure discovery from large semi-structured data. In SDM, 2002.
• 5: 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
• 6: Endre Boros , Vladimir Gurvich , Leonid Khachiyan , Kazuhisa Makino, On the Complexity of Generating Maximal Frequent and Minimal Infrequent Sets, Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, p.133-141, March 14-16, 2002
• 7: Douglas Burdick , Manuel Calimlim , Johannes Gehrke, MAFIA: A Maximal Frequent Itemset Algorithm for Transactional Databases, Proceedings of the 17th International Conference on Data Engineering, p.443-452, April 02-06, 2001
• 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: Karam Gouda , Mohammed Javeed Zaki, Efficiently Mining Maximal Frequent Itemsets, Proceedings of the 2001 IEEE International Conference on Data Mining, p.163-170, November 29-December 02, 2001
• 10: Dimitrios Gunopulos , Roni Khardon , Heikki Mannila , Sanjeev Saluja , Hannu Toivonen , Ram Sewak Sharma, Discovering all most specific sentences, ACM Transactions on Database Systems (TODS), v.28 n.2, p.140-174, June 2003 [doi>10.1145/777943.777945]
• 11: Harry B. Hunt, III , Madhav V. Marathe , Venkatesh Radhakrishnan , Richard E. Stearns, The Complexity of Planar Counting Problems, SIAM Journal on Computing, v.27 n.4, p.1142-1167, Aug. 1998 [doi>10.1137/S0097539793304601]
• 12: Akihiro Inokuchi , Takashi Washio , Hiroshi Motoda, An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.13-23, September 13-16, 2000
• 13: Michihiro Kuramochi , George Karypis, Frequent Subgraph Discovery, Proceedings of the 2001 IEEE International Conference on Data Mining, p.313-320, November 29-December 02, 2001
• 14: S. O. Kuznetsov. Interpretation on graphs and complexity characteristics of a search for specific patterns. Nauchno-Tekhnicheskaya Informatsiya, Seriya 2 (Automatic Documentation and Mathematical Linguistics), 23(1):23--27, 1989.
• 15: D. -I. Lin , Z. M. Kedem, Pincer-Search: An Efficient Algorithm for Discovering the Maximum Frequent Set, IEEE Transactions on Knowledge and Data Engineering, v.14 n.3, p.553-566, May 2002 [doi>10.1109/TKDE.2002.1000342]
• 16: C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
• 17: Christos H. Papadimitriou, NP-Completeness: A Retrospective, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.2-6, July 07-11, 1997
• 18: J. S. Provan and M. O. Ball. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM Journal on Computing, 12(4):777--788, 1983.
• 19: Ganesh Ramesh , William A. Maniatty , Mohammed J. Zaki, Feasible itemset distributions in data mining: theory and application, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.284-295, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773181]
• 20: E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249--260, 1995.
• 21: Salil P. Vadhan, The Complexity of Counting in Sparse, Regular, and Planar Graphs, SIAM Journal on Computing, v.31 n.2, p.398-427, 2001 [doi>10.1137/S0097539797321602]
• 22: L. G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8:189--201, 1979.
• 23: Jianyong Wang , Jiawei Han , Jian Pei, CLOSET+: searching for the best strategies for mining frequent closed itemsets, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956779]
• 24: Yongqiao Xiao , Jenq-Foung Yao , Zhigang Li , Margaret H. Dunham, Efficient Data Mining for Maximal Frequent Subtrees, Proceedings of the Third IEEE International Conference on Data Mining, p.379, November 19-22, 2003
• 25: Mohammed J. Zaki, SPADE: An Efficient Algorithm for Mining Frequent Sequences, Machine Learning, v.42 n.1-2, p.31-60, January-February 2001 [doi>10.1023/A:1007652502315]
• 26: Mohammed J. Zaki, Efficiently mining frequent trees in a forest, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775058]
• 27: M. J. Zaki and M. Ogihara. Theoretical foundations of association rules. In DMKD, 1998.
• 28: M. J. Zaki, S. Parthasarathy, M. Ogihara, and W. Li. New algorithms for fast discovery of association rules. In KDD, 1997.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Theory

Keywords:
complexity, data mining, maximal frequent itemset, maximal frequent pattern, theory