导读:本文包含了相似性连接论文开题报告文献综述及选题提纲参考文献，主要关键词:时间序列,Shapelets,相似性连接,差异向量
相似性连接论文文献综述
张振国,王超,温延龙,袁晓洁[1]（2019）在《基于相似性连接的时间序列Shapelets提取》一文中研究指出在时间序列分类问题中,以Shapelets特征为基础的分类算法具有很高的分类准确率和良好的可解释性,因此,高辨别能力Shapelets的提取已成为时间序列研究领域重要的研究热点之一.对于Shapelets提取的研究已取得了很多优秀的成果,但仍存在一些问题,主要是由于通过遍历所有子序列来获取Shapelets的方式非常耗时.尽管可以采取剪枝策略优化该过程,但往往会损失分类准确率.为此,提出一种基于相似性连接的Shapelets提取方法,该方法舍弃逐一判断子序列分类能力的策略,而是以子序列为单位,通过相似性连接的思想构建时序数据间的相似性向量.对于不同类别的时序数据,计算每一对时序数据间的差异向量,进而得到表示时序数据集中不同类别间差异的候选矩阵,然后根据候选矩阵的数值差异,快速筛选出具有高分类能力的Shapelets集合.在真实数据集上的大量实验表明:相比于现有的Shapelets提取方法,这种相似性连接方法所得到的Shapelets在分类任务中不仅具有很好的时间效率,而且能保证高分类准确率.(本文来源于《计算机研究与发展》期刊2019年03期）
成小海[2]（2019）在《基于Spark的高维数据相似性连接算法的研究与实现》一文中研究指出高维数据的相似性连接是指在给定的具有较高维度的数据集中,根据要求的距离计算公式,计算出距离小于给定阈值的向量对。该操作在图像相似度匹配、文本聚类、朋友推荐中有着广泛的应用。但是随着信息技术的发展,数据量的急剧增加,高维数据的相似性连接面临许多挑战。因此,对高维数据的相似性连接的研究有助于提高相关应用领域的效率。通过对现有高维数据相似性连接技术的研究,我们发现很多算法都存在数据冗余、计算重复、占用资源较多等问题,同时实验的效果也不够理想。为了解决以上问题,我们在本文中提出了自己的算法SAVD。其主要是将数据降维技术分段聚合表示(PAA)、符号化聚合表示(SAX)和垂直划分技术相结合。它的具体思想为首先将标准化向量进行PAA和SAX表示;其次对其进行垂直划分;然后通过使用本文提出的过滤方法处理垂直分区得到候选集;最后聚合各分区候选集并进行验证,找出所有满足距离要求的结果集。该方法解决了已有工作中存在的问题,提高了算法的执行效率。同时我们将算法进行了优化,提出了通过叁角不等式比较来过滤掉不必要的向量间计算,这样可以极大的提高算法的执行效率和降低算法的复杂度。为了验证本文中提出的算法的效率,在实验部分分别用MapReduce和Spark框架对该算法进行了实现,并在公开的数据集上与己有的算法进行了对比验证。实验结果表明,本文中提出的方法比现有方法有更高的效率。另外,针对现有使用场景中数据量持续增长的问题,我们将本文提出的算法SAVD在增量高维数据集中进行了拓展研究。首先将原始数据SAX降维处理后并垂直分区的中间运算结果存储到指定位置,然后对增量数据按相同的标准降维和垂直分区后与原始数据的中间输出合并运算,最后分别计算增量数据与原始数据集的相似性连接和计算增量数据与该数据集中的连接。实验证明,我们提出的方法要比直接使用相似性连接有更高的效率。(本文来源于《天津工业大学》期刊2019-01-11）
缪丰羽,王宏志,阮群生[3]（2018）在《一种基于MapReduce的不确定图上的相似性连接方法》一文中研究指出相比于确定图上的相似性连接,不确定图上的相似性连接通常具有更大的实际应用价值以及计算复杂性。文中研究了基于MapReduce分布式编程框架的不确定图上的相似性连接问题,提出了基于概率和的Map方剪枝和Reduce方剪枝的两种剪枝策略。Map方剪枝策略在映射过程中过滤掉了不可能具有相似图的不确定图。Reduce方剪枝策略用于减少约减过程中的候选图对。基于这两种剪枝策略,文中提出了一种基于MapReduce框架的不确定图上的相似性连接算法MUGSJoin。实验结果证明,该算法与同类算法相比具有更好的性能和可扩展性。(本文来源于《计算机科学》期刊2018年12期）
阮榕城[4]（2018）在《基于动态索引和虚拟多重字符过滤的新型字符串相似性连接分布式算法研究》一文中研究指出字符串相似性连接就是可以在单个或多个字符串样本数据集中,找出位于数据集中的所有相似字符串对。随着互联网信息系统和人工智能系统的不断发展,字符串相似性连接在很多应用中具有广泛的使用场景,例如网页相似性检索、数据融合、生物信息学、模糊字符串匹配等,是最近几年备受关注的科研方向之一。并且,越来越多的互联网企业都把字符串相似性连接作为未来人工智能发展的基础建设。但是,大数据时代的到来,海量字符串数据日益普遍,现有的字符串相似性连接算法在处理海量数据集时并不高效,主要有如下限制:(1)现有的算法均在将海量数据存储在磁盘中,然后在计算相似性的时候导入内存。然而这些算法都会在内存中产生大量的倒转索引,大量冗余索引将大大超过单台机器节点的内存限制。(2)现有的算法使用的过滤机制并不高效,产生的候选集中仍然包含大量的不相似子集,后续的数据验证环节就需要消耗更多的时间去验证数据。(3)现有的算法都是基于单台机器节点使用,然而单机器节点的内存往往是受限的,不易扩容,已经难以应付海量的数据集。本文在传统字符串相似性连接算法的基础上提出了一种新型的基于动态索引和虚拟多重字符过滤的分布式算法——DV-Join。新的算法能够解决传统算法的历史遗留问题。本文主要在以下几个方面有了重大突破:(1)该算法引入动态索引,在计算相似性的过程中动态调整已经产生的倒转索引,能够大大减少倒转索引的内存消耗。(2)在原有的过滤机制上添加了虚拟多重字符过滤算法,能进一步过滤候选对集合中非相似子集的数量,节省候选集验证时间。(3)使用开源的集群分布式系统Spark,在集群中并行执行对海量数据的处理计算任务,大大减少计算时间。在经过了大量的实验后,能够得到以下结论:DV-Join算法在处理海量数据集时,比已有的传统字符串相似性连接算法更有效率。(本文来源于《厦门大学》期刊2018-06-30）
许嘉,宋超,吕品,李陶深[5]（2019）在《基于EMD距离的数据流分布式相似性连接技术》一文中研究指出随着数据获取设备的不断进步和数据获取技术的快速发展,如何分析和挖掘应用中快速产生的数据流成为亟待解决的问题.数据流的相似性连接返回两个数据流上相似的数据对,是分析和挖掘数据流的重要操作.相比于Lp范式距离,例如曼哈顿距离和欧氏距离,EMD距离(Earth Mover's Distance)因其可以更准确地量化直方图元组之间的相似性而受到广泛关注,被广泛应用于解决基于内容的图像检索、冗余图像识别以及视频对象跟踪等重要应用问题.然而EMD距离的计算复杂度却高达叁次方,阻碍了EMD距离在数据流相似性连接问题中的应用.该文基于开源的Apache Storm数据流分布式并行处理框架,设计并实现了基于EMD距离的数据流分布式相似性连接技术,命名为EMD-DDSJ技术.该技术在数据分发时维护了连接计算节点上的数据局部性,并基于该数据局部性增强了连接算法对不相似直方图元组对间EMD计算的过滤性能,提高了各个连接计算节点的执行效率.同时基于连接计算节点的代价模型,提出了基于反馈的负载均衡策略,有效提升EMD-DDSJ技术的整体执行性能.在真实数据集上的实验结果展示了该文提出的EMD-DDSJ技术的高效性和可扩展性,比相关最好的技术在处理吞吐率上最高提升了1.4倍,在元组平均处理延迟上最多降低了44%,并且随着相似性阈值或滑动窗口大小的增大该提升比率还会进一步增大.(本文来源于《计算机学报》期刊2019年08期）
成小海[6]（2018）在《基于Spark的高维数据相似性连接》一文中研究指出高维数据相似性连接(HDSJ)是指在给定的空间数据库中,频繁执行连接和距离计算操作找出向量空间满足给定条件的数据对。但是随着数据量和维数的增加,HDSJ的计算成本将呈指数增加。针对HDSJ在处理海量数据时效率不佳的问题,利用Spark集群分布式和基于内存并行计算特性,提出了基于Spark框架的HDSJ改进方法。该方法主要借助Spark中高效的RDD算子,使用分段聚合近似(PAA)表示原始的高维向量,用符号聚合近似(SAX)将表示后的向量重新组织成组,这样可以避免大量不必要的计算。PAA和SAX都是已有的降维技术,将二者结合使用可以很好地过滤掉大部分的干扰数据。实验结果证明,该方法在保证实验结果准确率的前提下提高了运算速率,比现有方法有更好的性能优势。(本文来源于《计算机技术与发展》期刊2018年08期）
马友忠,张智辉,林春杰[7]（2018）在《大数据相似性连接查询技术研究进展》一文中研究指出为了深入理解和全面把握大数据相似性连接查询技术的研究进展,更好地促进其在图片聚类、实体解析、相似文档检测、相似轨迹检索等领域的广泛应用,对大数据相似性连接查询技术相关研究工作进行了深入调研和分析。首先对相似性连接查询的基本概念进行了介绍,然后分别对集合、向量、空间数据、概率数据、字符串等不同类型大数据的相似性连接查询相关研究工作进行了深入研究,对其优缺点进行了分析和总结。最后,指出了大数据相似性连接查询面临的若干挑战性问题及未来的研究重点。(本文来源于《计算机应用》期刊2018年04期）
缪丰羽,王宏志[8]（2018）在《一种不确定图数据库上的相似性连接方法》一文中研究指出在确定图上进行的相似性连接已有许多研究成果.然而,在实际应用中会有许多因素使得图结构数据变得不确定.研究了不确定图数据库上的相似性连接问题.采用联合概率分布表示法来描述图中边的不确定性,结合一种新的图的相似性度量方法,给出了不确定图数据库上的相似性连接的形式化定义,并设计了一组过滤策略来减少连接过程中候选图对的数量.大量的实验数据表明,所提出的方法具有较好的可行性和准确性.(本文来源于《软件学报》期刊2018年10期）
王俊凯[9]（2017）在《基于概率型相似性连接的聚集查询算法研究》一文中研究指出连接聚集查询在数据库、联机分析处理以及数据仓库中应用广泛。此类查询通常先采用连接操作将多张关系表合并起来,然后再执行聚集运算。随着数据库和数据仓库中出现了大量不确定性数据,连接聚集查询往往在连接阶段就面临失败。概率型相似性连接(Probabilistic Similarity Join,PSJ)基于相似性度量函数,能够解决不确定性数据的连接问题。然而,在PSJ上做聚集查询却面临挑战。一方面,PSJ具有复杂的映射约束,传统的聚集方法不适用于此类连接的聚集查询。另一方面,现有的研究只能解决一对一映射约束的PSJ聚集问题,而且效率较低。本文旨在解决PSJ结果上的聚集查询问题。首先,针对映射关系为多对多的PSJ,本文采用元组级不确定性模型对其建模,并基于动态规划和分治策略提出了两种聚集方法。其次,本文采用属性级不确定性模型对一对多型PSJ建模,并将多对多的聚集方法适配至此模型中,解决了一对多型PSJ的聚集查询问题。最后,本文采用概率图模型对一对一型PSJ建模,引入生成函数方法,再次基于动态规划和分治思想提出了一种聚集方法。本文在真实数据集DBLP上进行实验,结果表明本文提出的方法比现有方法更具优越性。(本文来源于《浙江大学》期刊2017-07-08）
张佳振[10]（2017）在《基于EMD的数据流相似性连接的研究》一文中研究指出近年来,随着共享视频、社交网络等新兴产品的崛起,网络中的数据规模也呈爆炸式增长。这些数据具有结构复杂、数量巨大等特点,因此从海量数据中提取关键数据难度变得越来越大,尤其是在海量数据中做相似性连接显得愈发困难。所谓相似性连接,是指从一个或两个数据源中查找所有的相似数据对,并返回结果。相似性搜索在概率数据相关的许多实际应用中扮演着十分重要的作用,如无线传感器网络、股票分析以及基于多个视频源的对象跟踪。EMD距离(Earth Mover's Distance)在计算机视觉领域返回的相似性概率数据与人类对相似性的判断更一致。然而,EMD立方级的复杂度阻碍了其相关应用的普及,特别是在分析快速到达数据的数据流方面,同时源源不断到达的数据可能会造成系统缓存不足、系统过载导致性能急剧下降等问题。为此,本文尝试采用EMD的方法对滑动窗口语义的数据流进行相似性连接处理,主要开展了以下方面的研究工作:(1)针对EMD距离函数优化问题中存在的复杂度高、计算时间长,数据流数据的无限性等问题,提出一种基于B+森林索引框架的EMD相似性算法(称为EMD-DSJoin)。算法的设计思想是:利用线性规划的原始对偶理论把到达的直方图概率数据转换为EMD下界距离,然后基于EMD的下界距离构建一组B+森林索引,利用B+森林有效地对不需要进行EMD计算的直方图概率数据剪枝,从而加快基于EMD的相似性连接效率;最后利用滑动窗口解决有限缓存保存延迟数据问题。算法具体的实现方法为:(a)通过构建B+树森林和更新可行解,提高过滤效果,过滤掉完全相关或完全不相关的数据;通过构建子索引,利用丢弃成块的子索引完成数据的丢弃,减少丢弃数据的维护代价。(b)优化B+树森林存档周期,根据滑动窗口值和容量因子的变化,使存档周期P值达到自适应变化的效果,从而让B+树森林索引机制更高效运行。通过用真实环境的数据集进行的验证实验和对比分析结果表明,EMD-DSJoin算法的CPU时间、EMD求精次数都有一定程度的减少,处理速度比已有对比算法快了 35%左右,说明EMD-DSJoin算法使数据剪枝更为高效,为处理乱序数据提供更为有效的处理策略。(2)数据流的数据到达并不是匀速的,当数据在某时间段集中到达时,由于系统资源有限,数据流高爆发时容易造成系统过载,从而导致连接性能大幅度下降。为了解决这一问题,本文提出了基于EMD-DSJoin算法的降载策略。该策略充分考虑了数据流上数据具有的时间关联性,在系统过载时过滤掉数据中包含的冗余数据,有效减少了相似性连接的次数,同时尽可能保证相似性连接结果的完整性。实验结果表明,使用降载策略的EMD-DSJoin 算法可以根据丢弃阈值设定的不同,不同程度地减少EMD求精次数和CPU时间,验证了降载策略的可行性和有效性。本文首次采用基于滑动窗口语义的EMD处理数据流相似性连接技术,提出了一系列策略来提高EMD-DSJoin在数据流上处理乱序延迟直方图概率数据的能力,较好地解决了数据流高爆发时系统过载问题。论文的研究成果为数据流上的数据相似性连接提供了提供新的思路和技术手段。(本文来源于《广西大学》期刊2017-05-01）
相似性连接论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
高维数据的相似性连接是指在给定的具有较高维度的数据集中,根据要求的距离计算公式,计算出距离小于给定阈值的向量对。该操作在图像相似度匹配、文本聚类、朋友推荐中有着广泛的应用。但是随着信息技术的发展,数据量的急剧增加,高维数据的相似性连接面临许多挑战。因此,对高维数据的相似性连接的研究有助于提高相关应用领域的效率。通过对现有高维数据相似性连接技术的研究,我们发现很多算法都存在数据冗余、计算重复、占用资源较多等问题,同时实验的效果也不够理想。为了解决以上问题,我们在本文中提出了自己的算法SAVD。其主要是将数据降维技术分段聚合表示(PAA)、符号化聚合表示(SAX)和垂直划分技术相结合。它的具体思想为首先将标准化向量进行PAA和SAX表示;其次对其进行垂直划分;然后通过使用本文提出的过滤方法处理垂直分区得到候选集;最后聚合各分区候选集并进行验证,找出所有满足距离要求的结果集。该方法解决了已有工作中存在的问题,提高了算法的执行效率。同时我们将算法进行了优化,提出了通过叁角不等式比较来过滤掉不必要的向量间计算,这样可以极大的提高算法的执行效率和降低算法的复杂度。为了验证本文中提出的算法的效率,在实验部分分别用MapReduce和Spark框架对该算法进行了实现,并在公开的数据集上与己有的算法进行了对比验证。实验结果表明,本文中提出的方法比现有方法有更高的效率。另外,针对现有使用场景中数据量持续增长的问题,我们将本文提出的算法SAVD在增量高维数据集中进行了拓展研究。首先将原始数据SAX降维处理后并垂直分区的中间运算结果存储到指定位置,然后对增量数据按相同的标准降维和垂直分区后与原始数据的中间输出合并运算,最后分别计算增量数据与原始数据集的相似性连接和计算增量数据与该数据集中的连接。实验证明,我们提出的方法要比直接使用相似性连接有更高的效率。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
相似性连接论文参考文献
[1].张振国,王超,温延龙,袁晓洁.基于相似性连接的时间序列Shapelets提取[J].计算机研究与发展.2019
[2].成小海.基于Spark的高维数据相似性连接算法的研究与实现[D].天津工业大学.2019
[3].缪丰羽,王宏志,阮群生.一种基于MapReduce的不确定图上的相似性连接方法[J].计算机科学.2018
[4].阮榕城.基于动态索引和虚拟多重字符过滤的新型字符串相似性连接分布式算法研究[D].厦门大学.2018
[5].许嘉,宋超,吕品,李陶深.基于EMD距离的数据流分布式相似性连接技术[J].计算机学报.2019
[6].成小海.基于Spark的高维数据相似性连接[J].计算机技术与发展.2018
[7].马友忠,张智辉,林春杰.大数据相似性连接查询技术研究进展[J].计算机应用.2018
[8].缪丰羽,王宏志.一种不确定图数据库上的相似性连接方法[J].软件学报.2018
[9].王俊凯.基于概率型相似性连接的聚集查询算法研究[D].浙江大学.2017
[10].张佳振.基于EMD的数据流相似性连接的研究[D].广西大学.2017