【摘 要】
：
在大数据的时代背景下,拼写检查、数据清洗、协同过滤等应用成为研究热点,而相似性连接作为这些众多数据分析的基本操作有着广泛的应用价值,同时Google提出的MapReduce编程模
论文部分内容阅读
在大数据的时代背景下,拼写检查、数据清洗、协同过滤等应用成为研究热点,而相似性连接作为这些众多数据分析的基本操作有着广泛的应用价值,同时Google提出的MapReduce编程模型是处理海量数据最流行的并行计算模型之一,但因其不能较好的支持相似性连接算法,使得在MapReduce上进行相似性连接成为大数据的一个重要可扩展的研究领域。相似性连接中,以n-gram算法为基础的传统算法应用领域非常广泛,增加了错误拼写对相似性度量的影响,但由于该算法生成的标记存在大量冗余,无形中增加了内存空间的消耗以及运行时间。随后针对n-gram算法提出了改进的ED-Join算法,在前缀筛选阶段减少了前缀标记的数量,但却给每个标记分配了位置因素,虽然运行时间显著减少,空间消耗减少却不多。并且以n-gram算法为基础的ED-Join算法并没有在并行架构下实现,无法适应海量数据处理的要求,因此在海量的数据中改进n-gram算法,减少冗余,减少空间消耗以及运行时间成为亟待解决的问题。针对以上问题,本文改进了传统的n-gram算法以及ED-Join算法,提出一种支持MapReduce的新型算法-n-gram-imp算法。首先,该算法在划分字符串时,用无冗余滑动窗口代替冗余滑动窗口,仅需选取少量的前缀标记参加过滤即可,使空间利用效率以及运行时间都得到了提升。其次,n-gram-imp算法生成的标记无冗余,需要对筛选出的标记进行针对性的过滤操作,所以提出了 Pre-imp前缀过滤算法。最后,在MapReduce计算模型上实现了基于n-gram-imp算法的相似性连接问题,达到了降低算法运行时间,加快数据处理速度的目的。最终在真实数据集和合成数据集上进行了大量的实验。通过与传统的n-gram算法以及ED-Join算法进行对比分析,证明了在并行架构下进行n-gram-imp算法的相似性连接可以达到在平均生成标记的数量、总体运行时间以及消耗内存三方面优于传统的n-gram算法以及ED-Join算法的目的。
其他文献
船舶目标的检测在民用、商用、军用等各方面均有着重要意义,船舶检测不仅仅能为海洋部门的海域监管做出重要贡献,而且还可能影响到国家的经济和领土安全。如相关部门可以通过监控特定海域与特定港口来维护海上交通安全,军队可以通过检测某些重要军事口岸快速获取敌军的军事部署和实力等。因此研究如何准确、快速的进行船舶目标检测非常重要。随着遥感技术的高速发展,尤其是高分系列卫星的成功发射,我们所能获得的遥感图像空间分
图像分割是图像处理与计算机视觉领域低层次视觉中最为基础和重要的领域之一,它是模式识别和目标检测的前提,具有重要的实际价值。但在图像中目标边界模糊的情况下,目标与背
由于每个人的人脸都有其特殊性,人脸识别系统在操作的过程中简单方便且具有无侵害性,使得人脸识别技术成为生物特征识别领域中的重要研究方向,并日益受到各个研究小组以及研
为全面提升烟草栽培管理过程中烟草病虫害的监测、预报和防控技术水平,利用软件技术构建烟草病虫害预警系统来监控烟草的生长状态已逐渐成为烟草栽培生产管理的重要研究方向
信息社会的发展为人们获取信息资源带来了极大的便利,而残疾人却由于身体状况、文化背景等自身局限而难以充分享受信息社会带来的便利,反而面临着被“信息鸿沟”所边缘化的危
无线网络在现实生活中有着广泛的应用,被认为是21世纪最具影响力和最有研究意义的技术之一。无线网络的迅速发展,对无线通信质量的要求越来越高,使用传统有线网络中的通信方
面向服务的体系架构(Service-Oriented Architecture，SOA)作为软件开发的新方式，正引领软件行业新一轮发展。随着基于SOA的服务系统的开发并应用，用户对服务系统的可用性要求越
随着电子记录设备的蓬勃发展,每天都会有大量的图像数据产生。为了更好地理解这些图像数据,针对图像内容的文字标注是必不可少的参考资料。然而单纯依靠人工来标注海量的图像
随着网络和移动通讯的发展,移动互联网应用的时代已经到来。许多原先只在台式机上运行的应用程序,随着移动互联网的兴起和智能移动设备的发展,纷纷转移到智能移动设备上来。
当前,物联网(Internet of Things)快速发展,各式各样的物联网设备接入到网络中,人们可以通过各种传感器与通信技术等实现物与物的连接,获取情景信息,延伸人类的感知,但是却产