臺灣博碩士論文加值系統

在這篇論文中, 我們提出一個實做在分散式環境中,理論式的演算法. 這演算法可以有效率的解決FP-tree的問題.此演算法使用divide and conquer的概念將大的資料集分割成多個子資料集.將資料分割可以減少演算法的總執行時間.此外,我們的演算法並不建構完整的FP-tree,取而代之的是使用一種叫做intermittence的概念也可有效率的降低執行時間.我們在傳送資料時,也會將資料壓縮成一維陣列以減少溝通成本.

In this paper, we proposed a novel algorithm which is implemented on the distributed system that can efficiently solve the problem of FP-tree.
The algorithm uses divide and conquer to split big database into several sub-database. With data division, the algorithm can reduce the total execution time of algorithm. The algorithm doesn’t construct the whole FP-tree. Instead, with intermittence, a time division mechanism, the algorithm can also efficiently reduce the execution time. We also compress the data into a one dimensional array while transmitting, which can reduce the communication cost.

1. Introduction 1
1.1 Background 1
1.2 Existing Solutions 2
1.3 Our methods 4
2. Related Works 4
2.1 Frequent Pattern-tree Algorithm 5
2.1.1 FP-tree construction 5
2.1.2 FP-growth 7
3. Our method 9
3.1 Notations 9
3.2 Proposed algorithm 11
3.2.1 The first scan 12
3.2.2 The second scan 13
3.2.2.1 Encode data 14
3.2.2.2 Intermittence transmitting 19
4. ANALYSIS 21
5. EXPERIMENT RESULTS AND DISCUSSION 23
6. CONCLUSION AND FUTURE WORKS 25
References 26

[1]R. Agrawal and R. Srikant, "Fast Algorithms for Mining Association Rules," Proceedings of the 20th VLDB Conference Santiago, Chile, 1994.
[2]J. Han, J. Pei, and Y. Yin, "Mining Frequent Patterns without Candidate Generation," Proceedings of the 2000 ACM SIGMOD international conference on Management of data, Dallas, Texas, United States.
[3]A. JAVED and A. KHOKHAR, "Frequent Pattern Mining on Message Passing Multiprocessor Systems," Distributed and Parallel Databases, Volume 16, 2004.
[4]M. Z. Ashrafi, D. Taniar, and K. Smith, "ODAM: An Optimized Distributed Association Rule Mining Algorithm," IEEE Distributed Systems Online 1541-4922, IEEE Computer Society, vol. 5, No. 3, 2004.
[5]R. Agrawal and J. C. Shafer, "Parallel Mining of Association Rules," IEEE Transactions on Knowledge and Data Engineering vol. 8, No. 6, 1996.
[6]D. W. Cheung, J. Han, V. T. Ng, A. W. Fu, and Y. Fu, "A Fast Distributed Algorithm for Mining Association Rules," Proceedings of the fourth international conference on Parallel and distributed information systems, Miami Beach, Florida, United States, 1996.
[7]A. Schuster and R. Wolff, "CommunicationEfficient Distributed Mining of Association Rules," Proceedings of the 2001 ACM SIGMOD international conference on Management of data, Santa Barbara, California, United States, 2001.
[8]K. M. Yu, J. Zhou, and W. C. Hsiao, "Load Balancing Approach Parallel Algorithm for Frequent Pattern Mining," V. Malyshkin (Ed.): PaCT 2007, LNCS 4671, 2007. © Springer-Verlag Berlin Heidelberg 2007.
[9]D. W. Cheung, V. T. Ng, A. W. Fu, and Y. Fu, "Efficient Mining of Association Rules in Distributed Databases," IEEE Transactions on Knowledke and DATA Engineering, VOL. 8, NO. 6, 1996.
[10] S. M. Chung and C. Luo, "Parallel Mining of Maximal Frequent Itemsets from Databases," Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence (ICTAI’03), Sacramento, California, 2003.
[11] G. Buehrer, S. Parthasarathy, S. Tatikonda, T. Kurc, and J. Saltz, "Toward Terabyte Pattern Mining An Architecture-conscious Solution," Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, San Jose, California, USA, 2007.
[12] J. F. Zhang, H. Shi, and L. Zheng, "A Method and Algorithm Of Distributed Mining Association Rules in Synchronisms," First International Conference on Machine Learning and Cybernetics, Beijing, November 2002.
[13]T. Shintani and M. Kitsuregawa, "Hash Based Parallel Algorithms for Mining Association Rules," Fourth International Conference on Parallel and Distributed Information Systems, Miami Beach, FL, USA, 1996.