Trie和PVM并行执行的消息传递方式
发布时间：2021-10-17 20:52
Apriori算法是解决频繁项集挖掘问题的基本算法之一。新一代具有并行处理能力的廉价计算机,更容易建立计算机集群,可以为这些新系统开发更有效并行FIM算法。为了提高效率,笔者研究了Trie和PVM并行执行的消息传递方式,并提出了一种新的消息传递方式与PVM并行计算机集群上推测的消息传递方式,希望能够为相关研究提供借鉴。
【文章来源】：信息与电脑(理论版). 2019,31(19)
【文章页数】：3 页
【部分图文】：
Trie结构示例
毓?Trie；从进程侦听主进程以获取要采取的步骤，因为主进程在对所采取的步骤进行编码的同时遍历自己的候选Trie。该方法如图2中的黄色箭头所示，具有较好的扩展性，但是只能扩展到生成和发送候选对象的特定值。PVM进程也存在问题，比如随机终止或较长的响应时间。（3）版本3。为了克服以前方法中存在的问题，本文提出了一种新的解决方案，并对编码后的Trie编写了一条消息。在这种方法中，从进程不必监听主进程，而是对这条消息进行解码，以构建候选Trie。如图2中的红色箭头所示。图2构建候选Trie为了返回支持计数结果，在完成支持计数之后，从进程创建一个数组并将其发送回去。由于候选程序在每个进程中的尝试完全相同，所以主进程算术上添加这些数组并遍历候选程序的尝试以插入值。2.3Apriori中的加速技术本文实现并评估了几种加速技术。第1个方法是从事务中删除不经常出现的元素，Bodon[5]将此称为过滤事务。由于每个事务及其元素在支持计数中都被访问了很多次，因此从事务中删除不频繁的元素会对Apriori算法的性能产生很大的影响。第2个方法是对于Trie中元素的顺序，可以讨论基于频率的顺序和其他方法（词典、随机等），可以用上升和下降的频率顺序构建Trie。上升的频率顺序有一个优势，即稀有元素更接近根，并在支持计数的早期步骤中从循环中断开。降序频率排序的优点是Trie更小，公共元素更接近根，因此占用的内存更少。第3个方法是对支持度计数的计算。在事务t中k个项目子集的支持计数中，假设在t中第j项后的某个深度d处，需要检查t中第i个位置的项目，使j<i<|t|-k+d+1。这是因为至少需要这么多项来完成Trie
集。3主要结论本文采用进化的发展过程。第一个并行化试验是将候选进程分别发送到从属进程，让它们构建自己的候选进程，同时尝试不同的频率顺序。它被称为Ver-sion1，结果如图3所示。在单处理器顺序算法和并行算法上都采用了基于频率的排序。紧凑并行使用一个Trie存储候选项和频繁项集。数据集由10000个事务组成，随机创建;每个事务最多有100个元素。可以看出，随着从程序数量的增加，版本1无法扩展其性能。相反，递归发送候选Trie的版本2的性能随着从进程数量的增加而增加。图3非递归（称为版本1）和递归（称为版本2）Trie传输选项的比较开发的版本3旨在通过创建由候选Trie的递归定义组成的单个消息来减少PVM系统上的消息传递负载。此版本的性能结果优于前一个版本，如图4所示。图4支持阈值0.45的改进消息传递图4中没有显示较低支持阈值的值，因为版本2不能生成任何可比较的时间。在支持阈值为0.4版本3时，7个从进程的响应时间为59秒，而PVM在版本2时终止。具有支持阈值的相同数据集现在减少到0.4，并在版本3中应用了额外的加速技术。各种加速技术应用于版本3，以二进制搜索为基础，结果如图5所示，要注意Apriori检查对候选人的影响。这大大减少了支持计数之前的搜索空间。在本例中，它还减少了通信时间，因为候选Trie被转移到从属进程，同时遍历始终优于其他支持计数技术。具有下限的反向二进制是最慢的。过滤事务不会改变响应时间，但不应该被误解，因为这种技术的效果依赖于数据分布和所选的支持阈值。图5相同数据集阈值减少4结语本文利用trie数据结构在并行计算机集群上测试了Apriori算法的可伸缩性
【参考文献】：
期刊论文
[1]矩阵压缩Apriori算法分析[J]. 沈艳,张琦智,刘垠,廉春波. 计算机应用. 2017(S2)
[2]基于Apriori和FP-growth的关联挖掘[J]. 肖谦,梅全喜,杨丽娇. 科技展望. 2016(27)
[3]关联规则挖掘Apriori算法的一种改进[J]. 屈鑫乙,王迪,刘滏. 中国市场. 2016(36)
[4]关联规则中几种算法的研究[J]. 顾玮. 办公自动化. 2016(12)
[5]关联规则挖掘综述[J]. 崔妍,包志强. 计算机应用研究. 2016(02)
本文编号：3442398
【文章来源】：信息与电脑(理论版). 2019,31(19)
【文章页数】：3 页
【部分图文】：
Trie结构示例
毓?Trie；从进程侦听主进程以获取要采取的步骤，因为主进程在对所采取的步骤进行编码的同时遍历自己的候选Trie。该方法如图2中的黄色箭头所示，具有较好的扩展性，但是只能扩展到生成和发送候选对象的特定值。PVM进程也存在问题，比如随机终止或较长的响应时间。（3）版本3。为了克服以前方法中存在的问题，本文提出了一种新的解决方案，并对编码后的Trie编写了一条消息。在这种方法中，从进程不必监听主进程，而是对这条消息进行解码，以构建候选Trie。如图2中的红色箭头所示。图2构建候选Trie为了返回支持计数结果，在完成支持计数之后，从进程创建一个数组并将其发送回去。由于候选程序在每个进程中的尝试完全相同，所以主进程算术上添加这些数组并遍历候选程序的尝试以插入值。2.3Apriori中的加速技术本文实现并评估了几种加速技术。第1个方法是从事务中删除不经常出现的元素，Bodon[5]将此称为过滤事务。由于每个事务及其元素在支持计数中都被访问了很多次，因此从事务中删除不频繁的元素会对Apriori算法的性能产生很大的影响。第2个方法是对于Trie中元素的顺序，可以讨论基于频率的顺序和其他方法（词典、随机等），可以用上升和下降的频率顺序构建Trie。上升的频率顺序有一个优势，即稀有元素更接近根，并在支持计数的早期步骤中从循环中断开。降序频率排序的优点是Trie更小，公共元素更接近根，因此占用的内存更少。第3个方法是对支持度计数的计算。在事务t中k个项目子集的支持计数中，假设在t中第j项后的某个深度d处，需要检查t中第i个位置的项目，使j<i<|t|-k+d+1。这是因为至少需要这么多项来完成Trie
集。3主要结论本文采用进化的发展过程。第一个并行化试验是将候选进程分别发送到从属进程，让它们构建自己的候选进程，同时尝试不同的频率顺序。它被称为Ver-sion1，结果如图3所示。在单处理器顺序算法和并行算法上都采用了基于频率的排序。紧凑并行使用一个Trie存储候选项和频繁项集。数据集由10000个事务组成，随机创建;每个事务最多有100个元素。可以看出，随着从程序数量的增加，版本1无法扩展其性能。相反，递归发送候选Trie的版本2的性能随着从进程数量的增加而增加。图3非递归（称为版本1）和递归（称为版本2）Trie传输选项的比较开发的版本3旨在通过创建由候选Trie的递归定义组成的单个消息来减少PVM系统上的消息传递负载。此版本的性能结果优于前一个版本，如图4所示。图4支持阈值0.45的改进消息传递图4中没有显示较低支持阈值的值，因为版本2不能生成任何可比较的时间。在支持阈值为0.4版本3时，7个从进程的响应时间为59秒，而PVM在版本2时终止。具有支持阈值的相同数据集现在减少到0.4，并在版本3中应用了额外的加速技术。各种加速技术应用于版本3，以二进制搜索为基础，结果如图5所示，要注意Apriori检查对候选人的影响。这大大减少了支持计数之前的搜索空间。在本例中，它还减少了通信时间，因为候选Trie被转移到从属进程，同时遍历始终优于其他支持计数技术。具有下限的反向二进制是最慢的。过滤事务不会改变响应时间，但不应该被误解，因为这种技术的效果依赖于数据分布和所选的支持阈值。图5相同数据集阈值减少4结语本文利用trie数据结构在并行计算机集群上测试了Apriori算法的可伸缩性
【参考文献】：
期刊论文
[1]矩阵压缩Apriori算法分析[J]. 沈艳,张琦智,刘垠,廉春波. 计算机应用. 2017(S2)
[2]基于Apriori和FP-growth的关联挖掘[J]. 肖谦,梅全喜,杨丽娇. 科技展望. 2016(27)
[3]关联规则挖掘Apriori算法的一种改进[J]. 屈鑫乙,王迪,刘滏. 中国市场. 2016(36)
[4]关联规则中几种算法的研究[J]. 顾玮. 办公自动化. 2016(12)
[5]关联规则挖掘综述[J]. 崔妍,包志强. 计算机应用研究. 2016(02)
本文编号：3442398
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3442398.html
