Processing frequent itemset discovery queries by division and set containment join operators

ABSTRACT

SQL-based data mining algorithms are rarely used in practice today. Most performance experiments have shown that SQL-based approaches are inferior to main-memory algorithms. Nevertheless, database vendors try to integrate analysis functionalities to some extent into their query execution and optimization components in order to narrow the gap between data and processing. Such a database support is particularly important when data mining applicatons need to analyze very large datasets or when they need access current data, not a possibly outdated copy of it.We investigate approaches based on SQL for the problem of finding frequent itemsets in a transaction table, including an algorithm that we recently proposed, called Quiver, which employs universal and existential quantifications. This approach employs a table schema for itemsets that is similar to the commonly used vertical layout for transactions: each item of an itemset is stored in a separate row. We argue that expressing the frequent itemset discovery problem using quantifications offers interesting opportunities to process such queries using set containment join or set containment division operators, which are not yet available in commercial database systems. Initial performance experiments reveal that Quiver cannot be processed efficiently by commercial DBMS. However, our experiments with query execution plans that use operators realizing set containment tests suggest that an efficient processing of Quiver is possible.

REFERENCES

• 1: Rakesh Agrawal , Amit Somani , Yirong Xu, Storage and Querying of E-Commerce Data, Proceedings of the 27th International Conference on Very Large Data Bases, p.149-158, September 11-14, 2001
• 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: Jochen Van den Bercken , Björn Blohsfeld , Jens-Peter Dittrich , Jürgen Krämer , Tobias Schäfer , Martin Schneider , Bernhard Seeger, XXL - A Library Approach to Supporting Efficient Implementations of Advanced Database Queries, Proceedings of the 27th International Conference on Very Large Data Bases, p.39-48, September 11-14, 2001
• 4: J. Chen and D. DeWitt. Dynamic Re-grouping of Continuous Queries. In Proceedings VLDB, Hong Kong, China, pages 430--441, August 2002.
• 5: M. Gimbel, M. Klein, and P. Lockemann. Interactivity, Scalability and Resource Control for Efficient KDD Support in DBMS. In Proceedings DTDM, Prague, Czech Republic, pages 37--50, March 2002.
• 6: Goetz Graefe , Richard L. Cole, Fast algorithms for universal quantification in large databases, ACM Transactions on Database Systems (TODS), v.20 n.2, p.187-236, June 1995 [doi>10.1145/210197.210202]
• 7: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 8: S. Helmer. Performance Enhancements for Advanced Database Management Systems. PhD thesis, University of Mannheim, Germany, December 2000.
• 9: S. Helmer and G. Moerkotte. Compiling Away Set Containment and Intersection Joins. Technical Report, University of Mannheim, Germany.
• 10: Maurice Houtsma , Arun Swami, Set-oriented data mining in relational databases, Data & Knowledge Engineering, v.17 n.3, p.245-262, Dec. 1995 [doi>10.1016/0169-023X(95)00024-M ]
• 11: Nikos Mamoulis, Efficient processing of joins on set-valued attributes, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872778]
• 12: William Maniatty , Mohammed Javeed Zaki, A Requirements Analysis for Parallel KDD Systems, Proceedings of the 15 IPDPS 2000 Workshops on Parallel and Distributed Processing, p.358-365, May 01-05, 2000
• 13: H. Mannila, H. Toivonen, and A. I. Verkamo. Efficient Algorithms for Discovering Association Rules. In AAAI Workshop on Knowledge and Discovery in Databases, Seattle, Washington, USA, pages 181--192, July 1994.
• 14: Sergey Melnik , Hector Garcia-Molina, Divide-and-Conquer Algorithm for Computing Set Containment Joins, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.427-444, March 25-27, 2002
• 15: Sergey Melnik , Hector Garcia-Molina, Adaptive algorithms for set containment joins, ACM Transactions on Database Systems (TODS), v.28 n.1, p.56-99, March 2003 [doi>10.1145/762471.762474]
• 16: Iko Pramudiono , Takahiko Shintani , Takayuki Tamura , Masaru Kitsuregawa, Parallel SQL Based Association Rule Mining on Large Scale PC Cluster: Performance Comparison with Directly Coded C Implementation, Proceedings of the Third Pacific-Asia Conference on Methodologies for Knowledge Discovery and Data Mining, p.94-98, April 26-28, 1999
• 17: Karthikeyan Ramasamy , Jeffrey F. Naughton, Efficient storage and query processing of set-valued attributes, 2001
• 18: Karthikeyan Ramasamy , Jignesh M. Patel , Jeffrey F. Naughton , Raghav Kaushik, Set Containment Joins: The Good, The Bad and The Ugly, Proceedings of the 26th International Conference on Very Large Data Bases, p.351-362, September 10-14, 2000
• 19: R. Rantzau. Frequent Itemset Discovery with SQL Using Universal Quantification. In P. Lanzi and R. Meo, editors, Database Support for Data Mining Applications, volume 2682 of LNCS. Springer, 2003. To appear.
• 20: Ralf Rantzau , Leonard D. Shapiro , Bernhard Mitschang , Quan Wang, Algorithms and applications for universal quantification in relational databases, Information Systems, v.28 n.1-2, p.3-32, 01 March 2003 [doi>10.1016/S0306-4379(02)00047-9 ]
• 21: 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
• 22: S. Sarawagi, S. Thomas, and R. Agrawal. Integrating Association Rule Mining with Relational Database Systems: Alternatives and Implications. Research Report RJ 10107 (91923), IBM Almaden Research Center, San Jose, California, USA, March 1998.
• 23: Shiby Thomas , Sharma Chakravarthy, Performance Evaluation and Optimization of Join Queries for Association Rule Mining, Proceedings of the First International Conference on Data Warehousing and Knowledge Discovery, p.241-250, September 01, 1999
• 24: 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
• 25: Chun Zhang , Jeffrey Naughton , David DeWitt , Qiong Luo , Guy Lohman, On supporting containment queries in relational database management systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.425-436, May 21-24, 2001, Santa Barbara, California, United States
• 26: Zijian Zheng , Ron Kohavi , Llew Mason, Real world performance of association rule algorithms, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.401-406, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502572]

INDEX TERMS

Keywords:
association rule discovery, relational divison, set containment join