基于BIDE的多核并行闭合序列模式挖掘

doi:10.3969/j.issn.1000-3428.2012.12.016

计算机工程 ›› 2012, Vol. 38 ›› Issue (12): 55-58. doi: 10.3969/j.issn.1000-3428.2012.12.016

基于BIDE的多核并行闭合序列模式挖掘

俞东进 ¹，郑苏杭 ¹，李万清¹，吴为 ²

(1. 杭州电子科技大学计算机学院，杭州 310018；2. 浙江省网络系统及信息安全重点实验室，杭州 310006)

收稿日期:2011-07-18 出版日期:2012-06-20 发布日期:2012-06-20
作者简介:俞东进(1969－)，男，教授级高级工程师、博士、CCF会员，主研方向：数据挖掘，数据库技术；郑苏杭，硕士研究生；李万清，讲师；吴为，高级工程师
基金资助:
浙江省重大科技计划基金资助项目(2008C11099-1)；浙江省网络系统及信息安全重点实验室基金资助项目

Multi-core Parallel Closed Sequential Patterns Mining Based on BIDE

YU Dong-jin¹, ZHENG Su-hang ¹, LI Wan-qing ¹, WU Wei ²

(1. School of Computer, Hangzhou Dianzi University, Hangzhou 310018, China; 2. Zhejiang Key Laboratory of Network System and Information Security, Hangzhou 310006, China)

Received:2011-07-18 Online:2012-06-20 Published:2012-06-20

摘要/Abstract

摘要： 基于经典的BIDE算法，提出一种多核并行闭合序列模式挖掘算法——MT_BIDE。该算法在频繁序列扩展判断前进行剪枝，在扩展过程中动态调整频繁序列及其伪投影数据集，平衡不同线程间挖掘闭合序列模式的计算量差异。实验结果表明，该算法具有较高的运行效率和加速比。

关键词: 多核, 闭合序列, BIDE算法, 序列模式挖掘, 伪投影数据集

Abstract: Based on the classical BIDE algorithm, this paper presents a multi-core parallel closed sequential patterns mining parallel algorithm, MT_BIDE. Through pruning before frequent sequential patterns expansion and reassigning them and their pseudo-projected datasets during the expansion process, MT_BIDE achieves the workload balancing which is always influenced by different calculation of different threads mining closed sequential patterns. Experimental results show that the algorithm has higher operating efficiency and speedup ratio.

Key words: multi-core, closed sequence, BIDE algorithm, sequential pattern mining, pseudo-projected dataset

中图分类号:

TP311

俞东进, 郑苏杭, 李万清, 吴为. 基于BIDE的多核并行闭合序列模式挖掘[J]. 计算机工程, 2012, 38(12): 55-58.

SHU Dong-Jin, ZHENG Su-Hang, LI Mo-Qing, TUN Wei. Multi-core Parallel Closed Sequential Patterns Mining Based on BIDE[J]. Computer Engineering, 2012, 38(12): 55-58.

http://www.ecice06.com/CN/Y2012/V38/I12/55

参考文献

[1] 朱扬勇, 熊赟. DNA序列数据挖掘技术[J]. 软件学报, 2007, 18(11): 2766-2781.
[2] Agrawal R, Srikant R. Mining Sequential Patterns[C]//Proc. of ICDE’95. [S. l.]: IEEE Computer Society, 1995.
[3] Agrawal R, Srikant R. Mining Quantitative Association Rules in Large Relational Tables[C]//Proc. of the ACM SIGMOD Conference Management of Data. Montreal, Canada: [s. n.], 1996.
[4] Agrawal R, Srikant R. Mining Sequential Patterns: Generalizations and Performance Improvements[C]//Proc. of EDBT’96. Avignon, France: [s. n.], 1996.
[5] Zaki M J. SPADE: An Efficient Algorithm for Mining Frequent Sequences[J]. Machine Learning, 2001, 42(1): 31-60.
[6] Han Jiawei, Pei Jian, Mortazavi-Asl B. FreeSpan: Frequent Pa- ttern-projected Sequential Pattern Mining[C]//Proc. of KDD’00. Boston, USA: [s. n.], 2000.
[7] Pei Jian, Han Jiawei, Mortazavi-Asl B, et al. Mining Sequential Patterns by Patten-growth: The Prefix Span Approach[J]. IEEE Trans. on Knowledge and Data Engineering, 2004, 16(11): 1424-1440.
[8] Ayres J, Gehrkeetal J. Sequential Pattern Mining Using a Bitmap Representation[C]//Proc. of the 8th ACM SIGKDD International Conf. on Knowledge Discovery and Data Mining. Edmonton, Alberta, Canada: [s. n.], 2002.
[9] Afshar R. Mining Frequent Max and Closed Sequential Pa- tterns[D]. Burnaby, Canada: School of Computing Science, Simon Fraser University, 2002.
[10] Yan Xifeng, Han Jiawei, Afshar R. CloSPan: Mining Closed Sequential Patterns in Large Datasets[C]//Proc. of SDM’03. San Fransisco, USA: [s. n.], 2003.
[11] Wang Jianyong, Han Jiawei. BIDE: Efficient Mining of Frequent Closed Sequences[C]//Proc. of ICDE’04. Boston, USA: [s. n.], 2004.
[12] Zhu Tian, Bai Sixue. A Parallel Mining Algorithm for Closed Sequential Patterns[C]//Proc. of AINAW’07. Niagara Falls, Canada: [s. n.], 2007.
[13] Cong Shengnan, Han Jiawei, Padua D. Parallel Mining of Closed Sequential Patterns[C]//Proc. of KDD’05. [S. l.]: ACM Press, 2005.
[14] Zhu Tian, Bai Sixue. A Parallel Mining Algorithm for Closed Sequential Patterns[C]//Proc. of the 21st International Conf. on Advanced Information Networking and Applications Workshops. [S. l.]: IEEE Computer Society, 2007.
[15] Tatikonda S, Parthasarathy S. Mining Tree-structured Data on Multicore Systems[C]//Proc. of VLDB’09. Lyon, France: [s. n.], 2009.
[16] Negrevergne B, Termier A, Me?haut J, et al. Discovering Closed Frequent Itemsets on Multicore: Parallelizing Computations and Optimizing Memory Accesses[C]//Proc. of HPCS’10, Toronto, USA: [s. n.], 2010.
[17] 王鹏, 孟丹, 詹剑锋, 等. 数据密集型计算编程模型研究进展[J]. 计算机研究与发展, 2010, 47(11): 1993-2002.

选择文件类型/文献管理软件名称

选择包含的内容

基于BIDE的多核并行闭合序列模式挖掘

Multi-core Parallel Closed Sequential Patterns Mining Based on BIDE

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	高秀武, 姜军, 白书敬, 黄亮明. 一种加速访存地址计算的编译优化[J]. 计算机工程, 2023, 49(1): 173-180.
[2]	周雍浩, 徐金龙, 李斌, 钱宏, 聂凯. 面向神威高性能多核处理器的并行编译优化方法[J]. 计算机工程, 2022, 48(9): 130-138.
[3]	吴军, 欧阳艾嘉, 张琳. 面向对比序列模式发现的独立精确置换检验算法[J]. 计算机工程, 2021, 47(8): 45-53,61.
[4]	梁秋玲, 张向利, 张红梅, 闫坤. 基于多核处理器的关联任务并行感知调度算法[J]. 计算机工程, 2021, 47(7): 212-217.
[5]	焦童, 陈玲玲, 安鑫, 李建华. 基于重用信息的非易失性缓存动态旁路策略[J]. 计算机工程, 2021, 47(4): 158-165.
[6]	王欣夷, 王耀彬, 李凌, 杨洋, 卜得庆, 刘志勤. HPEC中子程序级推测并行性分析[J]. 计算机工程, 2020, 46(8): 210-215,222.
[7]	何俊, 张彩庆, 李小珍, 张德海. 面向深度学习的多模态融合技术研究综述[J]. 计算机工程, 2020, 46(5): 1-11.
[8]	王忠民, 刘戈, 宋辉. 基于多核学习特征融合的语音情感识别方法[J]. 计算机工程, 2019, 45(8): 248-254.
[9]	冯国富, 舒玉娟, 陈明, 董立夫. 基于big.LITTLE架构的多目标功耗自适应控制方法[J]. 计算机工程, 2019, 45(7): 60-65.
[10]	屠雪真,屠要峰,陈小强. 一种优化的Key-Value型NoSQL系统[J]. 计算机工程, 2019, 45(6): 52-59.
[11]	任胜兵, 谢如良. 基于AdaBoost的弹性网型正则化多核学习算法[J]. 计算机工程, 2019, 45(10): 189-195.
[12]	邹国良,张石明,陈长吉,王振华. 基于改进最小距离法的图像匹配并行算法设计[J]. 计算机工程, 2018, 44(9): 218-223.
[13]	王俊昌,王振,付雄. 基于无锁数据结构的FIFO队列算法[J]. 计算机工程, 2018, 44(8): 315-320.
[14]	贺爱香,顾乃杰,苏俊杰. 基于多核ARM体系结构的基础函数优化方法[J]. 计算机工程, 2018, 44(5): 47-52,59.
[15]	赵瑞姣,朱怡安,李联. 基于异构多核系统的混合关键任务调度算法[J]. 计算机工程, 2018, 44(2): 51-55.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于BIDE的多核并行闭合序列模式挖掘

Multi-core Parallel Closed Sequential Patterns Mining Based on BIDE

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价