在資料探勘的領域中，探勘關連規則扮演著相當重要的地位。本篇論文以Apriori為基礎，在p2p(Peer to Peer)網路上探勘最大頻繁項目集(Maximal Frequent Itemsets)。其演算法分為兩階段，第一階段利用收集各節點局部的最大頻繁項目集(Local Maximal Frequent Itemsets)，並增加預測方式以產生部份的頻繁與非頻繁項目集，以利於在第二階段對產生的候選項目集做刪除的動作，來減少需要驗證的候選項目集來達到減少網路上封包的數量。而第二階段演算法則是以Apriori為主，但不同於Apriori的是增加預測較長的候選項目集，得到較長的頻繁項目集以增加下一個長度的候選項目集刪除的個數。從實驗結果顯示，不論是在密集資料庫或者稀疏資料庫，都能大量的減少網路上封包的傳輸量。

Association rule mining is one of most popular problems in the field of data mining. We propose a novel algorithm for distributed maximal frequent itemset mining in unstructured peer-to-peer networks based on a bottom-up Apriori-like process. The algorithm combines with two part. First, the master node collects local maximal frequent itmesets from others and discovers a set of maximal frequent itemsets and minimal non-frequent itmesets for subset infrequency pruning strategy and superset frequency pruning strategy. In the second stage, it is based on a bottom-up Apriori-like process. Unlike Apriori, this stage generates longer candidates at each level. Correctly predicted long itemsets are used for superset frequency pruning. An extensive set of experiments show that our proposed strategy is effective in candidate prediction, thus requiring significantly less message exchange than traditional approaches.

[1]R. Agrawal and J. Shafer. Parallel mining of association rules. IEEE Transactions on Knowledge and Data Engineering, 8(6):962 . 969, 1996
[2]R. Agrawal, and R. Srikant, “Fast Algorithms for Mining Association Rules in Large Databases,” Proceedings of the 20th International Conference on Very Large Data Bases, (VLDB'94), pp. 487-499, Sep. 1994
[3]Rakesh Agrawal, Tomasz Imielinski, and Arun N. Swami. Mining association rules between sets of items in large databases. In Proc. of the ACM SIGMOD Int'l. Conference on Management of Data, pages 207.216, Washington, D.C., June 1993
[4]R. J. Bayardo Jr. Efficiently mining long patterns from databases. In SIGMOD, 1998.
[5]Y. Birk, L. Liss, A. Schuster, and R. Wolff. A local algorithm for ad hoc majority voting via charge fusion. In Proc. of DISC, October 2004
[6]B. Bloom. Space/time tradeoffs in in hash coding with allowable errors. Communications of the ACM, 13(7):422-426, 1970
[7]Bonomi, Flavio; Mitzenmacher, Michael; Panigrahy, Rina; Singh, Sushil; Varghese, George (2006), "An Improved Construction for Counting Bloom Filters", Algorithms – ESA 2006, 14th Annual European Symposium, 4168, pp. 684–695
[8]S. Brin, R. Motwani, and C. Silverstein. Beyond market baskets: Generalizing association rules to correlations. In ACM SIGMOD, 1997
[9]S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, “Randomized gossip algorithms,” IEEE Trans. Info. Theory, vol. 52, no. 6, 2006
[10]D. Cheung and Y. Xiao. Effect of data skewness in parallel mining of association rules. In 12th Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 48 . 60, April 1998.