函数依赖发现算法的通用并行策略研究
发布时间：2021-04-25 13:15
函数依赖是重要的元数据,用于描述数据集中列之间的关系,可以被用于很多任务中,例如范式结构标准化,数据清洗等。很多单机和并行函数依赖发现算法已经被提出。之前的单机算法在数据集较小且单机存储的时候很高效,但是缺乏并行能力;另一方面,现存的并行算法存在很大的通信开销,导致其表现不佳。为了解决这个问题,本文做了如下三方面的工作:首先是提出FD-Combine算法解决了“如何推导”的问题。现存并行算法最大问题是通信开销,我们尝试通过数据并行模式的并行来避免大量的通信开销,而数据并行模式的并行的首要问题就是”如何将部分数据上成立的函数依赖推导得到全体数据的函数依赖”,即“如何推导”的问题。为此,我们构建了BL代数系统和基础项表达,形式化了函数依赖、非函数依赖、部分函数依赖的性质与运算关系。在BL代数系统内,我们提出FD-Combine算法,在每部分数据集即数据块满足一定条件时,可以将部分函数依赖推导得到全体数据上的函数依赖。我们对比FD-Combine算法与之前非函数依赖的推导算法,得到进一步理解,并给出FD-Combine算法的不同实现方式和相应的时间复杂度。然后,改造并选择了仿射平面区组设计算...
【文章来源】：中国科学技术大学安徽省 211工程院校 985工程院校
【文章页数】：69 页
【学位级别】：硕士
【文章目录】：
摘要
abstract
第1章 绪论
1.1 研究背景
1.2 国内外研究现状
1.2.1 国外研究现状
1.2.2 国内研究现状
1.2.3 发展动态分析
1.3 本文主要工作
1.4 本文组织结构
第2章 函数依赖发现算法概述
2.1 定义
2.2 三类发现算法
2.2.1 单机算法过去的实验对比
2.2.2 模式驱动类算法
2.2.3 数据驱动类算法
2.2.4 混合类算法
2.3 发现算法中的四种技术
2.3.1 验证技术
2.3.2 搜索剪枝技术
2.3.3 推导技术
2.3.4 重复检测技术
2.3.5 分布式环境下四种技术
2.4 分布式环境下的发现算法
2.4.1 三种类型的通信开销
2.4.2 几种并行算法的设计
第3章 部分数据函数依赖到全体数据函数依赖的推导
3.1 问题的背景分析
3.1.1 分布式环境下的通信开销分析
3.1.2 并行模式的分析
3.2 问题的形式化
L代数系统与FD-Combine推导算法"> 3.3 BL代数系统与FD-Combine推导算法
L代数系统定义与性质"> 3.3.1 BL代数系统定义与性质
3.3.2 基础项及基础项计算规则
3.3.3 FD-Combine推导算法
3.4 FD-Combine推导算法的进一步探索
3.4.1 FD-Combine算法与其他推导算法的关系
3.4.2 FD-Combine的算法实现方式和复杂度分析
3.5 本章小结
第4章 数据集在各个计算节点上的分割问题
4.1 问题的背景分析与目标
4.1.1 FD-Combine推导条件的满足
4.1.2 分割算法的高效性
4.1.3 分割结果的质量
4.2 问题的转化及形式化表达
4.3 区组设计与评估指标设计
4.3.1 区组设计与条件放松
4.3.2 评价指标定义与性质
4.4 仿射平面区组设计算法设计与分析
4.4.1 仿射平面区组设计算法流程
4.4.2 算法的时间复杂度分析与结果分析
4.5 本章小结
第5章 函数依赖发现算法的通用并行策略与实验
5.1 数据并行模式的通用并行策略
5.1.1 通用并行策略的介绍与例子
5.1.2 策略的复杂度分析和加速比
5.2 通用并行策略的实验
5.2.1 实验设置
5.2.2 小数据集上的实验
5.2.3 大数据集上的实验
5.3 本章小结
第6章 总结与展望
6.1 工作总结
6.2 未来展望
参考文献
致谢
在读期间发表的学术论文与取得的研究成果
【参考文献】：
期刊论文
[1]分布式大数据多函数依赖冲突检测[J]. 李卫榜,李战怀,姜涛. 计算机学报. 2017(01)
[2]关系数据中函数依赖检测方法[J]. 钟评,李战怀,陈群. 计算机学报. 2017(01)
[3]基于函数依赖与条件约束的数据修复方法[J]. 金澈清,刘辉平,周傲英. 软件学报. 2016(07)
[4]基于可能世界模型的关系数据不一致性的修复[J]. 徐耀丽,李战怀,陈群,钟评. 软件学报. 2016(07)
[5]分布式大数据不一致性检测[J]. 李卫榜,李战怀,陈群,杨婧颖,姜涛. 软件学报. 2016(08)
[6]分布式大数据函数依赖发现[J]. 李卫榜,李战怀,陈群,姜涛,刘海龙,潘巍. 计算机研究与发展. 2015(02)
[7]基于函数依赖的结构匹配方法[J]. 李国徽,杜小坤,胡方晓,杨兵,唐向红. 软件学报. 2009(10)
[8]时态函数依赖多值依赖混合集的成员籍问题研究[J]. 郝忠孝,李艳娟. 计算机研究与发展. 2006(07)
[9]具有多时间粒度的时态数据库初等关键字、简单范式分解问题研究[J]. 郝忠孝,李艳娟. 计算机研究与发展. 2005(09)
[10]函数依赖和规范化在关系和XML间的传播[J]. 谈子敬,施伯乐. 软件学报. 2005(04)
本文编号：3159451
【文章来源】：中国科学技术大学安徽省 211工程院校 985工程院校
【文章页数】：69 页
【学位级别】：硕士
【文章目录】：
摘要
abstract
第1章 绪论
1.1 研究背景
1.2 国内外研究现状
1.2.1 国外研究现状
1.2.2 国内研究现状
1.2.3 发展动态分析
1.3 本文主要工作
1.4 本文组织结构
第2章 函数依赖发现算法概述
2.1 定义
2.2 三类发现算法
2.2.1 单机算法过去的实验对比
2.2.2 模式驱动类算法
2.2.3 数据驱动类算法
2.2.4 混合类算法
2.3 发现算法中的四种技术
2.3.1 验证技术
2.3.2 搜索剪枝技术
2.3.3 推导技术
2.3.4 重复检测技术
2.3.5 分布式环境下四种技术
2.4 分布式环境下的发现算法
2.4.1 三种类型的通信开销
2.4.2 几种并行算法的设计
第3章 部分数据函数依赖到全体数据函数依赖的推导
3.1 问题的背景分析
3.1.1 分布式环境下的通信开销分析
3.1.2 并行模式的分析
3.2 问题的形式化
L代数系统与FD-Combine推导算法"> 3.3 BL代数系统与FD-Combine推导算法
L代数系统定义与性质"> 3.3.1 BL代数系统定义与性质
3.3.2 基础项及基础项计算规则
3.3.3 FD-Combine推导算法
3.4 FD-Combine推导算法的进一步探索
3.4.1 FD-Combine算法与其他推导算法的关系
3.4.2 FD-Combine的算法实现方式和复杂度分析
3.5 本章小结
第4章 数据集在各个计算节点上的分割问题
4.1 问题的背景分析与目标
4.1.1 FD-Combine推导条件的满足
4.1.2 分割算法的高效性
4.1.3 分割结果的质量
4.2 问题的转化及形式化表达
4.3 区组设计与评估指标设计
4.3.1 区组设计与条件放松
4.3.2 评价指标定义与性质
4.4 仿射平面区组设计算法设计与分析
4.4.1 仿射平面区组设计算法流程
4.4.2 算法的时间复杂度分析与结果分析
4.5 本章小结
第5章 函数依赖发现算法的通用并行策略与实验
5.1 数据并行模式的通用并行策略
5.1.1 通用并行策略的介绍与例子
5.1.2 策略的复杂度分析和加速比
5.2 通用并行策略的实验
5.2.1 实验设置
5.2.2 小数据集上的实验
5.2.3 大数据集上的实验
5.3 本章小结
第6章 总结与展望
6.1 工作总结
6.2 未来展望
参考文献
致谢
在读期间发表的学术论文与取得的研究成果
【参考文献】：
期刊论文
[1]分布式大数据多函数依赖冲突检测[J]. 李卫榜,李战怀,姜涛. 计算机学报. 2017(01)
[2]关系数据中函数依赖检测方法[J]. 钟评,李战怀,陈群. 计算机学报. 2017(01)
[3]基于函数依赖与条件约束的数据修复方法[J]. 金澈清,刘辉平,周傲英. 软件学报. 2016(07)
[4]基于可能世界模型的关系数据不一致性的修复[J]. 徐耀丽,李战怀,陈群,钟评. 软件学报. 2016(07)
[5]分布式大数据不一致性检测[J]. 李卫榜,李战怀,陈群,杨婧颖,姜涛. 软件学报. 2016(08)
[6]分布式大数据函数依赖发现[J]. 李卫榜,李战怀,陈群,姜涛,刘海龙,潘巍. 计算机研究与发展. 2015(02)
[7]基于函数依赖的结构匹配方法[J]. 李国徽,杜小坤,胡方晓,杨兵,唐向红. 软件学报. 2009(10)
[8]时态函数依赖多值依赖混合集的成员籍问题研究[J]. 郝忠孝,李艳娟. 计算机研究与发展. 2006(07)
[9]具有多时间粒度的时态数据库初等关键字、简单范式分解问题研究[J]. 郝忠孝,李艳娟. 计算机研究与发展. 2005(09)
[10]函数依赖和规范化在关系和XML间的传播[J]. 谈子敬,施伯乐. 软件学报. 2005(04)
本文编号：3159451
本文链接：https://www.wllwen.com/shoufeilunwen/xixikjs/3159451.html
