Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper discusses a novel communication efficient distributed algorithm for approximate mining of frequent patterns from transactional databases. The proposed algorithm consists in the distributed exact computation of locally frequent itemsets and an effective method for inferring the local support of locally unfrequent itemsets. The combination of the two strategies gives a good approximation of the set of the globally frequent patterns and their supports. Several tests on publicly available datasets were conducted, aimed at evaluating the similarity between the exact result set and the approximate ones returned by our distributed algorithm as well as the scalability of the proposed method.

REFERENCES

• 1: Workshop on frequent itemset mining implementations FIMI'03 in conjunction with ICDM'03. In fimi.cs.helsinki.fi, 2003.
• 2: Ramesh C. Agarwal , Charu C. Aggarwal , V. V. V. Prasad, A tree projection algorithm for generation of frequent item sets, Journal of Parallel and Distributed Computing, v.61 n.3, p.350-371, March 1, 2001 [doi>10.1006/jpdc.2000.1693]
• 3: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 4: 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
• 5: Andreas Mueller, Fast sequential and parallel algorithms for association rule mining: a comparison, University of Maryland at College Park, College Park, MD, 1995
• 6: Roberto J. Bayardo, Jr., Efficiently mining long patterns from databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.85-93, June 01-04, 1998, Seattle, Washington, United States
• 7: Tom Brijs , Gilbert Swinnen , Koen Vanhoof , Geert Wets, Using association rules for product assortment decisions: a case study, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.254-260, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312241]
• 8: David W. Cheung , Jiawei Han , Vincent T. Ng , Ada W. Fu , Yongjian Fu, A fast distributed algorithm for mining association rules, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.31-43, December 18-20, 1996, Miami Beach, Florida, United States
• 9: Douglas Burdick , Manuel Calimlim , Johannes Gehrke, MAFIA: A Maximal Frequent Itemset Algorithm for Transactional Databases, Proceedings of the 17th International Conference on Data Engineering, p.443-452, April 02-06, 2001
• 10: Usama M. Fayyad , Gregory Piatetsky-Shapiro , Padhraic Smyth , Ramasamy Uthurusamy, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 11: Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, Mining Very Large Databases, Computer, v.32 n.8, p.38-45, August 1999 [doi>10.1109/2.781633]
• 12: Karolien Geurts, Geert Wets, Tom Brijs, and Koen Vanhoof. Profiling high frequency accident locations using association rules. In Proceedings of the 82nd Annual Transportation Research Board, Washington DC. (USA), January 12-16, page 18pp, 2003.
• 13: Eui-Hong (Sam) Han , George Karypis , Vipin Kumar, Scalable Parallel Data Mining for Association Rules, IEEE Transactions on Knowledge and Data Engineering, v.12 n.3, p.337-352, May 2000 [doi>10.1109/69.846289]
• 14: 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
• 15: B. Park and H. Kargupta. Distributed Data Mining: Algorithms, Systems, and Applications. In Data Mining Handbook, pages 341--358. IEA, 2002.
• 16: Jong Soo Park , Ming-Syan Chen , Philip S. Yu, An effective hash-based algorithm for mining association rules, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.175-186, May 22-25, 1995, San Jose, California, United States
• 17: Srinivasan Parthasarathy, Efficient Progressive Sampling for Association Rules, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.354, December 09-12, 2002
• 18: Rakesh Agrawal , John C. Shafer, Parallel Mining of Association Rules, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.962-969, December 1996 [doi>10.1109/69.553164]
• 19: Naren Ramakrishnan , Ananth Y. Grama, Data Mining-Guest Editors' Introduction: From Serendipity to Science, Computer, v.32 n.8, p.34-37, August 1999 [doi>10.1109/2.781632]
• 20: Ashoka Savasere , Edward Omiecinski , Shamkant B. Navathe, An Efficient Algorithm for Mining Association Rules in Large Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.432-444, September 11-15, 1995
• 21: Assaf Schuster , Ran Wolff, Communication-efficient distributed mining of association rules, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.473-484, May 21-24, 2001, Santa Barbara, California, United States
• 22: Assaf Schuster , Ran Wolff , Dan Trock, A High-Performance Distributed Algorithm for Mining Association Rules, Proceedings of the Third IEEE International Conference on Data Mining, p.291, November 19-22, 2003
• 23: Takahiko Shintani , Masaru Kitsuregawa, Hash based parallel algorithms for mining association rules, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.19-30, December 18-20, 1996, Miami Beach, Florida, United States
• 24: S. Orlando, P. Palmerini, R. Perego, C. Lucchese, and F. Silvestri. kdci: a multi-strategy algorithm for mining frequent sets. In Proceedings of the workshop on Frequent Itemset Mining Implementations FIMI'03 in conjunction with ICDM'03, 2003.
• 25: S. Orlando , P. Palmerini , R. Perego , F. Silvestri, Adaptive and Resource-Aware Mining of Frequent Sets, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.338, December 09-12, 2002
• 26: S. Orlando, P. Palmerini, R. Perego, and F. Silvestri. An efficient parallel and distributed algorithm for counting frequent sets. In Proc. of Int. Conf. VECPAR 2002 - LNCS 2565, pages 197--204. Spinger, 2002.
• 27: Viviane Crestana-Jensen , Nandit Soparkar, Frequent Itemset Counting Across Multiple Tables, Proceedings of the 4th Pacific-Asia Conference on Knowledge Discovery and Data Mining, Current Issues and New Applications, p.49-61, April 18-20, 2000
• 28: Ran Wolff , Assaf Schuster, Association Rule Mining in Peer-to-Peer Systems, Proceedings of the Third IEEE International Conference on Data Mining, p.363, November 19-22, 2003
• 29: Mohammed J. Zaki, Scalable Algorithms for Association Mining, IEEE Transactions on Knowledge and Data Engineering, v.12 n.3, p.372-390, May 2000 [doi>10.1109/69.846291]
• 30: Mohammed J. Zaki, Parallel and Distributed Association Mining: A Survey, IEEE Concurrency, v.7 n.4, p.14-25, October 1999 [doi>10.1109/4434.806975]

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation

Keywords:
approximate data mining, association mining, distributed data mining, frequent itemsets