MSP：基于Map-Reduce的多子图查询处理与集成图索引的研究

沙特国王大学学报MSP：基于结构划分策略和Map-Reduce的多子图查询处理Shaik Fathimabi，R.B.V. Subramanyam，D.V.L.N.索马亚尤卢印度特伦甘纳邦瓦朗加尔国家技术学院计算机科学与工程系阿提奇莱因福奥文章历史记录：2016年6月14日收到2016年10月24日修订2016年11月15日接受2016年11月25日在线发布保留字：图表数据库大数据基于结构的图划分并行处理映射缩减综合图表索引A B S T R A C T在分布式环境中，图数据库的容量迅速增加，因为图来自多个自治源。子图查询处理是分布式环境下的一个具有挑战性的问题。集中式方法提出了许多算法，它们从图数据库中挖掘频繁子图并构造索引，这是非常昂贵的。这些算法需要大量的数据库扫描来挖掘频繁子图，并且采用过滤验证的方法，需要进行大量的子图同构测试。本文设计了一种基于Map-Reduce的多子图查询处理框架MSP。MSP使用分布式索引处理多个图查询该框架完全依赖于图的划分和索引。此外，为了提高其性能，我们提出了几种解决方案，以平衡工作负载和减少集成图索引的大小。提出了一种基于结构的划分技术和分布式的集成图索引构建方法。该工作使用两轮Map-Reduce，第一轮Map-Reduce对图进行分区并为每个分区创建索引，第二轮Map-Reduce处理子图查询和索引维护。一个好的分区将通过将负载平均分配给集群中的机器来减少索引大小，并提高查询评估的性能。这种图划分和集成图索引减少了查询图的搜索空间我们的方法允许在进行查询处理的同时将数据图增量地添加到集成图索引我们的实验表明，我们的方法显着降低了执行时间和规模的子图查询处理大型图数据库。©2016作者。制作和主办：Elsevier B.V.代表沙特国王大学这是一CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍图被广泛用于模拟复杂的结构，如蛋白质相互作用，化学化合物和网络数据在许多应用中（Willett，1998）。当代世界在图形数据库中有着巨大的应用。当数据库用于管理由图形表示的对象的数据时，数据库分为两类。第一类是单个图形设置，其中图形数据库仅包含一个大型图形。第二类是事务图数据库，它由*通讯作者。电子邮件地址：fathimanitw@gmail.com（S.Fathimabi）、rbvs66@gmail.com（R.B.V. Subramanyam）、soma@nitw.ac.in（D.V.L.N.）Somayajulu）。沙特国王大学负责同行审查制作和主办：Elsevier大量相对较小的图形。事务图数据库应用于化学、生物信息学等科学领域.图查询处理问题分为两类。第一个是子图查询处理，它用于检索数据库中的所有图，使得给定的查询图是它们的子图。第二个是超图查询处理（Cheng和Ke，2011），用于检索数据库中的所有图，使得查询图是它们的超图本文研究了具有广泛应用的子图子图查询问题也称为子图同构问题，属于NP完全问题（Lubiw，1981）.许多图形数据集日益增多.由于大型图数据库的规模和复杂性，通常很难用一台机器来处理。PubChem项目处理超过3000万种化合物，其存储大小达到数十TB（Willett，1998）。近年来，大数据现象已经出现在许多应用领域和研究中，包括模式识别（Kuramochi和Karypis，2005年）、社交网络、化学信息学（Willett，1998年）、医学图像处理、生物信息学、生物信息学、生物医学和生物医学。https://doi.org/10.1016/j.jksuci.2016.11.0071319-1578/©2016作者。制作和主办：Elsevier B.V.代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comS. Fathimabi等人/沙特国王大学学报23数据库（Euripides，1997）、图结构查询处理、图数据挖掘（Xifengand Jiawei，2002）、封闭图（Xifengand Jiawei，2003）、计算生物学。与此同时，Map-Reduce（Dean和Ghemawat，2008）已经获得了工业界和学术界的广泛关注MapReduce（hadoop，0000）提供了一种分布式方法来处理数据密集型作业，并且在跨计算机管理作业方面没有任何困难。MapReduce采用的以数据为中心的方法是使用将计算移动到数据的思想。它使用分布式文件系统（Shvachko等人， 2010）和（hdfs，0000），这些都经过了特别优化，可在处理海量数据时提高IO性能。这个框架的另一个主要原因是，更高级别的细节对程序员隐藏，并允许更多地专注于特定问题的计算逻辑。在多用户环境中，图查询由用户的数量给出在本文中，我们设计了一个新的多子图查询处理，命名为MSP。MSP解决了在大型图数据库上处理多个图查询的问题（Angles，2012）。我们提出了一个分布式的图索引和查询处理方法，使用Hadoop，一个开源的实现地图减少。我们首先讨论了执行图查询集和图数据集之间的所有成对子图同构测试需要很长时间的朴素方法。为了减少子图同构测试的数量，我们引入了基于结构的划分和集成图索引，用于进行过滤和验证步骤。索引维护是更容易通过使用集成图形索引。我们的工作贡献概述如下：本文提出了一个有效的多子图查询处理框架MSP，它可以处理大规模的图数据库和查询图集。本文提出了一种简单有效的负载感知分布策略--基于结构的数据划分技术，利用MapReduce增强了MapReduce提供的默认数据划分技术。我们介绍了一种有效的方法来建立分布式的方式来构建集成图索引使用多条边和顶点标签的连接。我们设计了分布式算法，在一轮Map-Reduce中处理查询和索引维护。我们引入了最大深度优先的代码，用于基于结构的划分。我们的实验证明了合成以及真实世界的大数据集上的算法的性能。本文的其余部分组织如下。我们将在第2节讨论相关工作。第3节介绍了一种方法。第4节介绍了拟定方法。第5节讨论了实验结果。最后，我们在第6节（表1）2. 相关工作在复杂结构的建模中，图形的使用已变得越来越重要。现在的图表用于对任何类型的数据进行建模。存在许多算法用于解决子图查询处理任务的集中和内存版本，其中最值得注意的是Graph Grep（Giugno和Shasha，2002）、Tree and graph search（Shasha等人， 2002）、FGIndex（Cheng等人，2007 ）、GIndex（Yan等人，2005）、ClosureTree（He和Singh，2006）、TreePi（Zhang等人，2007），树+ delta的图索引（Zhao等人，2007），一种在大型图形数据库中的新颖的谱编码（Zou et al.， 2008）、GString（Jiang等人，图包含和索引是在Chen等人中提出的。（2007年）。这些表1符号。符号描述|图的大小，图中的边数|Size of the graph, number of edges in the graph三维图形数据库图数据库或特定分区中的图的集合Q查询图Aqi查询的答案集qi图数据库的集成图索引IGIpnoD的特殊划分的积分图host（e）当前在IGIpnofreq（e）IGIpno中有e的图的个数算法假设数据集很小，并且使用内存方法在规定的时间量内完成挖掘任务。在（Kim等人，2013）使用Map-Reduce（PPMG）方法并行处理多个图查询，每次从数据图中提取特征来处理查询图。需要很长时间Luo等人（2011）使用边索引解决了单个子图查询处理问题。现 在 ， 许 多 算 法 都 使 用 Map-Reduce 处 理 单 个 大 型 图 。 Pregel（Malewicz等人，2010）提出了以顶点为中心的图形处理。Kang等人（2011）开发了一个系统来分析单个大型图，如Web数据或社交网络。在（Kang等人，2008）直径估计和使用Hadoop的挖掘。在本文中，我们专注于一个大的小图集。由于各种原因，在Map-Reduce等分布式平台上解决子图查询处理任务具有挑战性。文献中提供了两种类型的数据分区● 默认图分区● 基于密度的图划分2.1. 默认图分区这是Map-Reduce使用的默认分割方法它基于块大小对图进行分区，并且在分区过程中不考虑输入数据图的特性图的数目是不均匀分布的，并且载荷不是均匀分布的。然而，对于数据集中图的大小变化很大的数据集，我们使用基于密度的图分区。2.2. 基于密度的图划分基于密度的图数据分区在Aridhiet al.（2015）中提出。这种划分适用于数据集，其中图的大小不同。它基于输入数据图的特征，即在创建分区期间每个图的密度。它基于图的密度而不是基于图的边缘和结构上的标签将负载均等地分配给集群上的所有机器。3. 问题定义在这项工作中，我们考虑无向，标记和连接图。我们形式化地定义了一个图和子图的查询问题，并解决了这个问题.然后描述了图数据在Map-Reduce中的表示。3.1. 定义图：图由元组g =（V，E，L，l）表示，其中V是顶点集，E是无向边集，使得●●●●●●24S. Fathimabi等人/沙特国王大学学报2E. L是顶点或边的标签的集合，并且标签函数l定义映射：V U E？L.我们还用V（g）和E（g）分别表示图g的点集和边集。我们定义图g的大小，记为|G|，作为g中的边数，即|G|为|E（g）|.子图同构给定两个图s =（Vs，Es，Ls，ls）和g =（Vg，Eg，Lg，lg），称s与g（s <$g）同构当且仅当存在一个内射函数f：Vs？Vg，使得(1)6v2Vs，我们可以有f（v）2Vg和ls（v）=lg（f（v））;（2）6（u，v）2Es，我们可以有（f（u），f（v））2Eg，并且fs [u，v] = fg [f（u），f（v）]。3.2. 问题陈述设D = g1，g2，g3.. . gn是图形数据集。此外，设Q = q1，q2，q3... . q x是图形查询集，使得|Q||对于每个图形|for each graph查询q2Q，我们找到所有q是D的同构子图的图 结果是A Q= A q1，Aq2，. A qx，其中A q i= g j：g j2 D，q i <$g j，即每个A qi包含D中的数据图的集合，qi的超图这个问题不同于现有的一次处理一个子图查询的子图查询处理问题，但是这里它一次处理一批查询。我们开发一个一次处理批量查询的解决方案的原因如下：在分布式环境中，一次会有更多的查询来自不同的源。处理以下列方式进入的查询：高速流对于需要迅速查询响应的许多应用是有用的。在这里，我们集成了子图查询处理和索引维护。此外，批量查询处理使我们能够消除查询和插入图之间的公共部分的重复过程，从而获得更高的吞吐量。本文的目标是开发一个高效的分布式系统，使用集成图索引处理多个子图查询。3.3. 图表示图形为单线：大多数图形数据集都以多线格式提供。一些现有的频繁子图挖掘工作（Mansurul和Mohammad，2013）使用Hadoop在数据准备步骤中将图划分为一组文件，并将该组文件作为MapReduce程序的输入。在这项工作中，我们将多行格式的图形转换为单线格式的图形。在单行格式中，存在序列化格式g，其枚举g 中 的顶点和边，即{|V（g）|、|，l（V（g）），E（g）}，其中e E（g）表示为from-gid，to-gid，l（e）。|, l (V (g)), E (g)} where e E(g) is represented as from-gid,to-gid, l(e). ，no_of_vertices>，no_of_edges><所有顶点的标签>，edgelist>图id：单个图g的唯一标识符No of vertices：图形中的顶点总数边数：图中的边总数。Labels of all vertices：所有顶点的标签列表。Edgelist：图的边列表。每条边包含三个元素。& lt;sourceid，destinationid，edgelabel>例如：g2，4，4，A，B，C，E，0，1，b，0，2，d，1，2，e，2，3，f.[3][4][5][6][7][8][10][11][12][13][14][15][16][17][18][19][4. 该方法在本节中，我们将讨论所提出的使用基于结构的划分进行多子图查询处理和分布式环境中的集成图索引大型图形数据库具有不同类型的图形，这些图形具有不同的标签。第一步是基于标签和结构划分图。第二步是为图的划分构造集成图索引。第三步是使用集成图索引进行多图查询处理。首先，我们讨论以下Hadoop方法来设计一个使用Map-Reduce的高效算法：在映射器组合器设计模式（IMCDP）中：在这种模式中，组合器被写在映射器逻辑中。映射器不是逐行发送输出，而是使用在mapper组合中。它不改变算法的运行时间复杂度，但大大减少了需要从映射器到归约器进行混洗的键值对的数量和大小。因此，我们使用IMCDP。分布式缓存：它有效地将应用程序特定的大型只读文件分发给所有映射器。它是MapReduce框架提供的一种工具，用于缓存所有映射器所需的文件，即所有任务跟踪器（节点）。使用分布式缓存，我们可以在所有任务跟踪器中分配一些公共数据当我们需要分发文件时，文件的多个副本将被维护以供所有任务跟踪器访问。本文将整个工作分为四个阶段● 图划分● 集成图形索引创建● 子图查询集的处理和索引维护以下小节将讨论上述步骤4.1. 图划分4.1.1. 动机和原则将输入的大型图数据库划分为分区的动机在分布式环境中，算法的效率取决于我们如何有效地划分数据图并将其分发到集群上的节点好的划分技术可以有效地分布数据，降低集成成本和计算成本，即子图同构测试成本。一些作者将数据划分为单个机器上的预处理步骤。但在本文中，我们使用Map-Reduce阶段划分数据图为了处理图查询，我们需要检查集群上可用的所有数据我们可以检查具有类似查询图结构的图，而不是检查所有机器上的所有图。这种方法在通信成本和计算成本方面都更有效图划分技术可以将所有相似图集中到一台机器上。基于这个动机，我们开发了一种基于结构的图划分方法。在分布式环境中，异构数据来自不同的数据源进行处理。如果我们事先知道领域知识，我们就可以基于领域知识对图进行划分基于域的分区对于索引和查询处理更有效。我们提出了两种基于标签和数据图结构的图数据库分区技术，如下所示：● 基于标签的图划分● 基于结构的图划分4.1.2. 基于标号的图划分在这个划分中，具有相同标签的图进入一个或多个划分。一个地图减少轮是需要为这个partition。映射器读取图并准备键和值，键是根据字典顺序的所有边的串联，值是图id和深度的串联S. Fathimabi等人/沙特国王大学学报25图的遍历代码。每条边由三个元素表示：<源顶点标签，边标签，目的地顶点标签>。对于字典顺序，我们首先考虑源顶点标签，然后是边标签，最后是目标顶点标签。Reducer接收所有具有相似标签类型的图，建立集成图索引并存储在HDFS中。算法1给出了基于标号的图划分过程。图1a示出了标签划分之后的图。4.1.3. 基于结构的划分在某些应用中，顶点和边的标号是相同的，但图的结构是不同的。我们提出了一种基于结构的图划分技术，将所有具有相似标签和结构的图集中到一台机器上。我们使用标签和图的结构作为特征来划分图。为了得到结构，我们使用图的最大深度优先遍历代码。基于最大深度优先遍历码，对图进行划分。因此，它是更有效的相比，标签为基础的partition。两个Map-Reduce作业用于进行基于结构的图划分。第一轮Map-Reduce用于找到每条边，它的频率。第二轮Map-Reduce用于基于最大dfs代码划分图并进行图集成。图4示出了基于结构的划分的概述。图1a示出了基于结构的划分之后的图。在这个分区中，我们使用分布式缓存来存储第一轮Map-Reduce的结果，并在第二轮Map-Reduce中读取。第二个Map- Reduce回合进行基于结构的分区。第一轮Map-Reduce用于找到每个边的频率：在算法2中，映射器使用IMCDP方法在映射器处进行局部聚合。Mapper读取图形并解析边缘，并对整个分区的边缘进行局部频率计数。它发送边缘值作为键，本地频率计数作为值。约简器对边的频率进行全局聚合，并将边作为键发送，频率作为值发送。Maximum Depth First Traffic code：从具有最高频率的边缘开始，然后选择下一个最高频率边缘的图形的Depth FirstTraffic代码。先考虑后向边缘，然后考虑前向边缘。所有规则都与gspan中的深度优先搜索代码相同（Xifeng和Jiawei，2002）。如果两个边缘具有相同的频率，则根据下式选择边缘：边标号的字典顺序。图1.示例图形数据库和查询图形。26S. Fathimabi等人/沙特国王大学学报4.2. 创建集成图索引的有效方法我们使用Cheng和Ke（2011）中提出的方法将图整合为集成图索引。除了他们的算法之外，我们在集成过程中引入了两个优化，以减少集成图索引的大小给定一组图G，图集成的概念是将G中的所有图合并为一个紧致图IGI，其中图的重复公共子结构在G中尽可能地被消除为减小集成图索引的大小而提出的两个优化是● 平行边缘● 基于顶点标签的连接图2. IGI1与G1。现有顶点。图5示出了执行基于顶点标签的连接的示例。初始化集成图和集成图索引创建所需的方法如算法4所示。对于图1a中给出的示例图数据库和图1b中给出的查询图集合，解释了集成过程。图2是将g1放入IG后的IG。图3示出了在g2、g3、g4的积分之后的IG，并且我们可以识别多个边缘。图5示出了基于标签的连接的示例。图集成的一般方法是先从图G中挖掘出频繁子图，然后按照频繁子图的频率降序共享图G中的频繁子图进行图的合并。然而，频繁的子图挖掘是昂贵的，特别是当数据库更新频繁或查询流来。4.2.1. 平行边缘在两个顶点之间存在两个或多个边，这些边被称为平行边。我们可以将平行边表示为具有多个边标签的单个边。当顶点标签的集成是匹配的时，边标签是不同的，因此，在集成图中，我们可以向顶点添加平行边，而不是添加单独的顶点和边。这将减少集成图形索引的大小。标签和指针存储在头表中。4.2.2. 基于顶点标号的连接在集成过程中，深度优先遍历不匹配，使用顶点标签来集成图形，这称为基于顶点标签的连接。该方法在积分过程中，如果顶点标号与边标号不相同，则不需要添加新的顶点，而是将该标号与已有积分图中的顶点它通过利用S. Fathimabi等人/沙特国王大学学报27图3. IGI1及其边表和索引表。本文利用G中图的边频率的统计特性，提出了一个将一组图合并成一个紧图的有效算法。设G是一组图，IGI是图G的紧图称为图的积分图指数（IGI）。 我们在IGI中保留了G的边的图的信息，同时消除了G的边之间共享的重复边。G.我们首先定义IGI中边e的频率，表示为freq（e），作为G中在IGI中共享e的图的数量。为为了进行查询处理，我们还将IGI中的每条边与G中共享e的图（ID）的集合相关联，表示为作为宿主（e）。图集成的基本思想是利用当前IGI中边的频率来指导输入IGI的图形。更具体地说，当将图g合并到IGI中时，我们找到g中也在IGI中的所有边并选择在IGI中具有最高频率的一个边，我们简单地通过边标签的字典顺序来打破束缚。然后使用该边缘作为g和IGI中的起始边缘，我们同时执行对G和IGI的深度优先遍历以找到它们的公共子图。设e0为起始边，e1为深度优先遍历g时要访问的下一条边设E1是在IGI的深度优先遍历中我们可以选择访问的紧挨着e0的我们在E1中找到一条与e1匹配的边来访问。如果E1中有多条边匹配e1，我们选择频率最高的一条进行访问。这个过程会一直持续下去，直到我们遇到一个在IGI中无法匹配的g中的边。同时深度优先遍历中的匹配边形成g和IGI的公共子图。我们通过共享它们的公共子图将g合并到IGI中，同时我们在IGI中为g中尚未匹配的那些边创建新的边。 同时深度优先遍历中的匹配边形成g和IGI的公共子图。我们通过共享这个公共子图将g合并到IGI中，同时我们在IGI中为g中尚未匹配的那些边创建新的边。请注意，我们通过（lu，le，lv）匹配边，即定义一个离散边。g中的不同边e0在本例中，我们从g中的每个e实例开始多次运行同步深度优先遍历。在多重遍历中，我们选取g和IGI的最大公共子图，并通过共享该子图将g合并到IGI中。在这个过程中，我们使用一个共同的子图与平行的边缘和顶点标签的连接。利用平行边减少了IGI中的边数，利用基于顶点标号的连接减少了IGI中的顶点数。为了找到在IGI中具有最高频率的边作为同时深度优先遍历的起始边，我们构造边表来保持IGI中的不同边的集合边缘表中的每个不同的边缘ed具有指向IGI中的ed的实例的指针列表，并且第一个指针指向具有最高频率的实例算法4给出了集成图索引（IGI）的构造对于每个输入图gi，算法首先从边表中找到gi的每个不同边的频率，然后选择具有最高频率的边e0，其中e0指向IGI中的实例e。然后，对于gi中e0的每个实例e1，该算法找到gi和IGI的最大公共子图对于每个子图，我们应用顶点标签的连接和多个边缘技术。然后，我们挑选最大的匹配子图g，并通过共享g将gi合并到IGI中。然后，在IGI中为gi中的每条边而不是g中的每条边创建在合并过程中，对于g i中的每条边，我们还增加频率并更新IGI中匹配边的索引，以帮助将来的整合。可以注意到，每个索引（e）中的图ID是自动排序的，因为图以其ID的升序合并到IGI中。最后，当IGI中的所有图被合并时，输出IGI每个gi到IGI的合并仅花费线性时间，gi的大小，假设不同边的实例数对于大多数数据集来说，in gi是一个常量。算法4的总复杂度为O（n| G|其中n是图的平均大小in G.在最坏的情况下，当G中的每个图仅由一个不同的边组成（即所有边都是相同的）时，复杂度为O（n2| G|）.然而，对于事务图数据库中的图，即使n2例1：图1示出了由四个图g1、g2、g3和g4组成的一组图G。最初，积分图IGI =g1，如图2所示。IGI x：1意味着边具有标签x，28S. Fathimabi等人/沙特国王大学学报图4.基于结构的图划分和集成图索引的创建概述：算法2的结果被加载到分布式缓存中以用于基于结构的算法3展示了进行基于结构的划分和创建集成图索引的过程在算法3中，映射器读取图并准备最大DFS代码以发送最大DFS代码作为键，并且值是图id和最大DFS代码的级联图5.基于标签的连接示例频率1. 图3示出了分别在图3a-cIGI的索引表如图所示。 3 d.图积分法是一种简单有效的积分方法。它有几个优点。通过在合并图时允许边缘频率的降序，我们能够将图集成到许多其他图被集成到的位置。这该方法以频繁子图为集成指导，提取多个图的公共子图。图集成方法是非常快的，因为它不涉及任何昂贵的操作，如频繁的子图挖掘或子图同构测试。最昂贵的步骤是执行深度优先遍历，它在图g的大小上是线性的。用于指导积分的边缘频率可以很容易地收集和保持在积分过程中。集成图索引保留了图的所有邻域信息利用集成图索引可以提取公共子图。4.3. 图查询处理和索引维护我们现在讨论如何使用IGI进行查询处理和索引维护。此步骤同时执行查询处理和索引维护。这里，我们将查询处理和索引维护合并为一步，而不是分别进行查询处理和索引维护，以消除多余的工作和Map-Reduce轮数。我们首先给出整体框架，然后介绍每个步骤的细节。在此阶段，从HDFS加载所需的集成图索引文件。另一个输入是查询图和要插入的新图。算法5显示了该阶段所需的整个过程。框架我们的查询处理系统包括以下三个主要步骤：●●●S. Fathimabi等人/沙特国王大学学报29表3图形分区表。IGI文件名Graph IdsIGI1文件名Q1、Q2、Q3、G150IGI3文件名Q4，Q5，G100表4查询处理的结果。查询ID图形IDQ1 G1、G2、G4Q2 G2Q3 G2我们检查查询的所有边是否存在于该IGI中。如果所有边都不存在于任何IGI中，那么我们可以过滤该查询。这意味着该查询图的结果为空。对于要插入到IGI中的新图，我们检查IGI中新图的所有边，选择IGI有更多的新图的边。根据边的存在性，将图进行划分，并将其放置在表中。输入图形分区的结果存储在图形分区表中。图分区表的格式如表3所示。图分区表：过滤步骤后，结果存储在图分区表中，其格式如表3所示。4.3.2. 输入图形集成在输入图分区之后，应用算法4来整合属于每个IGI的所有输入图。对于每组查询，我们得到一个查询集成索引。查询集成索引图被加载到分布式缓存中以进行下一步验证。基于集成图索引特征的输入图划分。● 输入图形集成。● 查询图校验和索引维护。4.3.1. 基于集成图索引特征的输入图划分当查询图序列和要插入的新图被发出时，我们首先需要做预处理步骤。这里输入图意味着查询图和要插入的新图对输入图的处理首先根据IGI的结构对输入图进行划分特征表：所有IGI的深度优先交通工具放置在一个表中并存储在一个文件中。特征表的格式是特征及其文件名，其中包含特定的IGI。表2显示了特征表的格式。过滤IGI：根据特征表中IGI的结构划分输入图的数量。从特征表中，我们得到每个IGI的最大dfs代码对于每个查询图表2IGI的特征表。功能IGIpno文件名4.3.3. 验证在验证步骤中，我们根据预处理步骤仅加载所需的IGI。我们只从HDFS加载这些集成图索引文件，而不是所有IGI。从HDFS加载所需的IGI。集成的图形索引文件被加载到许多机器中。所有的输入图都被加载到分布式缓存中，使它们对所有机器可用，预处理的结果被加载到分布式缓存中，即表3所示。根据IGI文件名获取所有查询编号。在查询处理过程中，验证IGI中是否存在查询结构。如果存在，请将其发送给答案。如果是新的图，则在边索引表和边表中插入图ID。当我们在最后向IGI添加任何新图形时，我们将在HDFS上存储更新的IGI。 对于图中给出的例子。 1，最终结果如表4所示。当我们处理第一个查询时，边ABx>，BBy>和它们的图ID被放置在表中，并用于进一步的查询，而不是从IGI获得每个查询的边，这将减少I/O时间。5. 实验本节给出了一个实验结果，证明了我们的方法在合成和真实数据集上的性能在下面的实验中，我们的目标是确定集中式方法和分布式方法的集成图索引的效率。特别是，我们比较了索引创建时间、查询1 2 B B y 2 3 B C z 3 5 C D w 3 2 C B w 2 0 B A z 01 A B x 0 4 A B xIGI1文件名处理时间和索引维护成本。它首先描述了使用的数据集和实施细节。然后，它提出了一个dis-IGI2 IG2文件名的最大dfs代码对所得结果进行了讨论。●30S. Fathimabi等人/沙特国王大学学报和新的图形插入，其中包含各种数量的查询，即|Q| = 10、100、200、300至2000。5.1. 实验装置5.1.1. 数据集在我们的实验研究中使用的数据集在表5中描述，真实世界的图形数据集取自包含从PubChem网站提取的图形的在线来源。PubChem包含一百万个化学结构。每个图都有23.98个顶点，25.76条边，3.5个不同的顶点标签，平均2.0个不同的边标签，不同的顶点标签和不同的边标签的总数分别为81和3。大小PubChem数据集的大小为434 MB。对于我们的测试，我们生成3个lakhs图。我们还随机生成几组图查询表5真实的生物数据集。5.1.2. 实现平台我们在Java中实现了这项工作，并使用Hadoop（版本1.2.1）Map-Reduce的开源版本。数据库文件存储在Hadoop分布式文件系统（HDFS）中，HDFS是GFS的开源实现（Ghemawat等人，2003年）。我们的方法进行了所有的实验，使用一个本地集群与9个节点。在我们的测试中使用的处理节点配备了硬件：1 + 8节点集群前端：HP Proliant DL 380 P Gen 8，2 x Intel Xeon CPU E5-2640（2.5 GHz/ 6- core/15 MB/95 w）processor，64 GB RAM，333 X600 GB HDD machine; Storage：HP MSA 2040 SAN SFF/ 24 x300GBHDD/8⁄16GBPOETS;OS：RocksCluster6.1.1+CentOS6.5ServerwithHadoop 1.2.1.数据节点：英特尔至强E5-2640（2.5 GHz / 6核/15 MB/95瓦）处理器，16 GB RAM，2 X 300 GB硬盘机。5.2. 实验结果5.2.1. 在集中式与分布式平台上创建IGI该实验显示了集中式方法和分布式方法的时间变化。集中式方法意味着图形数据集度图每个图酵母79,59023.2P38841,47026SN12c40,00231.2OVCAR-840,51431.3NCI-H2340,35131.5MOLT-439,76330PC-327,50732SF-29540,26932SW-62040,53031S. Fathimabi等人/沙特国王大学学报31只有一台机器不使用Hadoop。单机配置：Intel i3处理器，8 GBRAM，500 GB硬盘。在这个实验中，我们使用了由12，000张图组成的合成数据集。表6显示了集中式和分布式方法所需的时间。这表明分布式方法可扩展到大型图形数据集。5.2.2. 集中式与分布式平台上的查询处理时间在这个实验中，我们对12，000个数据图进行了查询处理，这些数据图如表5所示，具有不同数量的查询图。Hadoop需要更少的时间，并且可以很好地扩展到大型图形数据库。表7显示了时间与查询图数量的关系。随着查询数量的增加，时间也会增加。5.2.3. 集成图索引构建时间与数据图数量在这个实验中，我们使用了由12，000个图形组成的合成数据集，并在9节点集群机器上执行。我们首先测试数据图数量的集成图索引创建时间。在这里，时间最初并没有增加，因为即使我们增加图形，数据也会分发到多台机器，因此需要相同的时间。图6示出了根据数据图的数量的时间变化。5.2.4. 使用基于标签的分区与基于结构的分区的在这个实验中，我们使用了由12，000个图组成的合成数据集，并在9节点集群机器上执行。该实验使用基于标签的划分算法和基于结构的划分算法进行。在这个实验中，我们使用了表5所示的合成数据集，并在9节点集群机器上执行。图7示出了LP和SP技术所花费的时间。与SP分区相比，LP占用的时间更少5.2.5. 基于标签的分区与基于结构的分区该实验是为了比较基于标签的划分和基于结构的划分。 图 8显示了当我们使用基于标签的分区和基于结构的分区时查询处理的比较。与基于标签的分区相比，基于结构的分区花费的时间更少。图6.集成图索引构建时间与数据图数量的关系图7.使用基于标签的分区与基于结构的分区的IGI创建时间表6集中式与分布式的集成图索引创建。数据集大小（图表数量，以千为单位）集中式算法所用时间（分钟）Hadoop所用时间（分钟）0.50.60.66120.7240.8471.5693.428155.212257.3表7集中式平台与分布式平台上的查询处理时间查询图的数量集中式算法所用时间（分钟）Hadoop所需时间10.050.04101814.6404719808526100 105 30图8.使用基于标签的分区与基于结构的分区的查询处理时间分区32S. Fathimabi等人/沙特国王大学学报图9.使用基于结构的分区与PPMG的查询处理时间。5.2.6. 基于结构划分的查询处理时间与现有算法PPMG的比较在这个实验中，我们使用合成数据集，我们在9节点集群机器上执行。进行该实验以比较基于结构的划分和PPMG（Kim等人， 2013年）。 图图9显示了基于分区的查询结构和PPMG的比较。PPMG和我们的方法所花费的时间有很大的不同。我们的基于结构的分区需要很少的时间相比，早期的算法PPMG。5.2.7使用REAL数据集创建集成图索引在这个实验中，我们使用了不同的真实数据集，并记录了集成图索引创建的运行时间我们考虑了五个真实的数据集，并显示了创建集成图索引所需的时间时间如图所示。 10个。5.2.8. 使用真实数据集的在这个实验中，我们使用了表5所示的真实数据集，并在集群机器上执行这里我们用了不同的数字图10.集成图索引创建与数据节点数量的性能评估。S. Fathimabi等人/沙特国王大学学报33我们记录了执行时间。如图11所示。我们执行了查询图的数量。如果查询图更多，则运行时间更多。5.2.9. 集成图索引创建时间与图分区技术在这个实验中，我们分析了不同的图分区技术和运行时间来创建集成图索引。 我们使用了表5所示的真实数据集。我们在9节点集群机器上执行。在这里我们使用了四种划分技术：默认图划分、基于密度的图划分、基于标签的图划分和基于结构的图划分。在这个实验中，我们记录了不同分区技术的集成图索引创建时间。在这里，我们比较了四种分区技术。与所有其他分区技术相比，默认分区需要很长时间。与基于标签的划分和基于密度的划分相比，基于结构的划分所花费的时间最少，如图所示。 12个。5.2.10. 使用真实数据集的在这个实验中，我们分析了不同分区技术的查询处理时间。在这里，我们使用了真实的数据集，图11. 查询图的数量与运行时间。图12.集成的图索引创建时间与图分区技术。图13. 查询处理时间与图分区技术。表8数据库更新时间。操作插入查询处理两总更新时间（秒）706080在表5中。我们在9节点集群上执行。我们记录了查询处理的运行时间，这里我们使用了100个查询。对于基于结构的分区，与所有其他分区技术相比，需要更少的时间。如图所示。 13岁5.2.11. 使用真实数据集在这个实验中，我们表明，除了高效的索引建设和快速查询处理，我们的索引也有一个非常低的维护成本。我们考虑三种不同的情况下的更新：插入，查询处理和两者兼而有之。我们使用酵母数据集进行该实验，如表5所示。仅对于插入，我们从60 K图的数据库开始，然后插入另外10 K图。对于这两种情况，我们都使用60 K图的数据库，并随机选择从另外10 K图和100个查询图中插入图。我们在在每种情况下所有更新结束60 K.我们在9节点集群机器上进行了这个实验。记录运行时间，如表8所示。从这个实验中，我们知道插入和查询处理可以同时进行，具有相同的计算复杂度和IO复杂度。6. 结论在本文中，我们提出了分布式方法来处理多个图查询的时间，而不是处理单个查询图。这种方法使资源得到最佳利用。提出了基于图的标号和基于图的结构基于结构的方法对于大型图数据集的查询处理更有效创建集成图索引的有效方法是与正常的集成图索引创建相比减小IG大小基于结构的划分减少了查询处理的通信成本和计算成本，即使它需要两轮MapReduce。该MSP适用于图形通用性较强的图形数据库在未来，我们想展示频繁子图挖掘如何从图索引中获益34S. Fathimabi等人/沙特国王大学学报⁄ing，我们希望使用内存中的分布式框架Spark来实现。引用Angles，Renzo，2012.当前图形数据库模型的比较。在：数据工程研讨会（ICDEW）（编辑），IEEE第28届国际会议IEEE，pp. 171比177Aridhi，Sabeur，d'Orazio，Laurent，Maddouri，Mondh