基于哈希表与十字链表存储的Apriori算法优化  

OPTIMIZATION OF APRIORI ALGORITHM BASED ON HASH TABLE AND CROSS-LINKED LIST STORAGE

作　　者：吴昊[1,2,3] 刘钊[1,2,3] 顾进广 Wu Hao;Liu Zhao;Gu Jinguang(School of Computer Science and Technology,Wuhan University of Science and Technology,Wuhan 430065,Hubei,China;Big Data Science and Engineering Research Institute,Wuhan University of Science and Technology,Wuhan 430065,Hubei,China;Hubei Province Key Laboratory of Intelligent Information Processing and Real-Time Industrial,Wuhan 430065,Hubei,China)

机构地区：[1]武汉科技大学计算机科学与技术学院,湖北武汉430065 [2]武汉科技大学大数据科学与工程研究院,湖北武汉430065 [3]湖北省智能信息处理与实时工业系统重点实验室,湖北武汉430065

出　　处：《计算机应用与软件》2022年第7期247-255,共9页Computer Applications and Software

基　　金：国家自然科学基金项目(61673304);国家社科基金重大计划项目(11&ZD189)。

摘　　要：Apriori算法在数据挖掘过程中需要多次扫描数据库,会造成I/O上有较大时间开销和负载,影响算法的运行速度,同时在计算频繁项集的过程中,需要进行大量迭代搜索与计算,算法的时间复杂度和空间复杂度较高。基于此,提出一种基于哈希表与十字链表存储的优化算法HTACL-Apriori。通过理论分析和数据进行实验对比,验证了优化后的HTACL-Apriori算法相对于传统的Apriori算法在时间效率和空间效率方面有明显的提高,达到了预期效果。The Apriori algorithm needs to scan the database multiple times during the data mining process, which will cause a large time overhead and load on the I/O and affect the speed of the algorithm. In the process of computing frequent itemsets, it needs to perform a large number of iterative searches and calculations, and the time complexity and space complexity of the algorithm are high. Therefore, this paper proposes an optimized algorithm HTACL-Apriori based on Hash table and cross-linked list storage. Through the theoretical analysis and experimental data, it is verified that compared with the traditional Apriorialgorithm, HTACL-Apriori significantly improves the time efficiency and space efficiency, and has achieved the expected results.

关 键 词：时间复杂度 空间复杂度 哈希表 十字链表 布尔矩阵 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]