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

《面向复杂距离度量的mapreduce相似性连接技术研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC学位论文面向复杂距离度量的MapReduce相似性连接技术研究作者姓名：指导教师：申请学位级别：学科专业名称：论文提交日期：学位授予日期：评阅人：雷斌王义教授于戈教授东北大学信息科学与工程学院硕士学科类别：工学计算机应用技术2014年6月论文答辩日期：2014年6月2014年7月答辩委员会主席：申德荣夏秀峰谷峪东北大学2014年6月万方数据AThesisinComputerApplicationTechnologyResearchonComplexDistanceMeasurebasedMapReduceSimilarityJoinTechniquesbyLeiBin

2、Supervisor：ProfessorWangYiProfessorYuGeNortheasternUniversityJune2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢二亡己思。学位论文作者签名：曙认日期：2川中．石．2缈学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交

3、论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口学位论文作者签名：一年半口【馏狄签字日期：如f伞．易．以两年口导师签名：签字目期：Ⅱl≮、6、)V万方数据东北大学硕士学位论文摘要面向复杂距离度量的MapReduce相似性连接技术研究摘要相似性连接操作在网页副本检测、实体识别、数据清洗和图像检索等领域都有很广泛的应用，随着数据规模的不断增大，利用分布式并行框架处理大规模数据的相似性连接已经吸引了越来越多的科研工作者和商业公司的关注。而EMD(EarthMover’SDi

4、stance)和BregmanDivergence等复杂距离度量因较强的鲁棒性及相似性度量结果更符合人类视觉等原因，被广泛应用于度量图像及语音等类型数据的相似性，但现有的关于上述复杂距离度量的相似性连接算法多只适用于集中式环境，无法满足大规模数据的处理需求，因此本文研究了利用MapReduce分布式并行处理框架解决面向复杂距离度量的大规模数据相似性连接的问题。首先基于块嵌套循环思想，使用随机均匀的数据划分方式，提出MapReduce框架下基本的EMD．BNLJ算法和Breg．BNLJ算法，其中EMD．BNLJ算法可解决面向EMD距离的大规模数据Top．足相似性自连接问题，Breg—BNL

5、J算法可解决面INBregmanDivergence距离的大规模数据相似性连接问题。其次根据EMD距离对偶问题的特性，将原始数据映射到一维空间，之后设计了基于一维空间内数据位置局部性的数据划分策略，减少了不必要的通信开销，并通过采样估算计算代价设计了基于Quantile的负载均衡策略，保证了算法的负载均衡性，进而提出了面向EMDIgg离的大规模数据Top．kEMD．DLPJ相似性自连接算法。在真实数据集上进行的丰富实验证实，EMD—DLPJ算法的通信开销最多为EMD．BNLJ算法的l／5，而执行效率最高为EMD．BNLJ算法的6．9倍。最后利用BregmanDivergence距_离计算

6、的特点，设计了以VA．File分割原始数据空间的数据划分策略，可提前过滤掉不必要的距离计算，减少通信开销，进一步通过采样估算计算代价设计了基于前缀的数据分组策略，保证了算法的负载均衡性，进而提出了面INBregmanDivergence距离的大规模数据Breg．VAFJ相似性连接算法。在多种真实数据集上的大量实验证实，Breg．VAFJ算法的通信开销最多为Breg．BNLJ算法的l／3，而执行效率最高为Breg．BNLJ算法的4．8倍。本文研究了面向复杂距离度量EMD矛llBregmanDivergence的基于MapReduce的相似性连接技术，根据各距离的计算特性设计了可精确控制的针

7、对原始数据集的数据划分方法，取代了基本的随机均匀划分方法，减少MapReduce作业的通信开销。同时通过采样估算计算代价，设计了对应的负载均衡策略，有效地保J,iETMapReduce作业的负载均万方数据东北大学硕士学位论文摘要衡性。最终在多个真实数据集上的大量实验证实了本文提出的算法的高效性。关键词：相似性连接；复杂距离；MapReduce；数据划分；负载均衡万方数据东北大学硕士学位论文AbstractResearchonComp