基于索引的子图查询技术研究进展

施炜杰 董一鸿 王雄 潘剑飞

摘 要：图作为表示实体间的数据结构，在社区发现、生物化学分析、社会安全分析等数据关联性要求较高的领域有着广泛的应用。对于大规模数据下进行实时的图查询问题，通过构建合适的索引可以有效降低查询响应时间，提高查询精确度。首先介绍基于索引的子图查询算法的基本结构;然后按索引的构建方式将主流算法分为基于枚举的方法和基于频繁模式挖掘的方法两大类，分别从索引特征、索引结构、应用数据集等方面进行介绍和分析;最后对基于索引的子图查询算法面临的主要问题进行总结和分析，阐述了最新的分布式系统下图查询技术，并对未来趋势进行展望。

关键词：子图同构;索引;子图查询;频繁模式

中图分类号： TP391

文献标志码：A

Abstract： As a type of data structure representing entities， graphs are widely used in fields that have high requirements on data relevance， such as community data discovery， biochemical analysis and social security analysis. Focusing on the issue of real-time graph query operation under large-scale data， building a suitable index can effectively reduce query response time and improve query accuracy. The basic structure of index-based subgraph query algorithm was firstly introduced and then state-of-the-art algorithms were divided into two categories by construction method of index： enumeration construction and frequent pattern mining construction. Then these algorithms were introduced and analyzed from three aspects： index features， index structures and application datasets. Finally， main problems toward index-based subgraph query algorithm were summarized and analyzed， the latest query technology based on the distributed system was briefly described， and the future trend was forecasted.

Key words： subgraph isomorphism; index; subgraph query; frequent pattern

0 引言

随着信息技术的飞速发展，图结构用于展示实体与实体之间的关系，在生物工程领域[1-2]、社交网络[3]等领域具有广泛的应用。图查询作为图数据处理的基本操作存在于各类应用：在社会安全分析[4]中，将犯罪团伙的作案关系模拟成使用图结构表示的关系模型，应用社区网络分析，通过子图查询可以有效识别出高危团伙;人才推荐系统[5]中，依托于社交网络通过将团队间的协作关系构建成图模型，通过与需求相应的子图结构进行查询匹配为招聘公司提供个性化的人才推荐方案;生物化学领域的分析研究[6]中，将各类蛋白质或有机高分子构建为图模型，能为专业人员提供更高效、精确的分析工具。

图查询过程主要以模式匹配为主，面临着子图同构问题，该问题已被证明是NP-hard（Non-deterministic Polynomial-time hard）问题[7]，存在大量的计算;其次当图数据过大时，如果每次查询都对数据集作一次遍历开销过大。通过构建索引能有效降低查询过程中的计算量。

索引查询主要可以分为过滤和验证两部分[8]：过滤是通过索引特征对数据集进行剪枝操作，并返回与查询图相似的候选集;验证是通过子图同构来对候选集进行验证最终返回查询的答案集。

因此图索引面临的主要有以下几个问题：1）构建索引的整体时间;2）查询返回答案集所需时间，其中包括过滤操作的计算时间和验证答案集的计算时间;3）索引大小，尤其在大图下索引能否放入内存;4）索引表的扩展性等。

1 基本概念

2 基于索引的图查询技术

传统的图查询操作，通过遍历数据集依次与查询图进行子图同构测试。由于子图同构本身就是NP-hard问题，加上庞大的数据量，其时空开销过大，不能满足实际的生产要求;而通过构建索引表能有效过滤与查询图不相关的图，减少子图同构的测试次数，大幅度降低查询时间。索引查询的整体时间复杂度[9]可以用式（1）来表示：

其中：Tresponse為一次查询返回答案集的时间，Tsearch为索引时间，TisSubG为子图同构时间，TI/O为算法在硬盘中对候选集Cq作I/O操作的时间。子图同构是NP-hard问题，计算时间复杂度较高，所以Cq·TisSubG占据Tresponse中很大一部分时间，因此索引设计需求主要集中在优化候选集的大小，减少验证阶段子图同构的计算次数，提高查询性能。

2.1 查询算法的基本结构

近年来面对图查询中的各类问题，相关学者提出了各种解决方案。基于路径特征的索引查询算法，适用于快速建表，索引大小的可控性强，适用于分布式环境下的索引搭建，但查询结果的精确度较低，结果存在大量的假阳（False Positive， FP）例;基于图或者树特征的索引查询算法，特征具有良好的剪枝效果，查询响应快，适用于需要快速查询，且结果精确度较高，主要通过频繁模式挖掘，但索引构件开销大，并且空间消耗不可控，因此也有通过迭代挖掘[10]的方式取代一次建表的，在一定的容错情况下，使目标函数不断逼近实际值，来降低索引构建过程中的时空消耗。通常图索引算法分为三个步骤[11]：1）索引构建;2）查询;3）答案验证。

2.1.1 索引构建

在索引构建阶段，算法主要从数据集中提取特征，并通过适当的数据结构构建索引表，主要面临两个问题[12]：1）索引特征的挖掘速度;2）索引特征是否具有良好的剪枝性。两者之间的关系成反比。常用的索引特征主要有：1）路径[13-18];2）树[19-21];3）图[22-24];4）多特征的混合结构[25-29]。特征的获取方式有：1）枚举获取数据中的所用特征;2）频繁模式挖掘获取数据集中的索引特征。

2.1.2 查询

查询阶段也称之为过滤阶段。首先将查询图序列化与索引表中特征进行匹配：如果完全匹配，则返回相应特征的ID;否则，将查询图分解成小片段系列化后再与索引表中特征进行匹配，产生一组可能包含查询图的候选集。在大多数算法中，候选集为查询图包含的各个片段的映射集的交集。对于存储位置信息的索引算法，可以迅速定位片段在索引表中的位置，实现快速查询。

2.1.3 答案验证

在查询阶段返回的候选集中可能存在与查询图不完全匹配的图，因此对候选集作验证操作以提高查询结果的质量是十分必要的。该过程主要是将候选集中的图与查询图进行子图同构测试，相应的匹配算法有Ullmanm[29]、VF2[30]等，现今的索引算法中主要使用VF2算法进行子图同构检测，也有部分算法使用自定的算法进行检测。

针对上述三个步骤中，各类算法间的差异主要区别于索引构建过程的构建方式，查询过程都遵循过滤+验证原则，因此下文从索引的构建方式出发，将现今主流的图索引算法分为基于枚举和频繁模式挖掘两类，作基本的阐述。

2.2 基于枚举的索引构建方法

基于枚举的索引构建没有针对某种特定标准筛选索引特征，而是索引了图集的所有结构。索引整体可控性强，构建快捷。索引特征主要以定长路径为主，也有部分算法针对图中的简单环和树结构进行枚举。算法遵循过滤+验证原则，优化主要集中在验证阶段。

2.2.1 gCode

gCode[13]基于谱图理论提出了针对顶点的编码方式，通过组合所有顶点编码来为每个图生成一个图编码。首先通过一个三元组〈L，N，top（S）〉作为顶点的辨识标签，其中L为顶点v自身的编码，N为顶点v的邻居节点的编码，top（S）是根据对以顶点v为根节点构建的路径树所有转换的矩阵取的前S个特征值，然后将顶点编码组合形成图编码，如图2为图1中图f13的gCode编码示意图。

在查询过程中，gCode首先将查询图按照上述的方式编码化，然后根据匹配顶点的辨识标签来对结果作剪枝处理，最后使用VF2算法对返回的候选集答案作剪枝操作。

2.2.2 GraphGrepSX

GraphGrepSX[14]适用于无向图，使用深度优先遍历（Depth-First-Search， DFS）算法枚举所有长度为k的路径，并存储在后缀树中。树中每个节点存储图的id列表以及出现在每个图中对应路径的次数。对查询图进行类似的分解与索引特征比较，剪枝掉与查询图不匹配的分支，根据节点中标签的出现频率进一步过滤，产生候选集，然后使用VF2进行验证得到答案集。图3为GraphGrepSX[14]对图1中f11深度遍历后形成的后缀树。

与GraphGrepSX[14]类似，Grapes[15]也是通过DFS形式枚举所有长度为k的路径，不同的是Grapes[15]是通过每个路径的起始节点id以及该路径在各个图中的计数信息维护位置信息;同时，Grapes[15]支持索引和查询处理过程的并行执行。索引中通过将节点巧妙地分配给线程完成，以便每个线程在不需要与其他线程同步信息同步的情况下完成计算任务。在查询过程中，查询图也经历了相同并行化的路径枚举和树结构处理，然后比较查询树与索引树，删除不匹配部分，通过保留的位置信息进一步过滤不必要的子图，最后进行子图同构测试得出答案集。此类索引适用于小量数据集。

2.2.3 Gstring

GString[16]算法主要针对生物化学类数据进行建模分析。不同于上述几个算法，GString更加注重于将图的结构语意嵌入至对图的简约表达中。该算法面向化学数据库的应用，提出了基于线型路径、星型以及环型结构的特征提取方法。给定一个图，依次提取所有的环结构、线型路径特征和星型特征，得到图的简约表示，最后通过DFS获取简约图的后缀树表示，作为查询索引。以类似的方式对查询图编码，通过后缀树得到查询候选集，最后使用VF2同构算法返回答案集。GString适用于小数据集的情况，当图集或查询图较大时，查询效率不高，主要用于生物高分子中化合物的分解分析。

2.2.4 CT-index

CT-index（index based on Cycle and Tree）[25]考虑到环结构对图结构的表达能力，将路径、树和环图作为索引构建的索引特征，依次枚举出数据图中所有的路径特征、树特征和环特征，并将这些特征组合规范化之后进行哈希编码，对每個图产生一个固定长度的fingerprint，针对树特征的规范化将树的重心节点确定为树的根节点。在查询阶段，同样将查询图规范化之后进行哈希编码的到一个固定长度的fingerprint;然后通过按位与操作将其与数据集中所有图的fingerprint进行比较，产生候选集;再利用改进的VF2算法对候选集作子图同构测试，得出答案集。

2.2.5 小结

基于枚举方式构建的索引如gCode、GraphGrepSX等结构简单，构建快捷，因此对索引结构的维护有着明显的优势，能适应数据频繁更新的情况，但是由于特征结构简单，过滤性能较差。在图1中，进行简单的查询操作，f14为查询图唯一的返回答案，但f8和f15不能通过路径特征的剪枝能力直接在索引阶段被过滤掉，因此查询返回的候选集较大。验证阶段是算法主要的瓶颈，类似的有GString、CT-index在枚举阶段通过对特定的树结构和环结构进行遍历，这也相应地增加了索引的构建时间。综上此类算法构建快捷，维护便捷，但查询的整体耗时与数据量不成线性关系，可扩展性较差，不适用于密度较高、结构复杂的图数据。

2.3 基于频繁模式挖掘的索引构建方法

针对基于枚举构建的图索引算法中过滤性能差、验证计算量大等缺点，基于频繁模式挖掘方式构建的图索引算法从索引特征的结构出发很好地解决了上述查询过程中的几个问题。算法主要思想是在频繁模式挖掘的基础上通过判别函数对频繁模型进行特征选择，将符合判别条件的模型作为索引特征保存在给定的索引结构中。在频繁模式挖掘中，特征的支持度是其映射集在整个数据集中的占比。如果特征的支持度高于阈值，该特征被认为是频繁的。特征的区分比是特征与其子特征之间修剪能力的度量。所有基于频繁模式挖掘的索引构建算法，基本思想都是为特征的区分比提供不同的度量方式。在索引构建中对每个特征进行序列化操作，将其映射集存入索引表中。部分索引构建算法保留特征位置信息，如路径特征的第一节点的IDid此处的ID，是否应该改为小写id，以便与2.2.2中的id书写保持一致？或者全部改为大写ID？请明确（用于定位路径的开始节点）、树特征的重心节点的IDid（用于标准化树型特征）等，最后將所有特征存储在算法给定的数据结构，如哈希表、前缀树或者图点阵中。

2.3.1 gIndex

gIndex[9]针对频繁模式挖掘中支持度的选择提出了根据子图大小计算支持度的递增函数，主要思想是采取增量函数计算子图的支持度，并设定判别率来判断一个特征是否冗余，索引非冗余特征。具体计算公式如下：

其中： fψix， fψiF，F为图集D的频繁子图集，ψ（l）为图size-支持度递增函数，γmin为用户给定的最小冗余度，Dfψi为子图x下所有的频繁子图集。当子图x同时满足式（2）、（3）时，子图x则为非冗余的频繁子图，并将这些挖掘得到的索引特征使用前缀树的形式通过哈希表存储。存储时不保留位置信息，只存储每个特征的对应的映射集。在查询处理期间，枚举查询图的所有图结构片段，直到最大片段，确保较小片段在较大片段之前被枚举。如果一个片段没有出现在索引中，则不会产生该片段的超图。通过每个扩展路径的最大片段的图ID列表的交集，得到查询的候选集。最后使用VF2算法比较查询图与所有候选图进行验证。

2.3.2 FG-index

FG-index（index based on Frequent subGraph）[22]提出δ-TCFG（δ-Tolerance Closed Frequent subGraph）特征标准用于衡量一个频繁子图是否冗余，提高索引对内存的利用率。δ-TCFG特征具体判定条件如下：

其中δ∈[0，1]，g为频繁子图，g为g′为子图，当且仅当g和g′满足式（4），且g′不为频繁子图时g为δ-TCFG特征。针对δ-TCFG特征建立倒排索引，如图4所示。

图4的索引结构保留索引特征位置信息实现快速查询，使用IDA（m，n，e）三元组结构定位GraphArray中的fi在EdgeArray中的位置，其中n=size（g），m=count（e，g），GraphArray为存储δ-TCFG特征的哈希表，EdgeArray存储δ-TCFG特征各边的哈希表;同时索引将δ-TCFG特征存储于内存，其余频繁模式存储在硬盘中以提高索引表的覆盖率。FG-index通过对δ-TCFG对频繁子图进行了细致的筛选，能直接返回精确的答案集，省却了索引验证的计算。

2.3.3 tree+Δ

tree+Δ（tree & delta）[21]以频繁树作为基本索引特征，再根据树特征按需选择少量的判别图Δ以提升索引的剪枝能力，将挖掘得到的索引特征存储于哈希表，不存储位置信息。针对判别图Δ的选择，tree+Δ[21]提出了通过树特征剪枝力的上下边界近似评估相应图特征冗余与否的计算函数，具体判定函数如下：

其中：g为g′的子图，Γ（g）、Γ（g′）分别为g、g′的频繁子树集，ε0为冗余系数，σ为频繁模式支持度，σx为模式x的支持度，当σΓ（g′）和σΓ（g）同时满足式（5）～（8）时，算法认为g′为非冗余特征图。

在查询阶段，tree+Δ[21]首先枚举出查询图q中所有满足最大长度的子集T（q），通过哈希表求的所有t的映射图集取交集得到候选集Cq，其中t∈T（q），最后使用VF2算法验证得到答案集。

2.3.4 Lindex

Lindex[23]由Dayu Yuan团队提出，相比之前的工作如何挖掘出合适的特征，该算法首次将工作重心放在索引表的数据结构上。该方法的索引特征是在频繁子图集的基础上挖掘得到，提出了基于倒排构建的点阵结构索引，每个节点都与一个〈key，value〉相关联，key代表一个索引特征，value代表该key映射下图集中的图。根据节点间的包含关系构建索引表，两个节点之间的边表示父节点中的key是子节点中key的子图，如图5所示。

图5为Lindex[23]索引结构示意图，根节点sg0为空图（没有节点或边的图）。节点sg0有两个孩子节点，分别是sg1和sg2。父节点是其子节点的频繁度最小的最大子图。在查询中通过索引特征间的包含逻辑进行快速查询，通过频繁度最小的最大子图构建整个索引，提高返回答案集的精度，大幅度降低了整体的查询时间;但是由于Lindex[23]要在频繁模式的基础上重新构建图见证，所以索引表整体的构建时间远远大于其他索引，但是当面对海量数据集时，基于频繁模式挖掘的索引构建时间比较长，在数据集动态更新的情况下，很难保证索引性能的实时性。Dayu Yuan团队首次提出基于迭代挖掘的索引构建方法[24]。算法首先通过较大的支持度完成首次特征挖掘，之后根据目标函数（见式（9）），迭代更新索引表中的索引特征，并且首次引入对查询日志的数据挖掘，通过将查询日志信息于索引特征相结合，使索引特征更能符合用户的查询习惯。

其中gain（p，P0）为索引特征集P0添加特征p之后的索引剪枝力的增益。

针对索引构件该算法采用与Lindex[23]中相同的构建方法进行索引构建。

2.3.5 小结

本节主要介绍了现主流的部分算法。gIndex主要针对频繁度的选择问题，通过使用动态增量函数对不同size的子图采取不同的支持度在保持索引覆盖率的同时降低内存消耗，但当面对万级的图集时算法的空间消耗还是过大。相应FG-index通过各个子图的映射集的大小进一步过滤冗余特征来减少索引的内存消耗。Lindex不同于上述算法设计思路，通过优化索引结构，避免算法在验证阶段的子图同构计算，但频繁模式挖掘本身时空消耗就很大，因此该类算法不适用于大数据量的情况，相应的有文献[24]通过迭代挖掘的方式和tree+Δ使用树特征代替图特征来提高前期挖掘的速度，但当面对千万级图数据时，此类算法都未能完成索引构建。综上，基于频繁模式挖掘的索引构建算法，索引剪枝力强，查询结果精确，支持快速查询;但索引前期构建时空消耗大，索引结构复杂，维护困难，不适用于当下大数据时代的数据环境。

2.4 基于索引的子圖查询算法总结

本节主要针对上述几类算法进行汇总，由于篇幅有限故不再对算法进行一一罗列，表1为部分基于索引的图查询算法汇总。基于枚举构建的索引算法中，由于考虑到特征结构对于枚举计算的影响，一般使用路径特征来构建索引表，但是路径特征忽略了图的结构信息，查询过程中返回的候选集较大，大幅度增加了验证阶段的时空消耗，相应的有CT-index使用路径、树和图作为索引特征，以提高索引表的过滤能力，但是也增加索引构建的时空消耗。基于频繁模式挖掘的索引构建方法，主要可以分为图特征和树特征两类，相比于基于枚举的索引构建算法，基于频繁模式挖掘的索引构建算法在索引构建阶段的耗时较大，动态维护难，但是由于算法基于频繁模式选择，所以其索引的内存占用和剪枝力要远远小于前者。

3 分布式下的子图查询

当面对海量数据集时，往往将数据图存储在分布式平台中。分布式查询已经在关系数据和XML（EXtensible Markup Language）等方面有了广泛的研究。针对分布式平台下对图模型作挖掘分析面临这如下几个问题：1）数据图的存储;2）高效分布式算法的设计;3）节点间高效的通信。针对图的存储问题，主要有点分割和边分割两种策略：前者能降低节点间的通信开销，但是动态的维护难度较大;后者的维护难度较低，但是增加了节点间的通信开销。现有的分布式图数据处理系统主要有Pregel和InfiniteGraph等[31]。

3.1 disHHK算法

disHHK（distirbuted Henzinger Henzinger KopkedisHHK有英文全称吗？）[32]是由Shuai Ma在2012提出的首个分布式图模式匹配算法，同时提出了针对分布式算法以相对计算时间、完成时间以及数据传输量为主的评估标准。算法整体可以分为调度节点的调度算法和工作节点的匹配算法两个部分。调度算法主要为匹配后对所有结果进行join操作时提供调度策略;匹配算法则是直接通过DFS遍历枚举工作节点中与查询图匹配的数据图，其中主要考虑部分匹配和完全匹配两种情况。算法在查询过程中，首先通过调度节点将查询图广播至各个工作节点上，各节点中通过单机下的HHK（Henzinger Henzinger KopkeHHK有英文全称吗？）匹配算法枚举出数据图中与查询图匹配的映射集，然后将结果回传至调度节点;调度节点通过基于贪心的调度策略分配各匹配结果至最优的工作节点进行join操作，最后输出查询图的查询结果。disHHK算法主要适用于有向图，由于其在单机下的匹配策略是通过DFS遍历来枚举查询图的匹配集，所以当节点间数据分布不均衡时，木桶效应就比较明显。

3.2 Stwig算法

Stwig（Sub twig）[33]认为由于索引的渐进复杂性，基于索引的查询算法不能提供稳定的性能，因此算法不建立索引，主要依靠内存云和大规模并行计算完成能在大的单图（十亿节点）下的子图查询。匹配过程通过图的拓扑结构的扩展来取代子图匹配中的join操作。其中算法主要通过基于采样的链接成本估计和基于成本的计算估计两个优化策略来避免通过图的拓扑结构的扩展来进行子图匹配中间存在着大量的无用遍历的问题。其中算法主要通过基于采样的链接成本估计和基于成本的计算估计两个优化策略来避免当通过图的拓扑结构扩展来进行子图匹配时存在大量无用遍历的现象。此句不通顺，“进行”是否应该改为“解决”，请明确查询过程中，首先算法先将查询图进行分解成二级树的集合得到Stwig序列，分解过程中算法主要通过式（10）来选择计算结果最大的顶点，分解算法主要保障能每次分解得到查询图中最大的二级树。

其中：deg（v）为顶点v的度， frep（v.label）为顶点v标签的频繁度。

分解之后，将Stwig序列广播至集群中的各个节点，然后根据图的拓扑结构进行扩展，其中主要通过优化Stwig序列的匹配顺序以此来降低节点间的通通信代价，最后得到匹配结果。算法主要通过拓扑结构的扩展来代替索引避免join操作产生大量的中间结果，降低计算成本，提升匹配的速度;但是Stwig并没有与通过索引的查询的相关算法作比较，同时实验对比算法较少。

3.3 分布式下子图查询算法总结

目前针对分布式下的子图查询算法，相关研究还处于起步阶段，现有的查询算法也都是未通过索引查询完成的，因此针对查询效率方面还有很大的提升空间，同时分布式下的子图查询算法相比单机下的查询算法有着评价指标不单一、算法结构更加复杂等特点。

4 结语

本文阐述了基于索引的子图查询的相关工作，通过建立索引可以有效降低查询中子图同构的计算时间。从索引的构建方法出发对主流的构建方法进行分类探讨，分别对基于不同构建方法的索引从索引特征的类型、索引特征获取方法、索引数据结构、索引是否存储位置信息这四个方面进行了对比分析，最后对最新的分布式环境下的子图查询算法作了简单归总。

随着子图查询的广泛应用以及数据量的不断增加。针对大数据环境，以往图查询技术很难适应与相应的工作环境。与传统的精确查询不同，大数据环境下的查询主要以模糊匹配为主，相应现图查询技术面临着以下几方面的挑战：1）索引的构建本身就存在大量的时空开销，与数据量的增加不成线性关系，并且存在一定的局部性;2）针对千万级顶点以上的数据图很难有合适的图索引算法能构建索引，完成快速查询操作;3）面对动态图下的索引维护容易丧失部分索引信息，通过针对索引性能的检测很难做到实时反馈的程度。

针对上述问题，图索引今后的发展趋势主要可以有：如下。

1）设计构建多级索引结构。针对目前索引构建的主要问题来看，主要体现在两个方面：a）从算法自身角度看，索引构建过程的时空损耗本来就十分巨大，尤其是基于频繁模式挖掘的索引构建算法。b）从数据角度看，由于数据量的不断增加，其计算量也增大，同时数据的存储就成了主要问题，而通过将图压缩技术和多级索引技术相结合，能有效提高索引表的覆蓋率以及在可接受的时间内返回精确的答案集，因此，从索引构建的角度出发，如何结合先主流的图压缩技术设计出精简高效的多级索引，将会是未来研究的一大趋势。

2）分布式环境下的索引构建方法。传统的基于索引的查询算法难以适用于分布式下的子图查询操作。图数据内部具有强关联性的特征，针对分布式下的子图查询算法有着数据通信量大、冗余计算严重等问题，通过构建索引能有效地减少子图查询过程中的冗余计算量，设计合理的任务调度算法也能大幅度地降低系统的信息吞吐量，但目前针对此类的研究尚未起步。针对分布式下的索引构建出发，如何设计合理的索引结构以适用于分布式环境下的子图查询算法，在未来也将会是研究的一大热点。

3）动态图的索引维护。图数据的频繁更新，传统的方法很难将索引覆盖率维持在容忍范围内。动态图的索引维护是一个较新的领域。现有的方法主要是通过增量监控的算法计算查询返回的答案集的偏移量，并设置阈值进行索引更新，更新方法都是通过直接重构实现。由于涉及到主观因素，其更新速度未能满足实时性的要求，同时由于引入了偏移量的计算，索引更新存在一定误差，存在大量的资源浪费现象。这也将是未来研究的一大趋势。

参考文献 （References）

[1] BERMAN H M， WESTBROOK J， FENG Z， et al. The protein data bank [J]. Genetica， 2000， 106（1/2）： 149-158.

[2] DESHPANDE M， KURAMOCHI M， WALE N， et al. Frequent substructure-based approaches for classifying chemical compounds [C]// ICDM 2003： Proceedings of the 2003 International Conference on IEEE International Conference on Data Mining. Washington， DC： IEEE Computer Society， 2003： 35.

[3] LIANG R， HAI Z， JIANG X， et al. Scaling hop-based reachability indexing for fast graph pattern query processing [J]. IEEE Transactions on Knowledge & Data Engineering， 2014， 26（11）： 2803-2817.

[4] YUAN Y， WANG G， XU J Y， et al. Efficient distributed subgraph similarity matching [J]. VLDB Journal， 2015， 24（3）： 369-394.

[5] LAPPAS T， LIU K， TERZI E. Finding a team of experts in social networks[C]// KDD 2009： Proceedings of the 2009 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2009： 467-476.

[6] 王超珲，黄一夫.基于增量信息索引的子图查询算法[J].计算机应用与软件，2016，33（10）：37-40.（WANG C H， HUANG Y F. A subgraph query algorithm based on incremental information index [J]. Computer Applications & Software， 2016， 33（10）： 37-40.）

[7] DINARI H. A survey on graph queries processing： techniques and methods [J]. International Journal of Computer Network & Information Security， 2017， 9（4）： 48-56.

[8] KATSAROU F， NTARMOS N， TRIANTAFILLOU P. Performance and scalability of indexed subgraph query processing methods [J]. Proceedings of the VLDB Endowment， 2015， 8（12）： 1566-1577.

[9] YAN X， YU P S， HAN J. Graph indexing： a frequent structure-based approach [C]// ICMD 2004： Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2004： 335-346.

[10] 陸慧琳，黄博.基于双索引的子图查询算法[J].计算机工程，2015， 41（1）：44-48.（LU H L， HUANG B. Subgraph query algorithm based on dual index [J]. Computer Engineering， 2015， 41（1）：44-48.）

[11] 黄云，洪佳明，覃遵跃，等.ERSearch：一种高效的子图查询算法[J].电子学报，2017，45（2）：368-375（HUANG Y， HONG J M， TAN Z Y， et al. ERSearch： an efficient subgraph query algorithm [J]. Acta Electronica Sinica， 2017， 45（2）： 368-375.）

[12] SOMKUNWAR M R， VAZE V M. Subgraph isomorphism algorithms for matching graphs： a survey [EB/OL]. （2017-07-01）[2017-12-10]. http：//ijett.in/index.php/IJETT/article/view/279/173.

[13] ZOU L， CHEN L， YU J X， et al. A novel spectral coding in a large graph database [C]// EDBT 2008： Proceedings of the 2008 International Conference on Extending Database Technology. New York： ACM， 2008： 181-192.

[14] BONNICI V， FERRO A， GIUGNO R， et al. Enhancing graph database indexing by suffix tree structure [C]// PRIB 2010： Proceedings of the 2010 International Conference on Pattern Recognition in Bioinformatics. Berlin： Springer， 2010： 195-203.

[15] GIUGNO R， BONNICI V， BOMBIERI N， et al. GRAPES： a software for parallel searching on biological graphs targeting multi-core architectures [J]. PLoS One， 2013， 8（10）： e76911.

[16] JIANG H， WANG H， YU P S， et al. GString： a novel approach for efficient search in graph databases [C]// ICDE2007： Proceedings of the 2007 IEEE International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 2007： 566-575.

[17] DI NATALE R， FERRO A， GIUGNO R， et al. SING： subgraph search in non-homogeneous graphs[J]. BMC Bioinformatics， 2010， 11（1）： 1-15.

[18] ZHAO P， HAN J. On graph query optimization in large networks [J]. Proceedings of the VLDB Endowment， 2010， 3（1/2）： 340-351.

[19] ZHANG S， YANG J， JIN W. SAPPER： subgraph indexing and approximate matching in large graphs [J]. Proceedings of the VLDB Endowment， 2010， 3（1）： 1185-1194.

[20] ZHANG S， HU M， YANG J. TreePi： a novel graph indexing method [C]// ICDE2007： Proceedings of the 2007 IEEE International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 2007： 966-975.

[21] ZHAO P， YU J X， YU P S. Graph indexing： tree+delta<=graph [C]// VLDB 2007： Proceedings of the 33rd International Conference on Very Large Data Bases. Trondheim： VLDB Endowment， 2007： 938-949.

[22] CHENG J， KE Y， NG W， et al. FG-index： towards verification-free query processing on graph databases [C]// SIGMOD 2017： Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2007： 857-872.

[23] YUAN D， MITRA P. Lindex： a lattice-based index for graph databases [J]. The VLDB Journal—The International Journal on Very Large Data Bases， 2013， 22（2）： 229-252.

[24] YUAN D， MITRA P， YU H， et al. Iterative graph feature mining for graph indexing [C]// ICDE2012： Proceedings of the 2012 IEEE International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 2012： 198-209.

[25] KLEIN K， KRIEGE N， MUTZEL P. CT-index： fingerprint-based graph indexing combining cycles and trees [C]// ICDE2011： Proceedings of the 2011 IEEE International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 2011： 1115-1126.

[26] LYU B， QIN L， LIN X， et al. Scalable supergraph search in large graph databases [C]// ICDE2016： Proceedings of the 2016 IEEE International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 2016： 157-168.

[27] YUAN D， MITRA P， GILES C L. Mining and indexing graphs for supergraph search [J]. Proceedings of the VLDB Endowment， 2013， 6（10）： 829-840.

[28] XIE Y， YU P S. CP-index： on the efficient indexing of large graphs [C]// CIKM： Proceedings of the 2011 ACM International Conference on Information and Knowledge Management. New York： ACM， 2011： 1795-1804.

[29] ULLMANN J R. An algorithm for subgraph isomorphism [J]. Journal of the ACM， 1976， 23（1）： 31-42.

[30] CORDELLA L P， FOGGIA P， SANSONE C， et al. A （sub）graph isomorphism algorithm for matching large graphs [J]. IEEE Transactions on Pattern Analysis & Machine Intelligence， 2004， 26（10）： 1367.

[31] HU H， WEN Y， CHUA T S， et al. Toward scalable systems for big data analytics： a technology tutorial [J]. IEEE Access， 2017， 2（1）： 652-687.

[32] MA S， CAO Y， HUAI J， et al. Distributed graph pattern matching [C]// WWW12： Proceedings of the 2013 Conference on World Wide Web. New York： ACM， 2012： 949-958.

[33] SUN Z， WANG H Z， WANG H X， et al. Efficient subgraph matching on billion node graphs [J]. Proceedings of the VLDB Endowment， 2012， 5（9）： 788-799.