Cost-based query optimization for complex pattern mining on multiple databases

ABSTRACT

For complex data mining queries, query optimization issues arise, similar to those for the traditional database queries. However, few works have applied the cost-based query optimization, which is the key technique in optimizing traditional database queries, on complex mining queries. In this work, we develop a cost-based query optimization framework to an important collection of data mining queries, i.e. frequent pattern mining across multiple databases. Specifically, we make the following contributions: 1) We present a rich class of queries on mining frequent itemsets across multiple datasets supported by a SQL-based mechanism. 2) We present an approach to enumerate all possible query plans for the mining queries, and develop a dynamic programming approach and a branch-and-bound approach based on the enumeration algorithm to find optimal query plans with the least mining cost. 3) We introduce models to estimate the cost of individual mining operators. 4) We evaluate our query optimization techniques on both real and synthetic datasets and show significant performance improvements.

REFERENCES

• 1: 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
• 2: Stephen D. Bay , Michael J. Pazzani, Detecting Group Differences: Mining Contrast Sets, Data Mining and Knowledge Discovery, v.5 n.3, p.213-246, July 2001 [doi>10.1023/A:1011429418057]
• 3: Christan Borgelt. Apriori implementation. http://fuzzy.cs.Uni-Magdeburg.de/borgelt/Software. Version 4.08.
• 4: Cristian Bucila , Johannes Gehrke , Daniel Kifer , Walker White, DualMiner: a dual-pruning algorithm for itemsets with constraints, 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.775054]
• 5: Surajit Chaudhuri, An overview of query optimization in relational systems, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.34-43, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275492]
• 6: Surajit Chaudhuri, An overview of query optimization in relational systems, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.34-43, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275492]
• 7: Scalable Classification over SQL Databases, Proceedings of the 15th International Conference on Data Engineering, p.470, March 23-26, 1999
• 8: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 9: Viviane Crestana and Nandit Soparkar. Mining decentralized data repositories. Technical Report CSE-TR-385-99, University of Michigan Department of Electrical Engineering and Computer Science, 1999.
• 10: Guozhu Dong , Jinyan Li, Efficient mining of emerging patterns: discovering trends and differences, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.43-52, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312191]
• 11: Sašo Džeroski. Multi-relational data mining: an introduction. SIGKDD Explor. Newsl., 5(1):1--16, 2003.
• 12: Bart Goethals and Mohammed J. Zaki. Workshop Report on Workshop on Frequent Itemset Mining Implementations (FIMI). 2003.
• 13: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.1-12, May 15-18, 2000, Dallas, Texas, United States
• 14: Jia Liang Han , Ashley W. Plank, Background for association rules and cost estimate of selected mining algorithms, Proceedings of the fifth international conference on Information and knowledge management, p.73-80, November 12-16, 1996, Rockville, Maryland, United States [doi>10.1145/238355.238440]
• 15: Tomasz Imieliński , Aashu Virmani, MSQL: A Query Language for Database Mining, Data Mining and Knowledge Discovery, v.3 n.4, p.373-408, December 1999 [doi>10.1023/A:1009816913055]
• 16: Viviane Crestana Jensen and Nandit Soparkar. Algebra based optimization strategies for decentralized mining. Technical Report CSE-TR-437-00, University of Michigan, 2000.
• 17: Ruoming Jin , Gagan Agrawal, New techniques for efficiently discovering frequent patterns, Ohio State University, Columbus, OH, 2005
• 18: Ruoming Jin , Gagan Agrawal, Systematic Approach for Optimizing Complex Mining Tasks on Multiple Databases, Proceedings of the 22nd International Conference on Data Engineering, p.17, April 03-07, 2006 [doi>10.1109/ICDE.2006.154]
• 19: Ruoming Jin , Kaushik Sinha , Gagan Agrawal, Simultaneous optimization of complex mining tasks with a knowledgeable cache, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081943]
• 20: Laks V. S. Lakshmanan , Raymond Ng , Jiawei Han , Alex Pang, Optimization of constrained frequent set queries with 2-variable constraints, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.157-168, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 21: Wei Li , Ari Mozes, Computing frequent itemsets inside oracle 10G, Proceedings of the Thirtieth international conference on Very large data bases, p.1253-1256, August 31-September 03, 2004, Toronto, Canada
• 22: Rosa Meo , Giuseppe Psaila , Stefano Ceri, A New SQL-like Operator for Mining Association Rules, Proceedings of the 22th International Conference on Very Large Data Bases, p.122-133, September 03-06, 1996
• 23: Rosa Meo, Marco Botta, and Roberto Esposito. Query rewriting in itemset mining. In Proc. of the 6th International Conference On Flexible Query Answering Systems, pages 111--124, June 2004.
• 24: Raymond T. Ng , Laks V. S. Lakshmanan , Jiawei Han , Alex Pang, Exploratory mining and pruning optimizations of constrained associations rules, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.13-24, June 01-04, 1998, Seattle, Washington, United States
• 25: M. Otey , S. Parthasarathy , A. Ghoting , G. Li , S. Narravula , D. Panda, Towards NIC-based intrusion detection, 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.956847]
• 26: P. Palmerini , S. Orlando , R. Perego, Statistical properties of transactional databases, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.968009]
• 27: Sunita Sarawagi , Shiby Thomas , Rakesh Agrawal, Integrating association rule mining with relational database systems: alternatives and implications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.343-354, June 01-04, 1998, Seattle, Washington, United States
• 28: Ramakrishnan Srikant, Quoc Vu, and Rakesh Agrawal. Mining association rules with item constraints. In David Heckerman, Heikki Mannila, Daryl Pregibon, and Ramasamy Uthurusamy, editors, KDD Conference Proceedings, pages 67--73, 1997.
• 29: Dick Tsur , Jeffrey D. Ullman , Serge Abiteboul , Chris Clifton , Rajeev Motwani , Svetlozar Nestorov , Arnon Rosenthal, Query flocks: a generalization of association-rule mining, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.1-12, June 01-04, 1998, Seattle, Washington, United States
• 30: Alexander Tuzhilin , Bing Liu, Querying multiple sets of discovered rules, 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.775055]
• 31: Craig Utley. Microsoft sql server 9.0 technical articles: Introduction to sql server 2005 data mining. http://technet.microsoft.com/en-us/library/ms345131.aspx.
• 32: Geoffrey I. Webb , Shane Butler , Douglas Newlands, On detecting differences between groups, 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.956781]
• 33: Xiaoxin Yin , Jiawei Han , Jiong Yang , Philip S. Yu, CrossMine: Efficient Classification Across Multiple Database Relations, Proceedings of the 20th International Conference on Data Engineering, p.399, March 30-April 02, 2004
• 34: Y. N. Law, C. R. Luo, H. Wang, and C. Zaniol. Atlas: a turing complete extension of sql for data mining applications and streams. In Posters of the 2003 ACM SIGMOD international conference on Management of data, 2003.
• 35: Takeshi Yoshizawa , Iko Pramudiono , Masaru Kitsuregawa, SQL Based Association Rule Mining Using Commercial RDBMS (IBM DB2 UBD EEE), Proceedings of the Second International Conference on Data Warehousing and Knowledge Discovery, p.301-306, September 04-06, 2000
• 36: M. J. Zaki, S. Parthasarathy, M. Ogihara, and W. Li. New algorithms for fast discovery of association rules. In 3rd Intl. Conf. on Knowledge Discovery and Data Mining., August 1997.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

          Nouns: SQL
      H.2.4 Systems
          Subjects: Query processing

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming