Extracting predicates from mining models for efficient query evaluation

ABSTRACT

Modern relational database systems are beginning to support ad hoc queries on mining models. In this article, we explore novel techniques for optimizing queries that contain predicates on the results of application of mining models to relational data. For such queries, we use the internal structure of the mining model to automatically derive traditional database predicates. We present algorithms for deriving such predicates for a large class of popular discrete mining models: decision trees, naive Bayes, clustering and linear support vector machines. Our experiments on Microsoft SQL Server demonstrate that these derived predicates can significantly reduce the cost of evaluating such queries.

REFERENCES

• 1: Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States
• 2: Rakesh Agrawal , Sakti P. Ghosh , Tomasz Imielinski , Balakrishna R. Iyer , Arun N. Swami, An Interval Classifier for Database Mining Applications, Proceedings of the 18th International Conference on Very Large Data Bases, p.560-573, August 23-27, 1992
• 3: Agrawal, S., Chaudhuri, S., Kollar, L., and Narasayya, V. 2000. Index tuning wizard for Microsoft SQL server 2000. White paper. Microsoft Corporation, Redmond, WA. Available online at http://msdn.microsoft.com/library/techart/itwforsql.htm.
• 4: Bay, S. D. 1999. The UCI KDD archive {http://kdd.ics.uci.edu}. Department of Information and Computer Science, University of California, Irvine, Irvine, CA.
• 5: Benson, S., McInnes, L. C., More, J. J., and Sarich, J. 2003. TAO (Toolkit for Advanced Optimization) Users Manual. Tech. rep. ANL/MCS-TM-242---Revision 1.5. Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL. Available online at http://www-fp.mcs.anl.gov/tao/.
• 6: Berger, M. and Regoutsos, I. 1991. An algorithm for point clustering and grid generation. IEEE Trans. Syst. Man Cybernet. 21, 5, 1278--86.
• 7: Blake, C. and Merz, C. 1998. UCI repository of machine learning databases. Department of Information and Computer Science, University of California, Irvine, Irvine, CA. Available online at http://www.ics.uci.edu/mlearn/MLRepository.html.
• 8: Christopher J. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, v.2 n.2, p.121-167, June 1998 [doi>10.1023/A:1009715923555 ]
• 9: Chang, C.-C. and Lin, C.-J. 2001. LIBSVM: A Library for Support Vector Machines. Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan. Software available online at http://www.csie.ntu.edu.tw/cjlin/libsvm.
• 10: Surajit Chaudhuri, Finding nonrecursive envelopes for Datalog predicate, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.135-146, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153862]
• 11: Chaudhuri, S. 1998. Data mining and database systems: Where is the intersection? In Bulletin of the Technical Committee on Data Engineering. Vol. 21.
• 12: Surajit Chaudhuri , Umeshwar Dayal, An overview of data warehousing and OLAP technology, ACM SIGMOD Record, v.26 n.1, p.65-74, March 1997 [doi>10.1145/248603.248616]
• 13: Surajit Chaudhuri , Prasanna Ganesan , Sunita Sarawagi, Factorizing complex predicates in queries to exploit indexes, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872802]
• 14: Surajit Chaudhuri , Phokion G. Kolaitis, Can Datalog be approximated?, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.86-96, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182602]
• 15: Efficient Evaluation of Queries with Mining Predicates, Proceedings of the 18th International Conference on Data Engineering, p.529, February 26-March 01, 2002
• 16: Surajit Chaudhuri , Vivek R. Narasayya, An Efficient Cost-Driven Index Selection Tool for Microsoft SQL Server, Proceedings of the 23rd International Conference on Very Large Data Bases, p.146-155, August 25-29, 1997
• 17: Surajit Chaudhuri , Kyuseok Shim, Optimization of Queries with User-defined Predicates, Proceedings of the 22th International Conference on Very Large Data Bases, p.87-98, September 03-06, 1996
• 18: Cohen, W. W. 1995. Fast effective rule induction. In Proceedings of the 12th International Conference on Machine Learning. Morgan Kaufmann, San Francisco, CA, 115--123.
• 19: Mark W. Craven , Jude W. Shavlik, Using neural networks for data mining, Future Generation Computer Systems, v.13 n.2-3, p.211-229, Nov. 1997 [doi>10.1016/S0167-739X(97)00022-8 ]
• 20: Dougherty, J., Kohavi, R., and Sahami, M. 1995. Supervised and unsupervised discretization of continuous features. In Proceedings of the 12th International Conference on Machine Learning. Morgan Kaufmann, San Francisco, CA, 194--202.
• 21: Ester, M., Kriegel, H.-P., Sander, J., and Xu, X. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 2nd International Conference on Knowledge Discovery in Databases and Data Mining (Portland, OR).
• 22: Joseph M. Hellerstein , Michael Stonebraker, Predicate migration: optimizing queries with expensive predicates, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.267-276, May 25-28, 1993, Washington, D.C., United States
• 23: Hong, S. J. 1987. MINI: A heuristic algorithm for two-level logic minimization. In Selected Papers on Logic Synthesis for Integrated Circuit Design, R. Newton, Ed. IEEE Press, Los Alamitos, CA.
• 24: Ron Kohavi , Dan Sommerfield , James Dougherty, Data Mining using MLC++, A Machine Learning Library in C++, Proceedings of the 8th International Conference on Tools with Artificial Intelligence (ICTAI '96), p.234, November 16-19, 1996
• 25: Hongjun Lu , Rudy Setiono , Huan Liu, NeuroRule: A Connectionist Approach to Data Mining, Proceedings of the 21th International Conference on Very Large Data Bases, p.478-489, September 11-15, 1995
• 26: McLachlan, G. and Basford, K. 1988. Mixture models: Inference and Applications to Clustering. Marcel Dekker, New York, NY.
• 27: Rosa Meo , Giuseppe Psaila , Stefano Ceri, An Extension to SQL for Mining Association Rules, Data Mining and Knowledge Discovery, v.2 n.2, p.195-224, June 1998 [doi>10.1023/A:1009774406717 ]
• 28: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 29: C. Mohan , Don Haderle , Yun Wang , Josephine Cheng, Single table access using multiple indexes: optimization, execution, and concurrency control techniques, Proceedings of the international conference on extending database technology on Advances in database technology, p.29-43, March 1990, Venice, Italy
• 30: David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, Chromatic nearest neighbor searching: a query sensitive approach, Computational Geometry: Theory and Applications, v.17 n.3-4, p.97-119, Dec. 2000 [doi>10.1016/S0925-7721(00)00021-3 ]
• 31: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 32: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 33: R. A. Reckhow , J. Culberson, Covering a simple orthogonal polygon with a minimum number of orthogonally convex polygons, Proceedings of the third annual symposium on Computational geometry, p.268-277, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41987]
• 34: 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
• 35: Wolfgang Scheufele , Guido Moerkotte, Efficient Dynamic Programming Algorithms for Ordering Expensive Joins and Selections, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.201-215, March 23-27, 1998

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.4 Systems
          Subjects: Query processing

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models

General Terms:
Algorithms, Performance

Keywords:
Complex predicate optimization, simpler rules from complex predictive functions