ACM SIGMOD Anthology VLDB dblp.uni-trier.de

An Efficient Algorithm for Mining Association Rules in Large Databases.

Ashok Savasere, Edward Omiecinski, Shamkant B. Navathe: An Efficient Algorithm for Mining Association Rules in Large Databases. VLDB 1995: 432-444
@inproceedings{DBLP:conf/vldb/SavasereON95,
  author    = {Ashok Savasere and
               Edward Omiecinski and
               Shamkant B. Navathe},
  editor    = {Umeshwar Dayal and
               Peter M. D. Gray and
               Shojiro Nishio},
  title     = {An Efficient Algorithm for Mining Association Rules in Large
               Databases},
  booktitle = {VLDB'95, Proceedings of 21th International Conference on Very
               Large Data Bases, September 11-15, 1995, Zurich, Switzerland},
  publisher = {Morgan Kaufmann},
  year      = {1995},
  isbn      = {1-55860-379-4},
  pages     = {432-444},
  ee        = {db/conf/vldb/SavasereON95.html},
  crossref  = {DBLP:conf/vldb/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Mining for association rules between items in a large database of sales transactions has been described as an important database mining problem. In this paper we present an efficient algorithm for mining association rules that is fundamentally different from known algorithms. Compared to previous algorithms, our algorithm not only reduces the I/O overhead significantly but also has lower CPU overhead for most cases. We have performed extensive experiments and compared the performance of our algorithm with one of the best existing algorithms. It was found that for large databases, the CPU overhead was reduced by as much as a factor of four and I/O was reduced by almost an order of magnitude. Hence this algorithm is especially suitable for very large size databases.

Copyright © 1995 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Umeshwar Dayal, Peter M. D. Gray, Shojiro Nishio (Eds.): VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland. Morgan Kaufmann 1995, ISBN 1-55860-379-4
Contents BibTeX

References

[1]
Rakesh Agrawal, Tomasz Imielinski, Arun N. Swami: Mining Association Rules between Sets of Items in Large Databases. SIGMOD Conference 1993: 207-216 BibTeX
[2]
Rakesh Agrawal, Ramakrishnan Srikant: Fast Algorithms for Mining Association Rules in Large Databases. VLDB 1994: 487-499 BibTeX
[3]
...
[4]
Jiawei Han, Yandong Cai, Nick Cercone: Knowledge Discovery in Databases: An Attribute-Oriented Approach. VLDB 1992: 547-559 BibTeX
[5]
...
[6]
Maurice A. W. Houtsma, Arun N. Swami: Set-Oriented Mining for Association Rules in Relational Databases. ICDE 1995: 25-33 BibTeX
[7]
Ravi Krishnamurthy, Tomasz Imielinski: Research Directions in Knowledge Discovery. SIGMOD Record 20(3): 76-78(1991) BibTeX
[8]
Gregory Piatetsky-Shapiro, William J. Frawley (Eds.): Knowledge Discovery in Databases. AAAI/MIT Press 1991, ISBN 0-262-62080-4
Contents BibTeX
[9]
...
[10]
Abraham Silberschatz, Michael Stonebraker, Jeffrey D. Ullman: Database Systems: Achievements and Opportunities. Commun. ACM 34(10): 110-120(1991) BibTeX
[11]
Michael Stonebraker, Rakesh Agrawal, Umeshwar Dayal, Erich J. Neuhold, Andreas Reuter: DBMS Research at a Crossroads: The Vienna Update. VLDB 1993: 688-692 BibTeX
[12]
Shalom Tsur: Data Dredging. IEEE Data Eng. Bull. 13(4): 58-63(1990) BibTeX
[13]
Jason Tsong-Li Wang, Gung-Wei Chirn, Thomas G. Marr, Bruce A. Shapiro, Dennis Shasha, Kaizhong Zhang: Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results. SIGMOD Conference 1994: 115-125 BibTeX

Referenced by

  1. Flip Korn, Alexandros Labrinidis, Yannis Kotidis, Christos Faloutsos: Quantifiable Data Mining Using Ratio Rules. VLDB J. 8(3-4): 254-266(2000)
  2. Themistoklis Palpanas: Knowledge Discovery in Data Warehouses. SIGMOD Record 29(3): 88-100(2000)
  3. Ke Wang, Yu He, Jiawei Han: Mining Frequent Itemsets Using Support Constraints. VLDB 2000: 43-52
  4. Pradeep Shenoy, Jayant R. Haritsa, S. Sudarshan, Gaurav Bhalotia, Mayank Bawa, Devavrat Shah: Turbo-charging Vertical Mining of Large Databases. SIGMOD Conference 2000: 22-33
  5. Jiawei Han, Jian Pei, Yiwen Yin: Mining Frequent Patterns without Candidate Generation. SIGMOD Conference 2000: 1-12
  6. Minos N. Garofalakis, Rajeev Rastogi, S. Seshadri, Kyuseok Shim: Data Mining and the Web: Past, Present and Future. Workshop on Web Information and Data Management 1999: 43-47
  7. Christian Hidber: Online Association Rule Mining. SIGMOD Conference 1999: 145-156
  8. Venkatesh Ganti, Johannes Gehrke, Raghu Ramakrishnan: A Framework for Measuring Changes in Data Characteristics. PODS 1999: 126-137
  9. Nicolas Pasquier, Yves Bastide, Rafik Taouil, Lotfi Lakhal: Discovering Frequent Closed Itemsets for Association Rules. ICDT 1999: 398-416
  10. Rajeev Rastogi, Kyuseok Shim: Mining Optimized Support Rules for Numeric Attributes. ICDE 1999: 206-215
  11. Holger Günzel, Jens Albrecht, Wolfgang Lehner: Data Mining in a Multidimensional Environment. ADBIS 1999: 191-204
  12. Chan Man Kuok, Ada Wai-Chee Fu, Man Hon Wong: Mining Fuzzy Association Rules in Databases. SIGMOD Record 27(1): 41-46(1998)
  13. Charu C. Aggarwal, Philip S. Yu: Mining Large Itemsets for Association Rules. IEEE Data Eng. Bull. 21(1): 23-31(1998)
  14. Sridhar Ramaswamy, Sameer Mahajan, Abraham Silberschatz: On the Discovery of Interesting Patterns in Association Rules. VLDB 1998: 368-379
  15. Flip Korn, Alexandros Labrinidis, Yannis Kotidis, Christos Faloutsos: Ratio Rules: A New Paradigm for Fast, Quantifiable Data Mining. VLDB 1998: 582-593
  16. Raymond T. Ng, Laks V. S. Lakshmanan, Jiawei Han, Alex Pang: Exploratory Mining and Pruning Optimizations of Constrained Association Rules. SIGMOD Conference 1998: 13-24
  17. Roberto J. Bayardo Jr.: Efficiently Mining Long Patterns from Databases. SIGMOD Conference 1998: 85-93
  18. Ashok Savasere, Edward Omiecinski, Shamkant B. Navathe: Mining for Strong Negative Associations in a Large Database of Customer Transactions. ICDE 1998: 494-502
  19. Banu Özden, Sridhar Ramaswamy, Abraham Silberschatz: Cyclic Association Rules. ICDE 1998: 412-421
  20. Rosa Meo, Giuseppe Psaila, Stefano Ceri: A Tightly-Coupled Architecture for Data Mining. ICDE 1998: 316-323
  21. Jun-Lin Lin, Margaret H. Dunham: Mining Association Rules: Anti-Skew Algorithms. ICDE 1998: 486-493
  22. Charu C. Aggarwal, Philip S. Yu: Online Generation of Association Rules. ICDE 1998: 402-411
  23. Dao-I Lin, Zvi M. Kedem: Pincer Search: A New Algorithm for Discovering the Maximum Frequent Set. EDBT 1998: 105-119
  24. Marek Wojciechowski, Maciej Zakrzewicz: Itemset Materializing for Fast Mining of Association Rules. ADBIS 1998: 284-295
  25. Tomasz Imielinski, Aashu Virmani: Association Rules... and What's Next? Towards Second Generation Data Mining Systems. ADBIS 1998: 6-25
  26. Renée J. Miller, Yuping Yang: Association Rules over Interval Data. SIGMOD Conference 1997: 452-461
  27. Eui-Hong Han, George Karypis, Vipin Kumar: Scalable Parallel Data Mining for Association Rules. SIGMOD Conference 1997: 277-288
  28. Sergey Brin, Rajeev Motwani, Craig Silverstein: Beyond Market Baskets: Generalizing Association Rules to Correlations. SIGMOD Conference 1997: 265-276
  29. Heikki Mannila: Methods and Problems in Data Mining. ICDT 1997: 41-55
  30. Dimitrios Gunopulos, Heikki Mannila, Sanjeev Saluja: Discovering All Most Specific Sentences by Randomized Algorithms. ICDT 1997: 215-229
  31. Tadeusz Morzy, Maciej Zakrzewicz: SQL-Like Language for Database Mining. ADBIS 1997: 311-317
  32. David Wai-Lok Cheung, Vincent T. Y. Ng, Ada Wai-Chee Fu, Yongjian Fu: Efficient Mining of Association Rules in Distributed Databases. IEEE Trans. Knowl. Data Eng. 8(6): 911-922(1996)
  33. Ming-Syan Chen, Jiawei Han, Philip S. Yu: Data Mining: An Overview from a Database Perspective. IEEE Trans. Knowl. Data Eng. 8(6): 866-883(1996)
  34. Rakesh Agrawal, John C. Shafer: Parallel Mining of Association Rules. IEEE Trans. Knowl. Data Eng. 8(6): 962-969(1996)
  35. Tomasz Imielinski, Heikki Mannila: A Database Perspective on Knowledge Discovery. Commun. ACM 39(11): 58-64(1996)
  36. Hannu Toivonen: Sampling Large Databases for Association Rules. VLDB 1996: 134-145
  37. Heikki Mannila: Data Mining: Machine Learning, Statistics, and Databases. SSDBM 1996: 2-9
  38. Ramakrishnan Srikant, Rakesh Agrawal: Mining Quantitative Association Rules in Large Relational Tables. SIGMOD Conference 1996: 1-12
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
 ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:46:06 2009