导读:本文包含了相似搜索算法论文开题报告文献综述及选题提纲参考文献，主要关键词:图编辑距离,图相似性搜索,外存索引,简明索引
相似搜索算法论文文献综述
陈晓阳[1]（2019）在《大规模图数据库的相似性搜索算法研究》一文中研究指出图作为强大的数据模型,不仅能够描述目标物体的属性,还能描述各个组成之间的结构关系,已经被成功地应用到许多领域中,包含生物信息学,计算机视觉,软件工程和社交网络等。另外一方面,随着信息技术的快速发展,可获得的图数据急剧增加,有效的图管理和查询变得越来越重要。相比于图数据库中的精确搜索,图相似性搜索可以提供鲁棒的解决方案,也就是说它支持容错和允许搜索不精确定义的模式。鉴于图编辑距离(Graph edit distance,GED)的优良特性:适用于任意类型的图和能够精确地捕捉图之间的结构和标签差异,本文考虑了基于GED度量的图相似性搜索问题。具体来讲,给定查询图Q和阈值τ,在图数据库D中找到所有与Q编辑距离小于或等于τ的图。由于GED计算是NP-hard问题,目前已有的方法都基于“过滤–验证”框架。在过滤阶段,设计不同的GED下界过滤那些肯定不满足阈值条件的图;这个阶段通过特定的索引结构高效地完成。在验证阶段利用精确的GED计算方法验证剩余的图。针对已有索引方法的不足(松弛的GED下界,过大的索引空间和有限的可扩展性)和GED计算方法的缺点(巨大的搜索空间,过量的内存消耗和许多昂贵的回溯),本文提出了新的索引结构和GED计算方法,以提高图相似性搜索的性能。具体工作概括为下面四个部分:第一部分研究了解决图相似性搜索的外存索引结构。针对现有索引方法在处理大规模图数据库时具有有限的可扩展性,本文提出了一种基于q-gram表示的外存索引框架,它能够处理超大规模的图数据库。具体而言,将q-gram计数过滤器转变为稀疏矩阵向量乘(Sparse matrix-vector multiplication,SpMV)问题,并提出了基于混合布局的q-gram矩阵索引,以实现有效的查询处理。同时,将每个图转变为vertex-edge 2D空间的点,并将全局计数过滤器转变为2D查询矩形来提高查询性能;这允许只在缩小的查询区域中执行搜索,从而显着地减少查询I/O次数。在真实数据集上的实验结果表明所提外存索引能够处理包含2500万个化合物的超大数据集,并比基于q-gram的外存倒排索引需要更少的查询I/O次数。第二部分研究了解决图相似性搜索的简明索引结构。鉴于现有内存索引方法的过滤能力有限和索引空间过大的问题,本文提出了一种简明的q-gram树索引,它结合了简明数据结构和混合编码,以最小的内存空间使用来提高查询性能。具体来说,所提简明q-gram树的索引大小只有主流索引大小的5%–15%,但同时在测试数据集上实现了几倍的查询加速。此外,还提出了两个有效的GED下界(即,q-gram计数下界和度序列下界)和一种下界提升技术,以获得尽可能小的候选集。在真实和模拟数据集上的实验结果表明,所提简明q-gram树在索引大小和查询性能方面都优于主流索引方法。据我们所知,该索引是第一个能够处理包含2500万个化合物的超大数据集的内存索引。第叁部分研究了GED的高效计算方法。观察到已有GED计算方法具有若干缺点:巨大的搜索空间,过量的内存消耗和许多昂贵的回溯调用,本文呈现了一种新颖的基于顶点映射的GED计算方法。该方法能够识别无效和冗余映射,从而在缩小的搜索空间中计算GED。此外,采用了波束堆栈搜索(beam-stack search),并结合了两种专门设计的启发式方法来提高GED计算,实现了内存利用和回溯调用之间的均衡。在真实和模拟数据集上的实验结果表明,所提方法在稀疏和稠密图上都优于主流GED计算方法。此外,还扩展了该方法以解决图相似性搜索问题。实验结果表明,扩展后的方法比已有的图相似性搜索方法快几十倍。第四部分研究了GED的近似计算方法。考虑到GED计算的NP-hard困难性限制了其在很多领域中的应用,本文提出了一种任何时间算法(anytime algorithm)近似计算GED。该近似算法将运行时间作为参数从而输出一系列改进的GED次最优解(suboptimal solution),以满足不同的运行时间需求。具体而言,提出了一种基于邻居偏差的贪心匹配方法,它能够在二次运行时间内快速地得到GED的初始次最优解;然后,采用结合了更有效的启发式估计的树搜索方法来提高所获得GED次最优解。该启发式函数基于扩展的分支编辑距离,理论上能够产生比标签编辑距离更加紧确的GED下界。在大的和小的运行时间设置下,相比于主流的GED近似算法,所提任何时间算法都能实现最小的偏差。(本文来源于《西安电子科技大学》期刊2019-03-01）
褚蓉,钮焱[2]（2018）在《基于形状特征的DTW距离相似性搜索算法》一文中研究指出针对时间序列相似性研究中存在动态时间弯曲DTW复杂度过高与分段思想易造成特征丢失的问题,提出了一种基于形状和升降性提取序列数据重要特征点的DTW相似性搜索算法,利用关键特征点快速筛选相似候选子序列集合,计算各个原始子序列的DTW距离,与改进的分段DTW距离度量方法进行实验比较。结果表明,该方法提高了相似性搜索效率,并具备更高的相似度。(本文来源于《软件导刊》期刊2018年03期）
董肖凯,方宏舰,周波[3]（2018）在《区间映射规则下的时间序列相似形态搜索算法——基于改进的正则化损失函数》一文中研究指出时间序列数据是一种随机过程,历史的波动趋势在不同的时期看来往往似曾相似。本文使用用可解释性的符号来刻画时间序列变化形态,改进了基于符号聚合相似的搜索模型,在原始搜索模型中引入改进的参数优化准则HIC,并提供了将字符转义为数值的变换方法,用于度量两个形态间的相似程度。结果表明,改进的模型实现了字符、数值的相互转化,且满足距离下界原理;参数的优化准则稳健的提高了模型的搜索精,有效的降低了算法复杂度。(本文来源于《价值工程》期刊2018年03期）
冯欢[4]（2017）在《高性能相似性搜索算法与优化关键技术研究》一文中研究指出相似性搜索是计算机学科中的一个基础性课题,被广泛应用于诸多研究领域中,包括信息检索,多媒体处理,机器学习等等。相似性搜索算法主要用于解决最近邻(Nearest Neighbor,NN)查询问题,由于在大部分的应用场景下,使用近似的查询结果就可以很好的满足应用的需求。因此,近年来,学术界提出了一系列近似求解最近邻查询问题的相似性搜索算法。然而,在大数据环境下,应用对搜索算法在数据维度、计算规模以及搜索性能等方面提出了更高的要求,使得高性能相似性搜索算法得到了当前学术界与工业界的普遍关注,这也是本文的主要研究内容。论文的主要成果包括:1.提出最优化子空间构建方法,提升了基于子空间聚类的一类相似性搜索算法的精度。针对基于子空间聚类的一类相似性搜索算法,本文提出了四种不同的子空间构建方案,并通过实验分析发现了子空间构建与搜索精度、搜索速度叁者间的关联关系。基于这些关系,进一步提出了子空间构建的最优化方法,该方法解决了此类算法在搜索精度上不稳定的缺陷,在保持同等搜索速度的前提下能够获得26.7%的精度提升。2.提出一种新的高精度高可扩展的并行相似性搜索算法PCAF。PCAF首次采用估算排名的方式来预测数据之间相似性的大小差异,同时实现了一种开销极小的双堆数据过滤机制,并且创新性的对搜索任务内部耦合进行拆解,设计了一种细粒度的并行搜索策略。实现结果表明,与现有的五种最流行的并行相似性搜索算法相比,PCAF可扩展性最佳,速度最快,能够在最短时间内查询到高精度(>98%)最近邻结果,获得1.3倍至18.9倍的加速比,并且可在多种不同数据集上实现精准搜索的算法。3.提出一套执行优化框架,解决了相似性搜索算法在实际应用中的性能优化问题。该框架对执行优化系统的架构、各部分组成形式和逻辑结构都进行了明确且详细的定义。通过设置精度、速度和计算规模优化目标,利用二分查找原理调节算法参数,使得调优后的算法能够满足用户对实际应用中的精度和性能需求。实验结果表明,使用基于该框架设计的执行优化系统对RKD、RBC和PCAF算法调优以后,能够在达到用户所需精度(>95%)的同时获得5.87倍至70.46倍的性能提升。其中,PCAF算法能够在不到3秒的时间内,完成对包含100万条960维数据的真实大规模数据集“GIST1M”的最近邻查询,其搜索精度高达95.15%。(本文来源于《清华大学》期刊2017-12-01）
姜大光,孙贺娟,易军凯[5]（2017）在《基于距离的相似最近邻搜索算法研究》一文中研究指出为了提高相似最近邻搜索(ANN)算法的精度,提出了一种在度量空间下基于距离的相似最近邻搜索算法—优化的VP森林(OVF)算法。在传统VP树(VT)算法的基础上,首先采用改进的选择优势点的方法,通过从数据集采样优势点候选集,对其进行评估,选取其中区分度大的点作为优势点;然后提出构建多棵VP树的新方法,改进距离优势点远的子树中最近邻不紧凑问题;接着提出使用优先队列与剪枝搜索方法结合的新搜索方法查找最近邻,减少了很多不必要的距离计算。最后通过实验结果表明,本文方法在数据维度、数据集大小、返回不同邻居个数、不同的距离函数及建树个数方面精度有了很大的提高。(本文来源于《北京化工大学学报(自然科学版)》期刊2017年05期）
何杰芳[6]（2016）在《无线传感器网络中分布式近似相似性搜索算法研究》一文中研究指出随着智能终端技术的迅速发展以及应用领域的不断扩展,无线传感器网络感知数据的种类和数量也快速增长,而其中的图片、视频等多媒体数据由于很好地满足了人们依赖视觉以及听觉获取信息的习惯,因此具有特别的研究价值。然而,由于无线传感器网络的感知数据量过于庞大,如何高效地搜索这些多媒体数据就成了一个重要的研究课题。近似相似性搜索是传统数据库中应对海量高维数据搜索的有效手段,其通过牺牲少量的算法准确度来提高算法效率,在高维数据搜索领域展现了很好的性能。传统数据库中近似相似性搜索的研究已经取得了巨大的进展,大量的近似相似性搜索算法被提出并得到了广泛的应用。然而无线传感器网络的感知数据除了呈现海量高维的特性以外,还呈现出随机散布的特点,传统数据库中集中式的近似相似性搜索算法无法满足无线传感器网络的分布式特性,因此需要一种有效的手段来实现无线传感器网络下的海量高维数据搜索。论文在研究了传统数据库中的近似相似性搜索算法的基础上,结合无线传感器网络的特性,提出了一种适用于无线传感器网络的分布式近似相似性搜索算法。算法依据局部敏感哈希技术的基本思想,采用过滤-验证的框架,利用低维的数据指纹代替高维数据进行相似性判断,有效地降低了无线传感器网络中相似性搜索的通信能耗。同时,算法引入相似性打分机制,利用数据指纹的相似程度对数据进行相似性打分并依据打分结果对数据进行筛选,有效地提高了近似相似性搜索的精度。最后,通过仿真证明算法能够有效地适应无线传感器网络的分布式环境,且相对于传统算法,论文的分布式近似相似性搜索算法能够有效地提高相似性搜索的准确度并降低无线传感器网络的数据通信能耗。(本文来源于《南京邮电大学》期刊2016-11-18）
王敏,潘永春,李想,陈芬,傅质馨[7]（2016）在《基于改进相似性搜索算法的短期风速预测》一文中研究指出风速及其波动特性的预测对包含风电场的电力系统运行有着重要意义,可以有效地减轻或避免风电对电力系统的不利影响,从而提高风电在电网中的渗透功率,提高电力系统的风电消纳能力。依据对风电波动性和变化趋势性进行的分析,提出采用改进相似性搜索法选择待预测数据的时序神经网络的训练样本,基于我国沿海某风场的风速预测算例表明该方法有效地提高了模型的预测精度,扩大了模型的预测范围,强化了模型的适应性。(本文来源于《陕西电力》期刊2016年03期）
余文森,吴薇[8]（2016）在《基于随机匹配的非局部相似块搜索算法》一文中研究指出针对非局部相似块搜索问题,提出一个基于随机匹配的k近邻块匹配算法.在基于Jump Flooding传播的块匹配算法基础上,改进其候选参考块的产生方式,增加从查询块的局部邻域中随机产生候选参考块这一方式.这一改进提高了候选参考块匹配的可能性,进而提高了算法的匹配精确度.实验结果表明改进算法在时间效率和并行性上,与原算法相差不大,但在匹配精确度上,要优于原算法.(本文来源于《计算机系统应用》期刊2016年03期）
王会青,孙宏伟,张建辉[9]（2016）在《基于Map/Reduce的时间序列相似性搜索算法》一文中研究指出将并行计算的策略引入到时间序列处理中,提出基于Map/Reduce的时间序列相似性搜索算法,充分利用云计算可进行大规模计算和数据处理的特点,有效降低了时间序列相似性搜索中运算量,简化了计算过程。该算法在心电图数据集上进行相似性搜索,分别进行PAA下界过滤和DTW距离的计算,验证运算时间和并行加速比随节点变化的情况,与传统的单机运算相比,有效地提高了时间序列挖掘效率。(本文来源于《山东大学学报(工学版)》期刊2016年01期）
杨健[10]（2015）在《基于编辑距离字符串Top-k相似性搜索算法的研究》一文中研究指出字符串相似性搜索在众多的领域具有广泛的应用,例如:数据清洗、数据集成、拼写检查、抄袭检测、生物序列分析等。到目前为止,有很多度量标准用来衡量字符串之间的相似程度,然而众所周知不存在一个相似性函数在所有领域中都具有最好的性质,编辑距离是所有被广泛接受的相似性函数中的一个。因此本文通过编辑距离表示两个字符串之间的相似程度。一般而言,字符串相似性搜索主要有两种类型:范围查询和Top-k相似性搜索,本文主要研究Top-k搜索问题,即给定一个查询字符串q,Top-k搜索返回字符串集合S中k个字符串,满足这k个字符串和查询字符串q的编辑距离最小。现如今解决字符串Top-k相似性搜索共有叁类算法,AQ和Appgram基于n-gram模型,但这两种方法忽略了n-gram的位置信息,同时AQ算法需要对不同长度n-gram建立多个索引导致很低的效率,Appgram不是精确查询,往往会丢失结果,Bedtree算法基于B+树结构,由于过滤条件过于宽松导致遍历过多节点,Range算法和Hstopk算法针对短字符串很有效,当处理长字符串集合时,为了提高查询性能,这两种算法需要很大的额外内存空间。针对现如今方法的缺陷,本文基于n-gram模型,结合n-gram位置信息,设计了新的倒排索引结构,在这个新的索引结构上设计了新的顺序搜索和改进的循环搜索算法;在过滤阶段,加入了长度过滤,数量过滤和位置过滤,同时加入了新的过滤方式频率过滤,实验证明频率过滤可以进一步过滤掉大量候选字符串;同时本文针对top-k查询的初始化进行了研究,结合字符串集合整体统计信息,将字符串集合分类,采用和查询字符串同一类的字符串进行初始化;最后设计了基于磁盘的索引构建和查询方法;最后本文在叁个真实数据集上进行了多组对比实验验证本文提出算法的高效性,首先测试各种算法在这叁个真实数据集上内存消耗,然后比较了各个算法查询性能,同时对索引的两种构建方式,两种搜索策略,堆的四种初始化算法进行了对比实验,然后对基于磁盘索引构建时间和查询性能进行了测试,最后对长度过滤策略和频率过滤策略进行了测试,通过多组实验证明了本文提出算法的高效性。(本文来源于《哈尔滨工业大学》期刊2015-06-01）
相似搜索算法论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
针对时间序列相似性研究中存在动态时间弯曲DTW复杂度过高与分段思想易造成特征丢失的问题,提出了一种基于形状和升降性提取序列数据重要特征点的DTW相似性搜索算法,利用关键特征点快速筛选相似候选子序列集合,计算各个原始子序列的DTW距离,与改进的分段DTW距离度量方法进行实验比较。结果表明,该方法提高了相似性搜索效率,并具备更高的相似度。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
相似搜索算法论文参考文献
[1].陈晓阳.大规模图数据库的相似性搜索算法研究[D].西安电子科技大学.2019
[2].褚蓉,钮焱.基于形状特征的DTW距离相似性搜索算法[J].软件导刊.2018
[3].董肖凯,方宏舰,周波.区间映射规则下的时间序列相似形态搜索算法——基于改进的正则化损失函数[J].价值工程.2018
[4].冯欢.高性能相似性搜索算法与优化关键技术研究[D].清华大学.2017
[5].姜大光,孙贺娟,易军凯.基于距离的相似最近邻搜索算法研究[J].北京化工大学学报(自然科学版).2017
[6].何杰芳.无线传感器网络中分布式近似相似性搜索算法研究[D].南京邮电大学.2016
[7].王敏,潘永春,李想,陈芬,傅质馨.基于改进相似性搜索算法的短期风速预测[J].陕西电力.2016
[8].余文森,吴薇.基于随机匹配的非局部相似块搜索算法[J].计算机系统应用.2016
[9].王会青,孙宏伟,张建辉.基于Map/Reduce的时间序列相似性搜索算法[J].山东大学学报(工学版).2016
[10].杨健.基于编辑距离字符串Top-k相似性搜索算法的研究[D].哈尔滨工业大学.2015