导读:本文包含了图索引论文开题报告文献综述及选题提纲参考文献，主要关键词:图数据库,分类过滤,图索引,子图匹配查询
图索引论文文献综述
白浚楼[1]（2015）在《基于分类的图索引方法研究》一文中研究指出随着图结构在复杂数据建模方面的广泛应用,图数据库技术得到了快速发展。如何从图数据库中快速检索数据已经成为一个研究热点。在图查询中,子图匹配查询和相似性查询是两种重要的查询方式。子图匹配查询是指返回数据库中包含查询图的图集合,而相似性查询是返回数据库中与查询图相似的图集合。处理子图匹配查询和相似性查询时,分别需要进行子图同构验证和图相似度计算,但子图同构验证和图相似度计算已经被证明是NP难题。为了快速有效地返回图查询的结果,目前主要采用“分类过滤+验证”两阶段处理机制。在这种机制中,首先预定义分类过滤规则,将图数据库分类,然后提取查询图特征,找到结果可能出现的类别,从而生成规模较小的候选集,最后对候选集进行子图同构验证或者图相似度计算得到最终的结果集。其中,人们可以根据分类过滤规则构造合适的图索引来提高查询效率。现有的用于处理子图匹配查询的图索引方法中,一般都是在查询前离线建立图索引,而忽视了查询图序列在时间上的相关性,容易出现冗余查询；已有的相似性查询的图索引方法主要集中在减少相似度的计算时间,而并没有提出一种缩小候选集规模的方法,仍需扫描整个数据库才能得到结果集。针对以上子图匹配查询问题,本文提出了一种双索引的方法。其主要思想是：首先采用传统方法,基于图数据库离线建立图索引DIndex(Database Index);然后在查询过程中,在线实时建立图索引HIndex(History Index)。HIndex中存放的是根据查询热度得到的一组频繁查询结构。这样当某些图被重复查询时,可以首先搜索HIndex,如果搜索成功,即可直接得到结果集,从而避免子图同构验证；如果搜索失败,则可按照传统方法搜索基于图数据库建立的索引DIndex,得到候选集。为了缩小相似性查询问题中候选图的规模,本文提出了一种多层过滤方法,并针对于不同的过滤层,分别提出了相适应的索引结构。首先将查询图的规模信息和顶点标签信息与图数据库中的图进行比较,将高偏差的图剔除；然后利用本文提出的基于子图向量异或乘积的计算方法得到一个有序集合,使得可能满足查询要求的图聚集在该集合的前半部分：之后本文采用类似二分查找的方式,通过计算映射距离,动态调整得到一个合适的下标值,使得可能满足要求的图都出现在该下标的左侧,这样就可以将该下标左侧的图直接加入到候选集；为了提高结果集的查全率,有序集合中出现在下标右侧的图也有一部分被选入候选集。最后,通过计算候选集中的图编辑距离,返回满足查询要求的图集合。最后,本文通过实验验证了双索引方法和多层过滤方法在子图匹配查询和图相似性查询中的有效性。在子图匹配查询的实验中,本文采用不同密度的查询序列进行查询,得到双索引方法和传统单索引方法以及无索引方法在不同情况下的平均子图同构次数。分析实验结果发现,随着查询密度的增大,双索引方法中子图同构验证的次数与已有的两种经典方法相比明显减少,从而提高了查询效率。在相似性查询实验中,本文分别从索引建立时间,索引大小以及索引性能以及查全率四个方面将多层过滤方法与已有的Closure-Tree方法进行对比。实验结果表明,多层过滤方法在索引建立时间、索引大小和查询时间上都优于Closure-Tree方法的同时,又能保持95%左右的查全率。(本文来源于《东南大学》期刊2015-06-01）
皇甫中民,张树生[2]（2015）在《基于图索引过滤机制的叁维CAD模型局部检索》一文中研究指出针对现有叁维CAD模型局部检索方法效率低、难以满足工程实际需要的问题,提出一种基于图索引过滤机制的叁维CAD模型局部检索方法。依据模型的B-Rep表示形式,提取其必要的几何拓扑属性等信息,将叁维CAD模型用属性邻接标记图表示;依据图的谱理论为属性邻接标记图及其各节点的局部结构进行编码,提出引理以论证模型局部匹配需满足的必要条件,并据此提出一种两层过滤的策略,构建了一种图编码索引结构;模型局部检索采用过滤—验证的思想,先依据提出的索引和过滤策略剪枝不符合规则的模型,再对候选集中的模型采用子图匹配的方法进行验证并输出。实验结果表明,所提方法在保证检索质量的基础上能够显着提高局部检索的效率,可满足工程检索的实际需要。(本文来源于《计算机集成制造系统》期刊2015年07期）
刘雅辉,刘春阳,张铁赢,程学旗[3]（2013）在《图索引技术研究综述》一文中研究指出随着信息技术和网络技术的发展,图作为一种通用的数据结构被用于不同学科建模各种实体以及实体之间的关系。图中各实体间隐藏了很多有价值的信息,为了挖掘图中隐藏的这些信息,图的相关研究成为了各领域的研究热点,但在大多数图研究中最关键的问题是如何有效地进行图查询。在图数据库中存在着两种图数据集:单图和图集。针对单图或图集进行图查询是相当费时的,为了加快图查询速度,图索引成为各种图查询算法的研究重点,而图索引的焦点在于利用图索引的结构模式来最小化搜索空间的大小。本文将图查询归为两种:子图查询和超图查询。在每种查询中,依据图索引建立时选择的图结构特性进行了细分,主要集中于图索引的构建思想,并对典型的索引方法进行了详细的叙述。针对不同的图索引分析了各自的优缺点,并比较了各种索引方法的特点。最后,总结并探讨了图索引的发展趋势。(本文来源于《山东大学学报(理学版)》期刊2013年11期）
赛娜（Zainab,Qays,Abdulhadi）[4]（2013）在《位图索引在数据仓库低基数值列中的研究》一文中研究指出在数据仓库和商业智能(BI)解决方案中加快查询处理是一个急需解决的问题。使用汇总表或索引等机制可以有效提高查询速度,其中预定义查询的汇总表已具有较好的性能,但需要预先花费额外的执行时间,而索引是一个更加高性能的且无需额外硬件的解决方案,但其中面临的挑战是如何找到一个合适各种数据集且都保持较高性能的索引类型。低基数数据在数据仓库中应用广泛,基数是一个数据集的列中值的个数。一般有大量重复值的列称作为低基数列,例如性别列,一般只有两个值：男性和女性,当然可以用其它的2个不同的符号来表示。B树是存储排序数据并允许以O(logn)的运行时间进行查找的树形数据结构,但B树索引应用于低基数值列时是一个非常低效的索引方法,在进行即席查询且数据量大时需要非常多I/O操作。因此一些关系型数据库管理系统采用新的索引技术,如位图索引,用以加快查询处理。位图索引有一个用于快速数据检索的特定结构,主要是利用二进制数(0或1)的字符串,以指示一个表中被索引的列是否为一个特定的值,也就是说,如果在一个索引列中一个特定的值存在,位图索引设置为'1',否则为'0'。与其它的索引技术相比,位图索引能大幅减少空间的使用,对于复杂逻辑的选择操作,可通过执行位的运算"AND","OR","NOT"等来快速地完成。位图索引的应用非常广泛,主要用于数据仓库系统和大型科学数据库。通过执行跨列位图间的快速逻辑运算,位图索引提供了一个更快的查询解决,而且能被被当代硬件广泛支持。很多商业的数据库系统都采用位图索引,如Oracle,从1995年开始就提供了位图索引,其它主要系统如DB2和Microsoft SQLServer没有采用。Microsoft SQL Server可能通过哈希连接生成位图,但不是通用的索引。DB2已经采用编码矢量索引,但是这基本上是一个编码投影索引,而不是一个位图索引。本论文的目的是通过实验的方式来证明在数据仓库中位图索引比B树索引更有效,尤其是对于低基数值列。在Oracle环境中,B树索引一般为默认的索引方式。我们通过3个典型的实验来测试在两个索引方式下复杂查询的执行时间,在每一个实验中我们分别测试3个条件、2个条件与1个条件的查询,并且测试4个不同的数据集,分别有100万条、80万条、60万条、30万条记录。我们首先在Oracle环境下设计并实现图形用户界面,采用Oracle Developer6i工具套件,这个套件由许多用于开发和编程项目的软件组成,这些软件以可视化的方式来处理数据仓库并操纵数据库。这意味着,使用可视化编程组件,如按钮、列表、标签、文本框、鼠标移动等等,无需复杂编程即可编写查询并以图形界面的方式呈现结果。我们使用Oracle lOg的数据库来创建表和索引。我们设计与实现的界面有2个主要部分即搜索使用位图索引、搜索使用B树索引,这2个部分具有相同的查询语句与数据集。我们在查询项目中的选择的参数选项有地区、学院、性别和年龄。当要执行查询时,我们首先确定搜索选项,即相当于在SQL语中复杂的“Where子句”条件,每个选项所代表的组合列表是通过鼠标左键点击下拉列表选择值进行组合。在每次实验中,我们对位图索引与B树索引的查询响应时间进行详细记录与比对,从而揭示在不同数据集与不同列值情形下两个索引方法的性能差别。实验主要包含以下叁个方案：方案一：搜索表使用叁个条件,其中有两个AND运算操作。搜索上分别做4组记录,30万条、60万条、80万条与100万条记录。方案二：搜索表使用两个条件,即一个AND运算操作,搜索上分别进行4组记录,30万条、60万条、80万条与100万条记录。方案叁：搜索表使用一个条件,搜索记录4组,分别30万条、60万条、80万条与100万条记录。我们用许多不同的查询参数来测试不同SQL查询以获得更多的结果进行较为全面的分析。从叁个实验方案进行观察发现,位图索引在对于低基数值列如“Y”或“N”、“男”或“女”等比B树索引速度优势明显。但是位图索引只是方便静态表(无更新)的查询,如果查询的表不是只读的,则B树索引是一种相对有效的选择。位图索引对于决策支持系统、数据仓库、OLAP等数据相对静态的情形非常有效,而B树索引则对于OLTP环境更有效。已有相关研究将位图索引和B树索引的时间和空间复杂性计算规则进行了分析,数学计算表明位图索引的时间和空间复杂性比B树索引低,尤其是对于低基数值列。对于大型数据仓库来说,位图索引被认为是在当前和未来很有发展前途的索引,因此我们期待提出更有效的位图索引方法。我们的目标是通过采取新的方法来提高位图索引的性能,这个方法的主要思想是将基本的位图索引算法和基于值域编码算法进行有效结合,考虑不同的基数值列类型。在基于值域编码算法(是基本的位图索引算法的改进)中,位图矢量用于表示一定范围内的值,而不是一个单独的值。查询处理器读取该位图矢量中的对象,并删除那些超出目标范围的对象。此方法的主要优势是提高了位图索引性能的效率,通过减少位图矢量所需的扫描时间,特别是当我们处理一定范围内值的时候,通过将值域分割成更小的域用以显着减少存储开销。基本的位图索引的想法是使用一个字符串的比特0或1,以指示是否一个元组的属性值为某一个特定值,其主要优势是逻辑运算能很好的被硬件支持,操作的执行都相当快。而且,用于构造位图索引的成本及其根据位图进行查找的成本都非常低。然而,简单的位图索引只对具有低数量不同值的属性才有效,因为,如果索引的属性的基数值低,则需要一个较小的数字位图,索引结构的空间复杂度低,而对于高基数值属性,则需要一个很大的数字位图,索引结构的空间复杂度高、时间性能也低,这成为基本位置索引算法的明显缺陷。我们通过观察发现,基于值域编码算法由于可以将某一范围数值归类到某一个值,对于高基数值属性,可以处理成相对规模较小的数字位图,从而可以克服基本索引算法的缺陷。因此我们提出把基于值域编码算法和基本位图索引算法进行有效结合,通过引进相异值比率参数并对列进行自动计算,在相异值比率较高即不同的值多称之为高基数值属性时采用基于值域编码算法,当相异值比率低即称之为低基数值属性时采用基本位置索引,如果相异值比率超过一定值时,则采用B树索引。通过引入数学方程式并使用二项式概率分布规则,我们对提出的混合索引方法的时间复杂性进行了分析,结果表明新方法的时间复杂性将低于单独使用基本位图算法,在最坏的情况下将和基于值域编码算法的时间复杂度相同。本论文包含五个章节,第一章叙述位图索引的引言和相关工作。在第二章中,我们提出了B树索引和位图索引的概述和一些相关的索引技术及各个索引的优势和劣势。在第叁章中,我们阐述了oracle developer的方法和关键技术和SQL数据库中创建表和索引的过程,在第四章中,我们描述了叁个实验的实施完成,并阐明结果的讨论和每个索引的时间和空间复杂度,由于我们提出把基本位图索引与基于编码的范围结合起来的方法,最终提高了位图索引的效率。第五章介绍了结论和未来的工作。(本文来源于《中南大学》期刊2013-07-01）
邹晓红,郭聪敏,郭景峰[5]（2013）在《一种有效的图索引查询算法》一文中研究指出图是一种很强大的工具,在许多应用领域如化学化合物,生物信息,XML文档,图像处理和社会网络等应用中它可以表示其对象及它们之间的关系,而且在模式化复杂的结构数据时图发挥了越来越重要的作用.图的一个最基本的操作是图的查询处理,经典的图查询问题是给出图数据库和一个查询图,从图数据库中找出那些包含查询图作为子图的图.在本文中对于给定的查询图提出了一种有效的索引策略,在图数据库中选取具有判别力的树作为特征树,对这些特征树进行编码,将结构之间的比较转化为编码序列之间的比较,并利用特征树建立索引,提出了两种剪枝策略,过滤掉数据库中与查询图不是精确匹配的图.实验验证了所提出查询处理算法的有用性和有效性.(本文来源于《小型微型计算机系统》期刊2013年02期）
汪辉,魏书堤,梁小满[6]（2013）在《位图索引在数据仓库性能优化中的应用(英文)》一文中研究指出检索性能的优劣在数据仓库应用中是至关重要的,位图索引在性能优化中起关键作用之一,并且它和传统的B树索引是不同的。通过实例描述了位图索引的构成原理,即:位图索引是由一系列有序的位向量组成;详细阐述了位图索引的特性(包括优点和缺点)以及其使用条件。最后文章结论指出合理地使用位图索引可以极大地改善大型系统的检索效率和减少系统资源。(本文来源于《电脑知识与技术》期刊2013年02期）
程鹏[7]（2010）在《位图索引技术及其研究综述》一文中研究指出位图索引是一种新兴的索引技术,特别适合于只读性海量数据的索引。本文对现有各种位图索引进行了分类,介绍了BBC、WAH、范围编码、区间编码、分箱和基于Bloom Filter编码的位图索引压缩和查询技术。比较了各种位图索引的空间和时间复杂度,讨论了如何根据数据的特性选择合适的位图索引,并指出位图索引的未来研究问题和方向。(本文来源于《科技信息》期刊2010年26期）
王黎明,程晓,柴玉梅[8]（2010）在《基于Bin位图索引的多维查询优化算法》一文中研究指出在属性基数(该属性可能的取值数)很高的情况下,简单位图索引需要占用太大存储空间。Bin位图索引可以很好解决这个问题。这种索引不像简单位图索引那样建立在不同的属性值上,而是建立在属性范围上,但候选检查往往占用大部分的查询时间。为了提高查询性能,提出一种排序方法来对各属性进行排序,以减少候选检查数目,并在此基础上提出动态预扫描算法。实验结果表明,排序和动态预扫描算法都取得了良好的效果。(本文来源于《计算机应用》期刊2010年08期）
宋杨,张杨[9]（2009）在《利用AutoCAD二次开发技术建立电力竣工图索引》一文中研究指出利用AutoCAD二次开发技术,对电力竣工图进行整理,建立有效索引,通过索引图可方便查看电力竣工图。(本文来源于《城市勘测》期刊2009年04期）
李楠[10]（2009）在《图索引技术新方法》一文中研究指出随着结构化数据在互联网应用中的大量出现,对复杂数据进行图建模在近年来越来越流行。图索引问题在图数据库应用中至关重要。本文主要研究了图数据库上的图索引问题。本文提出了MSTA索引方法及MSTA索引方法上的子图查询算法、超图查询算法、相似性查询算法和相关性查询算法。MSTA索引方法利用最小生成树作为数据特征,将所有的最小生成树依据边序列的包含关系和最大公共子图距离度量组织成MST树索引结构,高效的支持各种查询算法。传统索引方法的索引大小和索引建立时间是MSTA索引方法的数十倍,甚至上百倍。MSTA索引方法上的查询算法都是近似的,返回的结果是最好的部分结果。我们还分析了MSTA索引方法的原理和正确性。实验结果辅证了该索引方法的高效索引性能及查询性能。本文提出了RQ索引方法及RQ索引方法上的相关性查询算法。我们分析了相关性查询算法的代价组成,从而得出代价影响的两个结论;分析了已有索引方法在支持相关性查询上的不足。RQ索引方法,利用四种不同维度选择策略得到高维空间矩阵作为数据特征,将所有的高维空间矩阵组织到R树索引结构中。实验结果表明,RQ索引方法具有优秀的索引性能,并具有很好的可扩展性。RQ索引方法可以高效的支持相关性查询。(本文来源于《哈尔滨工业大学》期刊2009-06-01）
图索引论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
针对现有叁维CAD模型局部检索方法效率低、难以满足工程实际需要的问题,提出一种基于图索引过滤机制的叁维CAD模型局部检索方法。依据模型的B-Rep表示形式,提取其必要的几何拓扑属性等信息,将叁维CAD模型用属性邻接标记图表示;依据图的谱理论为属性邻接标记图及其各节点的局部结构进行编码,提出引理以论证模型局部匹配需满足的必要条件,并据此提出一种两层过滤的策略,构建了一种图编码索引结构;模型局部检索采用过滤—验证的思想,先依据提出的索引和过滤策略剪枝不符合规则的模型,再对候选集中的模型采用子图匹配的方法进行验证并输出。实验结果表明,所提方法在保证检索质量的基础上能够显着提高局部检索的效率,可满足工程检索的实际需要。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
图索引论文参考文献
[1].白浚楼.基于分类的图索引方法研究[D].东南大学.2015
[2].皇甫中民,张树生.基于图索引过滤机制的叁维CAD模型局部检索[J].计算机集成制造系统.2015
[3].刘雅辉,刘春阳,张铁赢,程学旗.图索引技术研究综述[J].山东大学学报(理学版).2013
[4].赛娜（Zainab,Qays,Abdulhadi）.位图索引在数据仓库低基数值列中的研究[D].中南大学.2013
[5].邹晓红,郭聪敏,郭景峰.一种有效的图索引查询算法[J].小型微型计算机系统.2013
[6].汪辉,魏书堤,梁小满.位图索引在数据仓库性能优化中的应用(英文)[J].电脑知识与技术.2013
[7].程鹏.位图索引技术及其研究综述[J].科技信息.2010
[8].王黎明,程晓,柴玉梅.基于Bin位图索引的多维查询优化算法[J].计算机应用.2010
[9].宋杨,张杨.利用AutoCAD二次开发技术建立电力竣工图索引[J].城市勘测.2009
[10].李楠.图索引技术新方法[D].哈尔滨工业大学.2009