Performance Evaluation and Analysis of K-Way Join Variants for Association Rule Mining

  • P. Mishra
  • S. Chakravarthy
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2712)


Data mining aims at discovering important and previously unknown patterns from the dataset in the underlying database. Database mining performs mining directly on data stored in (relational) database management systems (RDBMSs). The type of underlying database can vary and should not be a constraint on the mining process. Irrespective of the database in which data is stored, we should be able to mine the data. Several SQL92 approaches (such as K-way join, Query/Subquery, and Two-group by) have been studied in the literature.

In this paper, we focus on the K-way join approach. We study several additional optimizations for the K-way join approach and evaluate them using DB2 and Oracle RDBMSs. We evaluate the approaches analytically and compare their performance on large data sets. Finally, we summarize the results and indicate the conditions for which the individual optimizations are useful. The larger goal of this work is to feed these results into a layered optimizer that chooses specific strategies based on the input dataset characteristics.


Association Rule Mining Algorithm Frequent Itemsets Association Rule Mining Support Counting 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Agrawal, R., T. Imielinski, and A. Swami. Mining Association Rules between sets of items in large databases. in ACM SIGMOD 1993.Google Scholar
  2. 2.
    Agrawal, R. and R. Srikant. Fast Algorithms for mining association rules. in 20th Int’l Conference on Very Large Databases (VLDB). 1994.Google Scholar
  3. 3.
    Savasere, A., E. Omiecinsky, and S. Navathe. An efficient algorithm for mining association rules in large databases. in 21st Int’l Cong. on Very Large Databases (VLDB). 1995. Zürich, Switzerland.Google Scholar
  4. 4.
    Shenoy, P., et al. Turbo-charging Vertical Mining of Large Databases. in ACM SIGMOD Int’l Conference on Management of Data. 2000. Dallas.Google Scholar
  5. 5.
    Han, J., J. Pei, and Y. Yin. Mining Frequent Patterns wihtout Candidate Generation. in ACM SIGMOD 2000. Dallas.Google Scholar
  6. 6.
    Houtsma, M. and A. Swami. Set-Oriented Mining for Association Rules in Relational Databases. in 11th ICDE, 1995.Google Scholar
  7. 7.
    Han, J., et al. DMQL: A data mining query language for relational database. in ACM SIGMOD workshop on research issues on data mining and knowledge discovery. 1996. Montreal.Google Scholar
  8. 8.
    Meo, R., G. Psaila, and S. Ceri. A New SQL-like Operator for Mining Association Rules. in Pro. of the 22nd VLDB Conference. 1996 India.Google Scholar
  9. 9.
    Agrawal, R. and K. Shim, Developing tightly-coupled Data Mining Applications on a Relational Database System. 1995, IBM Almaden Research Center: San Jose, California.Google Scholar
  10. 10.
    Sarawagi, S., S. Thomas, and R. Agrawal. Integrating Association Rule Mining with Rekational Database System: Alternatives and Implications. in ACM SIGMOD 1998. Seattle, Washington.Google Scholar
  11. 11.
    Thomas, S., Architectures and optimizations for integrating Data Mining algorithms with Database Systems, in CSE. 1998, University of Florida.Google Scholar
  12. 12.
    Dudgikar, M., A Layered Optimizer or Mining Association Rules over RDBMS, in CSE Department. 2000, University of Florida: Gainesville.Google Scholar
  13. 13.
    Mishra, P. Evaluation of K-way Join and its variants for Association Rule Mining. MS Thesis 2002, Information and Technology Lab and CSE Department at UT Arlington, TX.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • P. Mishra
    • 1
  • S. Chakravarthy
    • 1
  1. 1.Information and Technology LaboratoryThe University of Texas at ArlingtonArlington

Personalised recommendations