一种基于MapReduce的大数据集相似自连接算法

如何快速发现数据集中重复或相似的记录是大数据处理技术中的一个基本问题。相似连接是一种有效的相似数据查找方法,且基于MapReduce的相似连接算法因对大数据集的处理能力强而得到广泛关注。通过分析当前相似连接算法进行自连接时存在的自连接冗余、读取原字符串复杂等问题,在Massjoin算法的基础上提出了一种改进的基于MapReduce的自连接算法。改进算法在过滤阶段增加了消除自身冗余的过滤条件,在验证阶段又采用了生成正反候选对和组合id等去冗余技术,并且读取原始字符串内容时只需读取数据集一次。实验数据显示,改进算法无论在过滤阶段还是在验证阶段都减少了算法的CPU时耗,结果表明所提改进策略是有效的。     

一种基于MapReduce的局部相似自连接算法

局部相似自连接能在给定的单个数据集中快速找到所有满足相似要求的记录对,它在数据清洗、基因序列比对和剽窃检测等领域都有广泛的应用。为研究基于单个字符串集的并行自连接算法,提出了一种基于MapReduce框架的自连接算法,解决了局部相似自连接的定位问题。该算法采用了过滤验证二阶段模式;在过滤阶段,采用无关对过滤和冗余对过滤抛弃了大量的无效字符串对;在验证阶段,通过生成小编号串内容保留项解决了字符串编号和内容的快速配对问题。实验结果显示,该算法在大数据集上的自连接速度一直快于当前的优秀算法LS-Join,同时非常适合动态编辑距离参数环境下的局部相似自连接操作。实验结果也证明,该算法中提出的相关技术有效地提高了局部相似自连接的速度。     

一种用于大数据内容安全监测的快速相似匹配并行算法

为了提高大数据集基于内容的相似匹配速度,本文采用MapReduce框架实现了一种并行的相似匹配算法,解决了大数据信息安全监测中的快速相似匹配问题。算法基于先过滤、再验证的方式设计了三个阶段。在配对阶段,通过对索引子串和匹配子串进行配对去除了不包含共享q-gram的无关对;在过滤阶段,通过q-gram命中特征过滤掉了一定不是真实匹配的候选对;在验证阶段,通过计算候选对的真实匹配度找出了满足要求的真实匹配。实验结果证明,本文提出的字符串分割过滤方法有效地提高了相似匹配的速度。实验结果也显示新算法较适合匹配度变化范围较大的应用场景。     

BMGSJoin：一种基于MapReduce的图相似度连接算法

图相似度连接在数据挖掘领域应用广泛,尤其是在数据预处理阶段,可用于数据清理、近复本检测等,其研究具有十分重要的意义。针对基于编辑距离约束的图相似度连接问题进行研究,返回两个图集合中所有编辑距离不超过给定阈值的图对。基于分布式编程框架MapReduce,设计采用“过滤-验证”框架的MGSJoin算法,利用基于路径的q-gram签名实现非解候选对的过滤,计数过滤。鉴于该算法键值对数量庞大的潜在问题,引入Bloom Filter技术对算法进行改进并设计BMGSJoin算法。实验结果表明,提出的两种图相似度连接算法能较大地改善现有算法的效率和可扩展性,并能较好地应对当前大数据挖掘分析的需求。     

基于相似连接的多源数据并行预处理方法

大规模网络环境和大数据相关技术的发展对传统数据融合分析技术提出了新的挑战。针对目前多源数据融合分析过程灵活性差、处理效率低的问题，提出了一种基于相似连接的多源数据并行预处理方法，该方法采用了分治和并行的思想。首先，通过对多源数据中的相似语义进行统一、对个性语义进行保留的预处理方法提高了灵活性；其次，提出了一种改进的并行MapReduce框架，提高了相似连接的效率。实验结果表明，所提方法在保证数据完整性的基础上，使总的数据量减小了32%。与传统的MapReduce框架相比，改进后的框架在耗费时间方面减小了43.91%，因此该方法可以有效提高多源数据融合分析的效率。     

一种基于数据划分的字符串相似连接外存算法

字符串相似连接操作具有广泛应用,因而将着重研究基于编辑距离的字符串相似连接.而现有的字符串相似连接算法大多为内存算法.实际应用中的数据集越来越大,有必要针对超大规模数据集研制字符串相似性连接外存算法.利用组合频率向量划分数据集,并提出了基于编辑距离的字符串相似性连接外存算法框架,证明了磁盘调度问题的难度并提出了不同的启发式磁盘调度方法.此外,还提出了基于该外存算法框架实现字符串相似性连接增量式计算的方法.实验结果表明,数据划分方法可以有效地过滤不相关的数据子集;磁盘调度算法能够有效减少磁盘IO次数;外存算法是高效的;增量式计算方法能够高效地处理数据更新.     

基于MapReduce的相似自连接新方法：过滤和内切圆算法

相似自连接是一个在很多应用领域中很重要的问题.对于海量数据集,MapReduce可以提供一个有效的分布式计算框架,相似自连接操作也同样可以应用在MapReduce框架下.但已有研究工作仍然存在不足,如对于聚集数据区域采用加细划分方法,目的是负载平衡,但不易实现.现有的算法不能有效地完成海量数据集的相似自连接操作.为此提出了2个新颖的基于MapReduce的相似自连接算法,其思想是采用坐标过滤技术,形成有效候选集,以及针对聚集区域采用六边形划分的内切圆算法.过虑技术是在等宽网格划分基础上,利用同一维坐标间的距离差与相似性约束阈值ε进行比较,可以明显地减少候选集的数量,也证明了六边形划分是所有正多边形全覆盖中最优的划分方法.实验结果表明：新方法比其他算法有更高的效率,提高效率80%以上,它能够有效地解决有聚集区域的海量数据集的相似自连接问题.     

基于FP-tree和MapReduce的集合相似度自连接算法

利用集合相似度自连接算法找出一个集合集中所有相似度大于给定阈值的集合对有着广泛的应用. 基于过滤-验证框架和并行分布式计算框架MapReduce的集合相似度连接是近年来的研究热点. 但现有算法在阈值低时产生较大规模的候选集,导致性能不理想. 针对这一问题,提出采用频繁模式树FP-tree及其派生结构FP-tree*将数据压缩在内存中计算集合相似度自连接以减小候选集规模. 首先设计并讨论基于现有FP-tree*的集合相似度连接计算及其优缺点,提出遍历效率更高的线性频繁模式树结构模型TELP-tree及基于它的算法TELP-SJ（TELP-tree self join）,其包括分别面向构建树和遍历树的2阶段过滤算法,这些算法可以减小树规模和减少树遍历. 然后,设计基于MapReduce的并行分布式算法FastTELP-SJ. 最后,基于4组真实应用数据集进行3组性能比较实验. 实验结果表明FastTELP-SJ算法面向高维大规模集合相似度自连接计算时,包括执行时间、内存占用率、磁盘使用量和可扩展性的运行效率最好.

     

基于划分的集合相似连接

集合相似连接(set similarity join)是指在给定的数据集中,按照基于集合间覆盖关系的相似度计算方法来衡量数据之间的相似度、并找出所有相似度不小于给定阈值的数据对的操作.集合相似连接作为一种新的基本操作在很多领域中有重要应用.随着社会网络、移动应用以及在线服务的发展,使得数据收集的效率和规模得到了很大的提高,同时给相似连接操作带来新的挑战.根据集合相似的必要条件,提出了相似集合之间的差异度.利用差异度和鸽巢原理,提出了一种新颖的基于数据划分的集合相似连接计算方法,该方法对集合进行自适应的均衡划分,并利用基于划分块的过滤方法来提高过滤的效率.为了进一步提高过滤的效果和相似连接的效率,利用划分块的位置信息提出了增强的过滤方法.针对提出的方法,在不同的环境下进行了实验,实验结果表明,该方法与已有的方法相比可以有效地提高相似连接的效率.     

Ed-Sjoin:一种优化的字符串相似连接算法

相似连接(similarity join)在数据清洗、生物信息、模式识别等应用领域中有着广泛应用,其中基于编辑距离的字符串相似连接是一种重要的相似连接.尽管当前有一些基于编辑距离的字符串连接算法提出,然而,当前的算法存在着大量的多余计算,影响了算法的效率.为了高效计算基于编辑距离的字符串连接,提出了一种优化的算法Ed-sjoin,分别从优化筛选算法和基于前缀的重复消减策略两方面对算法进行优化,这些优化策略可以实现更加有效的剪枝,并且避免了部分重复计算,从而加速算法的执行.实验结果表明,提出的方法优于现有方法.     

一种基于主存Δ-tree的高维数据自相似连接处理

相似连接作为数据挖掘的基元,可被用来大幅度提高相似搜索、数据分析和数据挖掘的速度.大多数研究主要集中在大量基于磁盘数据的高维连接.目前计算机可得到的主存容量越来越大以及对空间连接的有效处理的需求表明,一大类问题的空间连接能够在主存中处理.Δ-tree是一个新提出的多层索引,已被证实优于其他主存索引.因此,以Δ-tree为基础,提出了一种空间连接算法Δ-tree-join,研究了它的性能,和目前最先进的算法EGO-join和EGO\\+*-join进行了比较.结果显示Δ-tree-join的效率比它们有大幅度提高,是一种有效的连接方法.     

泛化双向相似连接

相似连接是数据管理领域的一个热门话题,已在社会生产生活中得到广泛应用.然而,现有的相似连接方法并不能满足真实世界不断增长的客观需求.本文通过引入定义在多种数据类型上的“满足”操作符和每条数据的独立阈值定义了一种新的相似连接——泛化双向相似连接.这种连接扩展了相似连接的应用范围.同时,本文还提出了两种高效的解决泛化双向相似连接问题的方法：子连接集算法和映射-过滤-验证算法.在真实和合成数据集上的大量实验结果展示了所提方法的正确性和有效性.     

一种基于主存△—tree的高维数据自相似连接处理

相似连接作为数据挖掘的基元,可被用来大幅度提高相似搜索、数据分析和数据挖掘的速度.大多数研究主要集中在大量基于磁盘数据的高维连接.目前计算机可得到的主存容量越来越大以及对空间连接的有效处理的需求表明,一大类问题的空间连接能够在主存中处理.△-tree是一个新提出的多层索引,已被证实优于其他主存索引.因此,以△-tree为基础,提出了一种空间连接算法△-tree-join,研究了它的性能,和目前最先进的算法EGO-join和EGO*-join进行了比较.结果显示△-tree-join的效率比它们有大幅度提高,是一种有效的连接方法.     

基于列存储的MapReduce分布式Hash连接算法

大数据具有规模大、深度大、宽度大、处理时间短、硬件系统普通化、软件系统开源化的特点。传统关系型数据库在对大数据进行操作时存在系统性能严重下降、计算效率提升有限以及可扩展性差等问题,因此引入MapReduce并行计算模型,提出一种大数据上基于列存储的MapReduce分布式Hash连接算法。首先,设计面向大数据的分布式计算模型,在设计的分片聚集并行连接的基础上,利用Hash连接以及动态探测方法优化了数据并行连接处理效率;然后,针对该算法开发了基于Hadoop的原型系统。通过实验证明,在大数据分析处理中,所提算法在执行时间和负载能力上都有很好的性能表现,也能提供良好的可扩展性。     

一种改进的相似重复记录检测方法

针对当前相似重复记录检测方法中存在的问题．提出一种改进方法．该方法根据关系表的决定属性值划分记录集,并在每个决定属性值类中检测相似重复记录．在决定属性值聚类时,提出了动态优先队列聚类算法和合并逆序算法．尽可能使相似重复的属性值聚为同一类;在记录聚类时提出了类调整算法,以提高类的代表记录的代表性．通过大量的实验分析,验证了该方法的有效性．     

一种大数据量的相似记录检测方法

大数据量的相似重复记录检测是数据清洗中的一个重要问题,提出一种基于q-gram层次空间的聚类检测方法：它首先将数据映射成q-gram空间中的点,并根据q-gram空间中的相似性度量采用层次聚类方法将相似的重复记录检测出来．它克服了传统的“排序＆合并”方法由于字符位置敏感不能将相似记录字符串排在邻近位置的不足和大数量外排序引起I／O代价过大的问题．理论分析和实验表明,方法不仅具有好的检测精度,且有好的伸缩性,能够有效地解决大数据量的相似重复记录检测．     

基于Δ-tree的高维数据相似连接算法

为了解决主存中高维数据相似连接问题,基于高效索引Δ-tree提出了连接两个不同数据集的主存相似连接算法Δ-tree-join*.该算法采用自顶向下的模式,充分利用Δ-tree的特性,使用较少的维数计算聚类之间的距离及数据点与聚类之间的距离,通过该距离过滤掉不必要的节点和数据点,减少计算量,提高连接效率.实验结果表明,△...     

一种基于MapReduce的不确定图上的相似性连接方法

相比于确定图上的相似性连接,不确定图上的相似性连接通常具有更大的实际应用价值以及计算复杂性。文中研究了基于MapReduce分布式编程框架的不确定图上的相似性连接问题,提出了基于概率和的Map方剪枝和Reduce方剪枝的两种剪枝策略。Map方剪枝策略在映射过程中过滤掉了不可能具有相似图的不确定图。Reduce方剪枝策略用于减少约减过程中的候选图对。基于这两种剪枝策略,文中提出了一种基于MapReduce框架的不确定图上的相似性连接算法MUGSJoin。实验结果证明,该算法与同类算法相比具有更好的性能和可扩展性。     

基于△-tree的高维数据相似连接算法

为了解决主存中高维数据相似连接问题,基于高效索引合△-tree提出了连接两个不同数据集的主存相似连接 算法△-tree-join*。该算法采用自顶向下的模式,充分利用△-tree的特性,使用较少的维数计算聚类之间的距离及数 据点与聚类之间的距离,通过该距离过滤掉不必要的节点和数据点,减少计算量,提高连接效率。实验结果表明,△- tree-join‘是一种更适合主存的相似连接算法,比目前这方面最先进的算法EGO及EGO‘具有更优的性能。     

基于MapReduce的数据倾斜连接算法

连接操作是大规模数据集在数据分析应用中最常用的操作,针对MapReduce自身不能有效地处理数据倾斜情况下的连接操作,提出了基于MapReduce的频次分类连接算法。根据数据在连接数据集中出现的频率将整个数据集分为3类,对倾斜数据利用分区算法和广播算法实现数据重分布,以消除数据倾斜的影响;对非倾斜数据采用Hash算法实现数据重分布。重分布后的数据在单节点内即可完成数据连接操作,避免了MapReduce框架下连接操作的跨节点传输代价;同时有效地均衡了MapReduce各节点的任务负载,从而提高了数据倾斜状态下连接操作的效率。通过与传统连接算法的对比,证明了所提算法的有效性和实用性。