Tổng luận về khai thác song song tập phổ biến từ dữ liệu giao dịch trên bộ xử lý đa nhân

dữ liệu UCI). Nhóm tác g iả chƣa quan tâm đến g iải pháp cân bằng tải. Song song đó, nhóm tác giả Wang đã đề xuất thuật toán D2P-Apriori [34]; phần thực nghiệm trên GeForce GTX 1080 (2.560 CUDA cores) với các ngƣỡng minsup lớn - chƣa thể hiện rõ hiệu suất của thuật toán. Năm 2019, Huan đã đề xuất thuật toán NPA-CFI [35] – thuật toán song song khai thác tập phổ biến đóng trên BXLĐN theo hƣớng tiếp cận giải pháp (2). Thuật toán NPA-CFI, phân chia thành 3 Pha độc lập, tác vụ song song tự nhiên trên Pha 1 và Pha 3. Điều này đã làm g ia tăng hiệu năng của thuật toán đáng kể. Tuy nhiên, ở Pha 3 của thuật toán vẫn chƣa đề cập đến giải pháp cân bằng tải. Cùng thời điểm trên, Wu đề xuất thuật toán GFPG-LLMA [36] – thực nghiệm trên GeForce GTX 1070 (1.920 CUDA cores), h iệu suất chƣa cao và nhóm tác giả cũng bỏ ngỏ vấn đề cân bằng tải. Nhìn chung, phần lớn các công trình nghiên cứu lựa chọn giải pháp (3) cho bài toán khai thác song song tập phổ biến và chƣa thật sự quan tâm đến vấn đề cân bằng tải. C. Xác định tới hạn theo định luật Amdahl và Gustafson Chúng tôi đã khảo sát gần 30 công trình nghiên cứu liên quan khai thác song song tập phổ biến trên BXLĐN, chƣa thấy công trình đề cập đến vấn đề tới hạn theo cả 2 định luật. D. Đánh giá hiệu năng của giải thuật trên BXLĐN Các g iải thuật trên chƣa tính toán cụ thể hiệu suất khai thác tập phổ biến trên từng nhân xử lý (Core). Chúng tôi khảo sát và chọn lựa phƣơng pháp tính hiệu năng [35] trên từng nhân xử lý theo phƣơng trình nhƣ sau: ¸ ¹ ·¨ © §¸ ¹ ·¨ © §  c T c TTHS SSM1 (5) Trong đó: - TS: thời gian thực hiện tuần tự - TM: thời gian thực hiện tính song song trên BXLĐN - c: số lƣợng nhân của CPU (số core) Đây là cơ sở khi so sánh các giải thuật song song theo định hƣớng của giải pháp (2) – tìm giải thuật tốt hơn. V. KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN Trong bài viết này, chúng tôi khảo sát và tổng luận về một số thuật toán khai thác song song tập phổ biến trên BXLĐN theo hƣớng tiếp cận phân tích cấu trúc dữ liệu và chiến lƣợc tìm kiếm trên không gian sinh, đƣợc sử dụng trong khai thác song song tập phổ biến trong một số công trình suốt hơn hai mươi năm qua. Qua đó, giúp các nhà nghiên cứu trong lĩnh vực khai thác dữ liệu có đầy đủ cở sở khi lựa chọn giải pháp kỹ thuật phù hợp cho bài toán khai thác song song tập phổ biến trên BXLĐN. Bên cạnh đó, tổng luận còn cho thấy chƣa có nhiều đề xuất quan tâm đến vấn đề cân bằng tải và một số công trình chỉ mang t ính thực nghiệm chuyển từ thuật toán tuần tự sang môi trƣờng tính toán song song – giải pháp (3). Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020) ISBN: 978-604-80-5076-4 300 Dựa trên các khảo sát và tổng luận một số thuật toán khai thác song song tập phổ biến trên BXLĐN đƣợc trình bày ở phần 3 và 4: Tƣơng lai, chúng tôi sẽ nghiên cứu tìm kiếm giải thuật tốt hơn để có thể khai thác song song tập phổ biến trên dữ liệu giao dịch cỡ lớn, có trọng số, cũng nhƣ mở rộng trên các hệ thống tính toán phân tán nhƣ Hadoop, SprakNgoài ra, chúng tôi cũng tập trung quan tâm đến việc tìm kiếm giả i pháp cho vấn đề cân bằng tải để đảm bảo hiệu năng cao nhất khi thực hiện trên BXLĐN. LỜI CẢM ƠN Nghiên cứu đƣợc tài trợ bởi Viện Đào tạo và Nâng cao TP.HCM trong đề tài có mã số V2019.09. TÀI LIỆU THAM KHẢO [1] R. Agrawal, T. Imilienski, A. Swami. Mining association rules between sets of large databases. Proceedings of the ACM SIGMOD International Conference on Management of Data, Washington, DC, (1993), 207-216. [2] J. Han, J. Pei, Y. Yin. Mining Frequent Patterns without Candidate Generation. SIGMOD Conf. 2000, (2000), 1-12. (FP-tree,FI) [3] J. Liu, Y. Pan, K. Wang, J. Han. Mining frequent item sets by opportunistic projection. KDD 2002, (2002), 229-238. (Prefix-Tree,FI) [4] N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal. Discovering frequent closed itemsets for association rules. Proceecings of the 5th Int Conf on Database Theory, LNCS, Springer-Verlag, Jerusalem, Israel, (1999), 398–416. (lattice – Aclose) [5] M.J. Zaki, C. J. Hsiao. CHARM: An Efficient Algorithm for Closed Association Rule Mining. (1999), 1-20. (IT-Tree) [6] D. Lin, Z. M. Kedem. Pincer-Search: A New Algorithm for Discovering the Maximum Frequent Itemset. EDBT Conference Proceedings, (1998), 105-110. (Pincer) [7] D. Burdick, M. Calimlim, J. Gehrke. MAFIA: A Maximal Frequent Itemset Algorithm for Transactional Databases. Proc of the ICDE Conf, (2001), 443-452. [8] R. J. Bayardo. Efficiently mining long patterns from databases. in Proc. The ACM SIGMOD Int. Conf. on Management of data, (1998), 85-93. (SE-Tree) [9] R. Agarwal, C. Aggarwal, V. V. V. Prasad. Depth First Generation of Long Patterns. In Proc. ACM SIGMOD, (2000), 108-118. [10] J. S. Park, M. S. Chen, P. S. Yu. Efficient Parallel and Data Mining for Association Rules. CIKM 1995: (1995), 31-36. [11] M. J. Zaki, M. Ogihara, S. Parthasarathy, W. Li. Parallel Data Mining for Association Rules on Shared-Memory Multi-Processors. SC 1996: (1996), 43. [12] R. Agrawal, J. C. Shafer. Parallel mining of association rules. in IEEE Transactions on Knowledge and Data Engineering, vol. 8, no. 6, pp. 962-969, (1996), doi: 10.1109/69.553164. [13] E. Han, G. Karypis and V. Kumar. Scalable Parallel Data Mining for Association Rules. Proc. ACM Special Interest Group on Management of Data (SIGMOD), (1997). [14] M. J. Zaki, S. Parthasarathy, M. Ogihara, W. Li. Parallel Algorithms for Discovery of Association Rules. Data Min. Knowl. Discov. 1(4): (1997), 343-373. [15] S.M. Chung, C. Luo. Parallel mining of maximal frequent itemsets from databases. Tools with Artificial Intelligence 2003. Proceedings. 15th IEEE International Conference on, (2003), 134-139. [16] A. Javed, A. Khokhar. Frequent pattern mining on message passing multiprocessor systems. Distributed and Parallel Databases, 16(3), (2004), 321-334. [17] L. Liu, E. Li, Y. Zhang, Z. Tang. Optimization of Frequent Itemset Mining on Multiple-Core Processor. VLDB ’07: (2007), 1275–1285. [18] S. H. Adil, S. Qamar. Implementation of association rule mining using CUDA. 2009 International Conference on Emerging Technologies, Islamabad, (2009), 332-336. [19] J. Zhou, K. M. Yu*, B. C. Wu. Parallel Frequent Patterns Mining Algorithm on GPU. IEEE International Conference on Systems Man and Cybernetics (SMC2010), (2010), 435-440. [20] B. Negrevergne, A. Termier, J. F. Méhaut, T. Uno. Discovering Closed Frequent Itemsets on Multicore: Parallelizing Computations and Optimizing Memory Accesses. HPCS’10 IEEE: (2010), 521–528. [21] H. Li, N. Zhang. Mining maximal frequent itemsets on graphics processors. Fuzzy Systems and Knowledge Discovery (FSKD) 2010 Seventh International Conference on, vol. 3, (2010), 1461-1464. [22] G. Teodoro, N. Mariano, J. W. Meira, R. Ferreira. Tree Projection- Based Frequent Itemset Mining on Multicore CPUs and GPUs. 2010 22nd Int Symposium on Computer Architecture and High Performance Computing, Petropolis, (2010), 47-54. [23] K. M. Yu, S. H. Wu. An Efficient Load Balancing Multi-core Frequent Patterns Mining Algorithm. 10th Int Conf on Trust, Security and Privacy in Computing and Communications, Changsha, (2011), 1408-1412. [24] F. Zhang, Y. Zhang, J. Bakos. Gpapriori: Gpu-accelerated Frequent Itemset Mining. Proc. of the 2011 IEEE International Conference on Cluster Computing, (2011), 590-594. [25] C. Silvestri, S. Orlando. gpuDCI: Exploiting GPUs in Frequent Itemset Mining. Parallel Distributed and Network-Based Processing (PDP) 2012 20th Euromicro International Conference on, (2012), 416-425. [26] B. Missaoui, K. Arour, Y. Slimani. Parallel Binary Approach for Frequent Itemsets Mining. International Journal of Computer and Communication Engineering, (2013), 230. [27] D. Nguyen, B. Vo, B. Le. Efficient strategies for parallel mining class association rules. Expert Syst. Appl. 41(10): (2014), 4716-4729. [28] F. Wang, B. Yuan. Parallel Frequent Pattern Mining without Candidate Generation on GPUs. Data Mining Workshop (ICDMW) 2014 IEEE International Conference on, (2014), 1046-1052. [29] B. Negrevergne, A. Termier, M. C. Rousset, J. F. Méhaut. ParaMiner: A Generic Pattern Mining Algorithm for Multi-Core Architectures. Data Min Knowl Disc 28(3): (2014), 593–633. [30] Ö. M. Soysal, E. Gupta, H. Donepudi. A sparse memory allocation data structure for sequential and parallel association rule mining. The Journal of Supercomputing, (2015). [31] K. M. Yu, S. H. Liu, L. W. Zhou, S. H. Wu. Apriori-based High Efficiency Load Balancing Parallel Data Mining Algorithms on Multi- core Architectures. Int Journal of Grid and HPC, 7, (2015), 77. [32] H. Jiang, H. Meng. A Parallel FP-Growth Algorithm Based on GPU. e- Business Engineering (ICEBE) IEEE 14th Int Conf on, (2017), 97-102. [33] K. W. Chon, S. H. Hwang, M. S. Kim. Gminer: A fast gpu-based frequent itemset mining method for large-scale data. Information Sciences, 439-440, (2018), 19 – 38. [34] Y. Wang, T. Xu, S. Xue, Y. Shen. D2P-Apriori: A deep parallel frequent itemset mining algorithm with dynamic queue. 10th Int Conf on Advanced Computational Intelligence, Xiamen, (2018), 649-654. [35] H. Phan. An Efficient Mining Algorithm of Closed Frequent Itemsets on Multi-core Processor. In: Li J., Wang S., Qin S., Li X., Wang S. (eds) Adv. Data Mining and Applications. ADMA 2019: (2019), 107-118. [36] Y. C. Wu, M. Y. Yeh, T . W. Kuo. Fast Frequent Pattern Mining without Candidate Generations on GPU by Low Latency Memory Allocation. Big Data (Big Data) IEEE Int Conf on, (2019), 1407-1416. [37] P. Karthik, J. B. Saira. Frequent Item Set Mining of Large Datasets Using CUDA Computing. In: Das K., Bansal J., Deep K., Nagar A., Pathipooranam P., Naidu R. (eds) Soft Computing for Problem Solving. AISC, Springer, 1057, (2020), 739-747. [38] Grand Challenges to Computational Science. Future Generation Computer Systems 5, Special Double Issue, No. 2&3, (1989). [39] San Diego Supercomputer Center (SDSC). Grand Challenge Equations. University of California. San Diego, (1999). [40] I. Foster, C. Kesselman. The Grid 2 – Blueprint for a new computing infrastructure. the 2nd edition, Morgan Kaufmann, (2004). [41] A.S. Tanenbaum. Distributed Operating Systems. Prentice Hall, (1990). Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020) ISBN: 978-604-80-5076-4 301