面向复杂距离度量的MapReduce相似性连接技术研究

发布时间：2017-10-19 19:09

  本文关键词：面向复杂距离度量的MapReduce相似性连接技术研究

  更多相关文章： 相似性连接 复杂距离 MapReduce 数据划分 负载均衡

【摘要】：相似性连接操作在网页副本检测、实体识别、数据清洗和图像检索等领域都有很广泛的应用,随着数据规模的不断增大,利用分布式并行框架处理大规模数据的相似性连接已经吸引了越来越多的科研工作者和商业公司的关注。而EMD(Earth Mover's Distance)和Bregman Divergence等复杂距离度量因较强的鲁棒性及相似性度量结果更符合人类视觉等原因,被广泛应用于度量图像及语音等类型数据的相似性,但现有的关于上述复杂距离度量的相似性连接算法多只适用于集中式环境,无法满足大规模数据的处理需求,因此本文研究了利用MapReduce分布式并行处理框架解决面向复杂距离度量的大规模数据相似性连接的问题。首先基于块嵌套循环思想,使用随机均匀的数据划分方式,提出了MapReduce框架下基本的EMD-BNLJ算法和Breg-BNLJ算法,其中EMD-BNLJ算法可解决面向EMD距离的大规模数据Top-k相似性自连接问题,Breg-BNLJ算法可解决面向Bregman Divergence距离的大规模数据相似性连接问题。其次根据EMD距离对偶问题的特性,将原始数据映射到一维空间,之后设计了基于一维空间内数据位置局部性的数据划分策略,减少了不必要的通信开销,并通过采样估算计算代价设计了基于Quantile的负载均衡策略,保证了算法的负载均衡性,进而提出了面向EMD距离的大规模数据Top-k EMD-DLPJ目似性自连接算法。在真实数据集上进行的丰富实验证实,EMD-DLPJ算法的通信开销最多为EMD-BNLJ算法的1/5,而执行效率最高为EMD-BNLJ算法的6.9倍。最后利用Bregman Divergence距离计算的特点,设计了以VA-File分割原始数据空间的数据划分策略,可提前过滤掉不必要的距离计算,减少通信开销,进一步通过采样估算计算代价设计了基于前缀的数据分组策略,保证了算法的负载均衡性,进而提出了面向Bregman Divergence距离的大规模数据Breg-VAFJ相似性连接算法。在多种真实数据集上的大量实验证实,Breg-VAFJ算法的通信开销最多为Breg-BNLJ算法的1/3,而执行效率最高为Breg-BNLJ算法的4.8倍。本文研究了面向复杂距离度量EMD和Bregman Divergence的基于MapReduce的相似性连接技术,根据各距离的计算特性设计了可精确控制的针对原始数据集的数据划分方法,取代了基本的随机均匀划分方法,减少了MapReduce作业的通信开销。同时通过采样估算计算代价,设计了对应的负载均衡策略,有效地保证了MapReduce作业的负载均衡性。最终在多个真实数据集上的大量实验证实了本文提出的算法的高效性。
【关键词】：相似性连接 复杂距离 MapReduce 数据划分 负载均衡
【学位授予单位】：东北大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP338.6;TP391.41
【目录】：

• 摘要5-7
• Abstract7-11
• 第1章 引言11-19
• 1.1 研究背景11-14
• 1.1.1 相似性连接11-12
• 1.1.2 基于复杂距离的相似性度量12-13
• 1.1.3 大规模数据的分布式并行处理13-14
• 1.2 问题提出14-16
• 1.2.1 基于复杂距离度量的大规模数据相似性连接的特点14-15
• 1.2.2 研究现状15-16
• 1.3 本文贡献16-17
• 1.4 组织结构17-19
• 第2章 相关工作19-33
• 2.1 复杂距离相似性度量19-21
• 2.1.1 EMD距离19-20
• 2.1.2 Bregman Divergence度量20-21
• 2.2 索引与数据划分21-25
• 2.2.1 面向EMD距离的索引22-23
• 2.2.2 面向Bregman Divergence的索引23-25
• 2.3 MapReduce计算框架与Hadoop系统25-27
• 2.4 MapReduce计算框架下的相似性连接技术27-31
• 2.4.1 利用二维空间网格划分数据27-28
• 2.4.2 利用Voronoi图划分数据28-29
• 2.4.3 利用Z-value空间填充曲线划分数据29-31
• 2.5 本章小结31-33
• 第3章 基于EMD距离的Top-k相似性连接算法33-55
• 3.1 协同过滤框架33-36
• 3.1.1 B~+树过滤34-35
• 3.1.2 LB_(IM)过滤35-36
• 3.1.3 三角不等性过滤36
• 3.2 基于块嵌套循环进行数据划分的基本算法36-42
• 3.2.1 抽样确定Top-k相似性连接初始阈值38-39
• 3.2.2 查找局部S_(Topk)39-42
• 3.3 基于数据局部性进行数据划分的改进算法42-49
• 3.3.1 抽样确定近似分位数和T值44-45
• 3.3.2 利用数据局部性查找局部S_(Topk)45-49
• 3.4 实验结果及分析49-53
• 3.5 本章小结53-55
• 第4章 基于Bregman Divergence度量的相似性连接算法55-77
• 4.1 基于块嵌套循环进行数据划分的基本算法55-57
• 4.2 基于VA-File进行数据划分的改进算法57-68
• 4.2.1 构建VA-File索引58-59
• 4.2.2 制定负载均衡策略59-66
• 4.2.3 实现相似性连接66-68
• 4.3 实验结果及分析68-74
• 4.4 本章小结74-77
• 第5章 总结与展望77-79
• 5.1 本文的主要贡献与结论77-78
• 5.2 未来工作78-79
• 参考文献79-83
• 致谢83-85
• 攻读硕士学位期间的论文项目情况85

【相似文献】

中国期刊全文数据库 前4条

1 郝建柏;陈贤富;黄双福;杨俊;;一种基于模糊近邻标签传递的半监督分类算法[J];微电子学与计算机;2010年02期

2 余海洋;林琛;陈珂;江弋;邹权;;Pass-Join-K:多分段匹配的相似性连接算法[J];计算机科学与探索;2013年10期

3 刘雪莉;王宏志;李建中;高宏;;实体数据库中多相似连接顺序选择策略[J];计算机科学与探索;2012年10期

4 ;[J];;年期

中国硕士学位论文全文数据库 前4条

1 雷斌;面向复杂距离度量的MapReduce相似性连接技术研究[D];东北大学;2014年

2 刘雪莉;基于实体的相似性连接操作的研究[D];哈尔滨工业大学;2012年

3 周健雯;异质网络上的自相似性连接算法研究与实现[D];复旦大学;2013年

4 徐媛媛;基于MapReduce的相似性连接研究[D];宁波大学;2014年

，

本文编号：1062810