函数依赖发现算法的通用并行策略研究

目录

声明

摘要

第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问题的形式化

3．3 BL代数系统与FD-Combine推导算法

3．3．1 BL代数系统定义与性质

3．3．2基础项及基础项计算规则

3．3．3 FD-Combine推导算法

3．4 FD-Combine推导算法的进一步探索

3．4．2 FD-Combine的算法实现方式和复杂度分析

3．5本章小结

第4章数据集在各个计算节点上的分割问题

4．1 问题的背景分析与目标

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未来展望

参考文献

致谢

在读期间发表的学术论文与取得的研究成果