Domain and data partitioning for parallel mining of frequent closed itemsets

ABSTRACT

In this paper, we propose an algorithm to partition both the search space and the database for the parallel mining of frequent closed itemsets in large databases. The partitioning of the search space is based on splitting the power set lattice of the total item set to two sub-lattices. Conditional databases axe used to partition the large database. The combination of the search space and database partitioning allows parallel processors to mine the frequent closed itemsets independently and thus minimizes the interprocessor communication and synchronization. The partitioning also ensures the load balance among the parallel processors.

REFERENCES

• 1: 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
• 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: Hannu Toivonen, Sampling Large Databases for Association Rules, Proceedings of the 22th International Conference on Very Large Data Bases, p.134-145, September 03-06, 1996
• 4: Mohammed Javeed Zaki, Srinivasan Parthasarathy, Mitsunori Ogihara, and Wei Li. New algorithms for fast discovery of association rules. In Proceedings of the Third International Conference on Knowledge Discovery and Data Mining, pages 283--286, 1997.
• 5: 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
• 6: 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]
• 7: Karam Gouda , Mohammed Javeed Zaki, Efficiently Mining Maximal Frequent Itemsets, Proceedings of the 2001 IEEE International Conference on Data Mining, p.163-170, November 29-December 02, 2001
• 8: 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]
• 9: Mohammed Javeed Zaki , Srinivasan Parthasarathy , Wei Li, A localized algorithm for parallel association mining, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.321-330, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258524]
• 10: Dejiang Jin , Sotirios G. Ziavras, A Super-Programming Approach for Mining Association Rules in Parallel on PC Clusters, IEEE Transactions on Parallel and Distributed Systems, v.15 n.9, p.783-794, September 2004 [doi>10.1109/TPDS.2004.37]
• 11: Nicolas Pasquier , Yves Bastide , Rafik Taouil , Lotfi Lakhal, Discovering Frequent Closed Itemsets for Association Rules, Proceeding of the 7th International Conference on Database Theory, p.398-416, January 10-12, 1999
• 12: M. J. Zaki , M. Ogihara , S. Parthasarathy , W. Li, Parallel data mining for association rules on shared-memory multi-processors, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.43-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States [doi>10.1145/369028.369117]
• 13: Jian Pei, Jiawei Han, and Runying Mao. Closet: An efficient algorithm for mining frequent closed itemsets. In Proceedings of ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, pages 21--30, 2000.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Algorithms, Design, Performance

Keywords:
association rule, conditional database, frequent closed itemset, parallel algorithm, parallel data mining, partitioning