导读:本文包含了频繁子图查询论文开题报告文献综述及选题提纲参考文献，主要关键词:大规模动态图,标签约束,聚合划分,Top-K查询
频繁子图查询论文文献综述
单晓欢,王广香,宋宝燕,丁琳琳,许岩[1]（2018）在《大规模动态图中标签约束的频繁子图Top-K查询》一文中研究指出Top-K子图查询作为重要的图搜索技术,因可更具针对性地为用户返回查询结果而被广泛应用于社交网、生物信息网等新兴领域。随着图规模增大且动态演变,用户通常希望通过增加约束条件而快速、准确获得查询结果。鉴于上述查询需求,提出了一种标签约束的频繁子图Top-K查询方法(LVC-FS Top-K)。该方法通过建立频繁结构映射与标签值聚合的二级索引(FSM-LVA),快速准确地锁定查询图结构并根据约束限制剪枝过滤,缩小查询范围,提高查询效率;利用FSM-LVA索引对同构于查询图的频繁结构进行查找以实现频繁结构查询,同时结合查询图的约束条件及K值限制对频繁子图进行匹配筛选,缩小比较空间,加快查询效率。实验结果表明提出的方法能快速准确地在大规模动态图中进行具有约束限制的频繁子图Top-K查询。(本文来源于《计算机科学与探索》期刊2018年11期）
白同贺[2]（2017）在《基于频繁子图的图查询技术研究》一文中研究指出随着计算机科学与技术的发展,图数据结构在各个领域内得到广泛应用。图数据管理和查询已经成为一种研究热点。其中,图查询的基本方式分为子图匹配查询和图相似性查询。子图匹配查询返回图数据库中包含查询图的数据图,图形似性查询返回在一定的距离范围内与查询图相似的数据图。在这两种查询中,分别需要图同构验证或相似度的计算,这两种计算都已被证明是NP困难的,因此提升查询的性能也只能是最大化过滤掉非结果集。目前,对于这两种查询的优化,主要是基于过滤验证机制,即在查询时通过查询图的特征过滤掉不符的数据图,得到规模较小的候选集,然后对候选集进行同构验证或者相似度的计算。其中,一般选用图集中的频繁子图作为特征进行过滤,因为其保留了全局的结构信息,过滤性更强。在子图匹配查询问题中,现有的方式一般是通过图集中的特征建立索引,在查询时对查询图进行边扩展的方式得到相应的候选集。此方式在进行查询时的时间复杂度较高,并且没有充分利用查询图包含的特征进行索引的过滤,为此,本文提出了一种利用节点邻接特征进行过滤的索引结构Vindex。针对特定的领域,考虑图集特征之间的位置关系,结合用户的查询记录,提取其中较为有价值的特征位置关系,建立了基于嵌入特征关系的索引结构,用于减小候选集的大小。并提出利用特征之间的包含关系以及特征与数据图之间的关系,在一定程度上对索引项和候选集进行缩减。在图相似性查询问题中,现有的方法大多致力于减小编辑距离的计算时间,而对于缩小候选集规模没有提出合适的索引结构和查询过滤方法。本文结合编辑距离的概念和查询图的结构特征,对图集之中的数据图进行过滤,将相差度较大的图剔除。然后利用子图向量异或乘的方式对图进行聚集,将于查询图较为相似的图聚集在候选集中的前一部分,然后利用分支映射距离结合动态调整的方式得到一个较为精确的候选集。在验证阶段,利用图之间的编辑距离关系,建立了基于编辑距离的索引GDindex,在验证时首先与在索引之中的图进行计算,然后利用查询图和索引图的编辑距离关系,对候选集中的其他数据图进行处理,通过此种方式的处理可以减小最终的编辑距离计算的次数。最后,本文设计了验证实验,在真实Pubchem数据集上进行实验,分别从索引的建立时间、候选集大小和查询运行时间叁个方面与现有方法比较。实验结果表明,与现有的方法进行相比,本文提出的方法有效可行,可以提升查询性能。(本文来源于《东南大学》期刊2017-05-31）
许岩[3]（2017）在《基于频繁子图的大规模动态图约束top-k查询方法研究》一文中研究指出图数据作为一种有效描述现实世界各类实体及其关系的手段,被应用在生物分子网络分析、社交网络处理、智能交通和云数据处理等众多领域。近些年,随着信息技术的飞速发展,图所代表的实体数目的增加导致图的规模不断变大,同时实体间关系的变化导致图的频繁更新,因此针对大规模动态图的处理研究十分重要。图数据的top-k查询是图数据处理领域的重点研究,中小规模图数据的top-k查询已经日益成熟,然而现有的算法在处理大规模图时大都存在难以进行图结构匹配的问题,同时具有约束条件的图数据top-k查询的相关研究相对较少。针对上述问题,本文提出基于频繁子图的大规模动态图约束top-k查询方法(frequent subgraph based constraint top-k query,FSCtop-k)。该方法处理约束语义的图数据top-k查询,首先在初始数据图的基础上,建立频繁子图索引和标签值聚合索引;其次,查询时,针对查询图频繁和非频繁,分别给出查询方法,在索引上筛选后,在较小的候选子图集中找到约束top-k的查询结果;最后,针对大规模动态图的特性,给出动态图的更新策略,通过公共节点分析、设置监视变量和预留极大、极小索引项的方法解决动态更新问题。该方法提出解决约束语义的图数据top-k查询,在索引上查询时通过两次剪枝比较次数,控制候选子图集的范围,具有良好的可行性和查询效率。本文的主要内容可概括如下:(1)提出约束语义,提出图数据的约束top-k查询概念,在普通图数据top-k查询的基础上,增加约束条件限制。(2)提出建立频繁子图索引和标签值聚合索引。通过遍历数据图,挖掘初始数据图中的频繁子图的方法,建立频繁子图索引。建立标签值聚合索引解决约束top-k查询问题。通过算法,为节点标签值分配索引编号,将子图映射到索引中,为子图分配标记位,建立标签值聚合索引,并给出索引的分段密度计算方法,保证图的约束top-k查询的效率。(3)针对查询图频繁和非频繁情况,给出对应的约束top-k查询方法,在较小的候选子图集中找到约束top-k的查询结果。(4)针对大规模动态图的约束top-k查询问题,给出动态图的更新策略。首先确定定时更新的更新策略,其次提出在缓存器中进行边的公共节点分析、设置监视变量,解决图结构的变化,最后提出预留极大、极小索引项解决节点标签值变化导致的索引越界问题。(5)在模拟数据集和真实数据集上进行了实验,验证了本文方法在大规模动态图上实现约束top-k查询的有效性和可行性,且具有良好的查询效率。(本文来源于《辽宁大学》期刊2017-05-01）
频繁子图查询论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
随着计算机科学与技术的发展,图数据结构在各个领域内得到广泛应用。图数据管理和查询已经成为一种研究热点。其中,图查询的基本方式分为子图匹配查询和图相似性查询。子图匹配查询返回图数据库中包含查询图的数据图,图形似性查询返回在一定的距离范围内与查询图相似的数据图。在这两种查询中,分别需要图同构验证或相似度的计算,这两种计算都已被证明是NP困难的,因此提升查询的性能也只能是最大化过滤掉非结果集。目前,对于这两种查询的优化,主要是基于过滤验证机制,即在查询时通过查询图的特征过滤掉不符的数据图,得到规模较小的候选集,然后对候选集进行同构验证或者相似度的计算。其中,一般选用图集中的频繁子图作为特征进行过滤,因为其保留了全局的结构信息,过滤性更强。在子图匹配查询问题中,现有的方式一般是通过图集中的特征建立索引,在查询时对查询图进行边扩展的方式得到相应的候选集。此方式在进行查询时的时间复杂度较高,并且没有充分利用查询图包含的特征进行索引的过滤,为此,本文提出了一种利用节点邻接特征进行过滤的索引结构Vindex。针对特定的领域,考虑图集特征之间的位置关系,结合用户的查询记录,提取其中较为有价值的特征位置关系,建立了基于嵌入特征关系的索引结构,用于减小候选集的大小。并提出利用特征之间的包含关系以及特征与数据图之间的关系,在一定程度上对索引项和候选集进行缩减。在图相似性查询问题中,现有的方法大多致力于减小编辑距离的计算时间,而对于缩小候选集规模没有提出合适的索引结构和查询过滤方法。本文结合编辑距离的概念和查询图的结构特征,对图集之中的数据图进行过滤,将相差度较大的图剔除。然后利用子图向量异或乘的方式对图进行聚集,将于查询图较为相似的图聚集在候选集中的前一部分,然后利用分支映射距离结合动态调整的方式得到一个较为精确的候选集。在验证阶段,利用图之间的编辑距离关系,建立了基于编辑距离的索引GDindex,在验证时首先与在索引之中的图进行计算,然后利用查询图和索引图的编辑距离关系,对候选集中的其他数据图进行处理,通过此种方式的处理可以减小最终的编辑距离计算的次数。最后,本文设计了验证实验,在真实Pubchem数据集上进行实验,分别从索引的建立时间、候选集大小和查询运行时间叁个方面与现有方法比较。实验结果表明,与现有的方法进行相比,本文提出的方法有效可行,可以提升查询性能。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
频繁子图查询论文参考文献
[1].单晓欢,王广香,宋宝燕,丁琳琳,许岩.大规模动态图中标签约束的频繁子图Top-K查询[J].计算机科学与探索.2018
[2].白同贺.基于频繁子图的图查询技术研究[D].东南大学.2017
[3].许岩.基于频繁子图的大规模动态图约束top-k查询方法研究[D].辽宁大学.2017