Spark平台下的分布式函数依赖发现算法

作者：朱星宇; 蔡志成; 刘段; 徐建; 李小平

来源：小型微型计算机系统, 2020, 41(08): 1569-1575.

• 数据挖掘
• 函数依赖发现
• DepMiner
• 分布式计算
• Spark

函数依赖发现被广泛应用于分布式大数据分析,是数据清洗、质量评估和语义分析的重要手段.已有函数依赖发现算法主要针对集中式数据,不适用于分布在不同节点上的云计算数据.将分布式数据汇集到集中节点非常耗时,而使用传统集中式方法分别处理分布式节点上的数据会导致错误的结果.已经存在的分布式算法存在内存消耗过大的缺点.因此,本文提出一种基于云计算数据处理平台Spark的快速低内存分布式函数依赖发现算法.该算法提出了多个分布式任务分配策略和基于标识符集一致性的最大等价类元素去重策略,在保障正确性前提下,减少了集合交集运算的次数,加快了处理速度.实验结果表明,与传统集中式算法相比,本文提出的分布式算法在本实验环境下使平均执行时间降低了50%左右,去重策略进一步降低了30%左右执行时间.和已有分布式函数依赖发现算法相比,在有些实例上可以节省大约75%的内存.

• 单位
  东南大学; 南京理工大学