【论文阅读】An Overview of Reachability Indexes on Graphs

Chao Zhang, Angela Bonifati, and M. Tamer Özsu. 2023. An Overview of Reachability Indexes on Graphs. In Companion of the 2023 International Conference on Management of Data (SIGMOD '23). Association for Computing Machinery, New York, NY, USA, 61–68. https://doi.org/10.1145/3555041.3589408

ABSTRACT

图一直是建模实体和它们之间的关系的自然选择。最基本的图处理运算符之一是可达性查询，它检查在普通图中是否存在从源到目标顶点的路径，以及该路径是否能够基于边缘标记图中的边缘标签满足给定的路径约束。由于这些查询固有的可传递性，处理可达性查询可能需要访问图的很大一部分。这使得在大图上评估它们的代价高昂。因此，在过去的三十年里，人们花费了大量的精力来设计索引技术，构建先进的数据结构来有效地压缩图的传递闭包，从而加速在线查询处理，即可达性索引。在本教程中，我们将对现有的可达性索引进行深入的技术回顾，从那些为普通图设计的索引到那些为边缘标记图设计的索引。我们通过总结将这些技术集成到gdbms中的开放挑战来总结本教程。

1 INTRODUCTION

图在建模真实数据[32]中无处不在，其中将关系表示为一流对象很重要——顶点表示实体，边表示关系。这些例子可以在不同的领域中找到，如生物网络[28]、金融网络[30]、社交网络、交通网络[4]和知识图[16]。使用图形结构的数据，其中一个最有趣的查询是检查从一个顶点到另一个顶点的有向路径的存在性，即在网络中从一个实体到另一个实体的传递关系，这被称为可达性查询（𝑄𝑟）。可达性查询是一种著名的基本图形数据处理操作符，在[36,37]实践中得到了广泛的应用。一些人认为它们是最有趣的面向图的查询[38]。
教程大纲。在本教程中，我们将深入回顾每种类型的可达性索引。我们从图上可达性查询的背景开始教程，然后是简单可达性索引(3)和路径约束的可达性索引(4)。我们将讨论开放的挑战(5)。我们共享我们的愿景，即在现代gdbms中为可达性查询提供成熟的索引。

2 BACKGROUND

我们采用图𝐺=（𝑉，𝐸）的共同定义，其中𝑉是一组顶点，𝐸是一组边，而𝑒∈𝐸⊆𝑉×𝑉。本文的边是有向的。随着图的丰富，这个定义将得到增强。因此，问题是根据𝑄𝑟中的参数来检查𝐺中路径的存在性。

2.1 Plain reachability

普通图遵循上述定义𝐺=（𝑉，𝐸）。图1(a)显示了一个平面图。在普通图上的可达性查询被称为普通可达性查询。普通的可访问性查询Qr （s， t） 包含一对参数，一个源顶点 s ∈ V 和目标顶点 t ∈ V ，Qr （s， t） 检查是否存在G中从s到t的路径，称为s-t路径，例如，在图1（a）中，Qr （A，G） = true，因为 s-t 路径 （A， D， H，G）。

2.2 Path-constrained reachability

有边缘标记的图可以包含不同类型的关系，其中每条边都被分配了一个特定的标签，例如，RDF图[15]。在这种情况下，该图被定义为𝐺=（𝑉，𝐸，𝐿），其中𝐿是一组标签，每个𝑒∈𝐸被分配一个标签𝑙∈𝐿。图1(b)显示了一个边缘标记的图，代表了一个具有三种关系的社交网络，即𝐿={朋友，跟随，worksFor}。边标记图上的可达性查询可以使用边标签[21,52]对路径的附加约束来表示，称为路径约束可达性查询。路径约束的可达性查询𝑄𝑟（𝑠，𝑡，𝛼）包含作为参数的源（𝑠）和目标（𝑡）顶点，以及使用𝐿指定路径约束的表达式𝛼。𝑄𝑟（𝑠，𝑡，𝛼）检查𝐺中是否存在𝑠-𝑡路径，以便该路径能够满足𝛼强制执行的约束。一般来说，𝛼被定义为一个正则表达式，使用边标签𝑙∈𝐿作为文字字符，并使用连接的“·”、交替的“∪”和Kleene运算符（星号“∗”或加号“+”）为元字符，由以下语法生成：𝛼：：=𝑙|𝛼·𝛼|𝛼∪𝛼|𝛼+|𝛼∗。由𝑄𝑟（𝑠，𝑡，𝛼）中的正则表达式𝛼强制执行的路径约束是，𝑠-𝑡路径的边缘标签序列应该在𝛼的语言中形成一个单词。例如，如果𝛼=（friendOf ∪ follows）∗，那么图1(b)中的𝑄𝑟（𝐴，𝐺，𝛼）=𝑓𝑎𝑙𝑠𝑒，因为从𝐴到𝐺的每个路径都包括工作表sfor。使用正则表达式作为路径约束的路径查询称为正则路径查询（RPQ）[1,3]，而路径约束的可达性查询是RPQ的一个子类，它检查是否存在可以满足由正则表达式定义的路径约束的𝑠-𝑡路径。路径约束可达性查询已广泛应用于图分析中，如社会网络中的社会关系分析、生物网络中蛋白质的交互路径分析、金融交易网络中的洗钱检测等。

2.3 Reachability processing

纯可达性查询可以通过执行在线遍历[50]来处理，例如，宽度优先遍历（BFS）、深度优先遍历（DFS）或双向宽度优先遍历（BiBFS）。然而，这些方法访问了图的大部分，这对于大型图是非常低效的。路径约束的可达性查询可以通过引导图遍历来处理：根据查询中的正则表达式𝛼构建一个有限自动机（FA），然后遍历由FA [3,5]引导遍历。然而，由于𝛼中存在Kleene操作符，该图的很大一部分仍然需要访问。
加速普通可达性查询的简单方法是构建一个传递闭包（TC）[2]，它可以扩展到路径约束的可达性查询，称为广义传递闭包（GTC）[21,52]。TC计算并存储图中每对顶点之间存在路径的路径。虽然使用TC进行查询处理只需要恒定的时间，但高的计算和存储成本使得它在实践中不可行。GTC通过添加边缘标签的附加信息来扩展TC，以处理路径约束的可达性查询。然而，GTC的计算比TC的计算更具挑战性，因为在图中根据大量可能的路径约束需要额外的路径区分。因此，计算GTC在实践中也是不可行的。
在过去的三十年里，重要的研究都集中在设计先进的数据结构来有效地计算和存储tc或gtc，同时为（普通/路径约束的）可达性查询提供高效的处理。这些先进的数据结构被称为可达性索引[2、7-11、13、14、17-20、25-27、29、31、34、35、39-41、43、45、46、49-51、55]。设计可达性指标的一般直觉是减少在构建tc或gtc时可达性信息的冗余记录，并在不同可达的顶点对之间存储简洁的信息。这使得推导出图中任意一对顶点的可达性成为可能。派生过程应该比使用在线图遍历的查询处理所花费的时间要少得多，这使得索引变得有趣。有两种不同类型的可达性索引反映了可达性查询：普通可达性索引[2、7-9、11、13、14、17-20、25-27、29、31、34、35、39-41、43、45、46、49-51、55]和路径约束的可达性索引[10,12,21,33,44,52,56]。

3 PLAIN REACHABILITY INDEXES

现有的纯可达性索引可以根据底层框架分为三个主要类别：树覆盖[2]、2跳标记[14]和近似TC [46]。纯可达性指标汇总见表1。“索引类型”列表示索引是部分的还是完整的。完整的索引可以通过仅使用索引查找来处理查询，而部分索引则需要额外的图形遍历。输入列表示索引假定为输入的图类型：有向无环图，一般图。动态列指示索引是否可以支持图形更新，即边/顶点的删除和插入。

3.1 Tree-Cover-Based Indexes

树覆盖指数[2]的基础是附加到每个顶点的一个或多个间隔，用来处理可达性问题设[𝑎𝑣，𝑏𝑣]表示附加到顶点𝑣的区间。树覆盖方法定义在一般图的生成树上，然后扩展到处理没有被生成树覆盖的边。因此，我们可以识别出三种基本结构：(1)树；(2) DAGs；和(3)一般图形。基于树覆盖框架，在表1的第一个块中列出了索引技术[9,17,24,27,40,43,50,51]。附加到顶点的间隔是不同的。
树的间隔标签。在这类技术中，对于每个顶点𝑣，𝑏𝑣是通过树的根遍历得到的𝑣的后阶数，𝑎𝑣是树中所有𝑣后代中最低的后阶数。𝑄𝑟（𝑠，𝑡）可以通过检查是否有𝑏𝑡∈[𝑎𝑠，𝑏𝑠]来处理。直觉上，𝑄𝑟（𝑠，𝑡）可以通过检查𝐺生成树中根于𝑠的子树是否包含𝑡来处理，并且分配给顶点的间隔编码了足够的信息来进行检查。
在DAGs中的可达性。当使用区间标记方法来处理DAG中的可达性时，出现了一个主要问题：如果顶点𝑡只能通过包含非树边的路径从顶点𝑠中到达，那么区间标记就不能捕获这些路径。在原始的树覆盖方法中，首先基于DAG的生成树计算顶点区间，然后继承顶点区间。对于间隔为[𝑎𝑢，𝑏𝑢]和[𝑎𝑣，𝑏𝑣]和𝑏𝑣∈的非树边（𝑢，𝑣），为了记录𝑣可达from𝑢，𝑢从𝑣继承[𝑎𝑣，𝑏𝑣]。因此，𝑢有两个间隔[𝑎𝑢，𝑏𝑢]和[𝑎𝑣，𝑏𝑣]。由于可达性的传递性，树边也需要间隔继承，例如，对于树边（𝑤，𝑢），可以从𝑤访问𝑣，这样𝑤需要从𝑢继承[𝑎𝑣，𝑏𝑣]。DAG中的顶点以反向拓扑顺序来继承间隔。如果一个顶点的间隔恰好是相邻的，它们可以合并以有效地存储，例如，间隔[1,6]和[7,8]可以合并到间隔[1,8]。
从循环图到dag。具有有向循环的一般图可以利用一种有效的约简方法（Tarjan的算法[42]）在线性时间内转换为DAG。具体来说，所有的强连接组件（SCC），其中每个顶点都可以从每个其他顶点到达，都被识别出来，每个SCC被粗化为一个有代表性的顶点。该转换的输出将是一个DAG。然后，可以处理𝑄𝑟（𝑠，𝑡），首先检查𝑠和𝑡是否属于同一个SCC，然后使用上面讨论的DAG方法在不同的SCC中检查DAG中的可达性。因此，由于泛化很容易，文献中大多数普通可达性指标都假设dag作为输入。
简而言之，树覆盖索引是具有区间继承的区间标记方法。树覆盖方法的主要缺点是，由于图中可能存在非树形边，因此每个顶点可能需要从其他顶点继承区间。索引大小定义为分配给顶点的间隔总数，一个DAG可以被不同形状的生成树覆盖，从而导致不同的索引大小。最优的树覆盖度[2]可以导致最小的指数大小。然而，基于最优树覆盖度计算最小大小指数的复杂度与计算TC [2]的复杂度相同，这在实践中是难以实现的高。
[9,40,50]的一些后续工作旨在减少每个顶点的间隔数量。这些工作采用了两种类型的设计来减少间隔的数量： (1)准确地记录𝑘的间隔（例如，GRAIL [50]）和(2)以最多的𝑘间隔进行记录（例如，法拉利[40]），其中𝑘是一个输入参数。在GRAIL中，𝑘的时间间隔是通过使用𝑘的随机生成树来计算的。在法拉利中，即使区间不相邻，也会合并区间，以保证每个顶点的最大区间数不大于𝑘，从而导致近似区间的存在。这两种方法都不计算完整的索引，使用索引查找的查询结果可能包含假阳性，但没有假阴性。因此，这些部分索引可以用于指导在线遍历，以计算正确的查询结果。尽管部分索引需要额外的图遍历来进行查询处理，但它们的索引构建时间和索引大小与输入图的大小呈线性关系，这使得它们成为具有数百万个顶点的大型图的第一个可行的方法之一。此外，使用这些索引的可达性处理可以比只使用图遍历快一个数量级。颗粒扩展了匕首[51]中的动态图。
一些早期的工作扩展了区间标记，包括双标记[17]、GRIPP [43]和路径树[24,27]。然而，他们复杂的设计可能无法处理当前现实世界的图形。具体来说，双标记和路径树是为树状结构设计的，例如XML数据库，只有当非树边的数量非常低时，它们对图的应用才很有效。虽然GRIPP是一个部分索引，但如果部分索引返回false，它就需要遍历图，这与圣杯和法拉利的设计相比没有竞争力，因为它们的部分索引返回的查询结果中没有假阴性。

3.2 2-Hop-Based Indexes

2跳标记位于传递闭包物化和在线搜索（BFS、DFS、BiBFS）之间。在2跳index [14]中，每个顶点𝑣∈𝑉都被标记为两组顶点：𝐿𝑖𝑛（𝑣）和𝐿𝑜𝑢𝑡（𝑣）。一个vertex𝑢∈𝐿𝑖𝑛（𝑣）if𝑣是可访问的from𝑢，对于𝐿𝑜𝑢𝑡（𝑣）也是如此。下面将讨论这些集合的构造。𝑄𝑟（𝑠，𝑡）的处理方法是检查： (1)𝑠∈𝐿𝑖𝑛（𝑡）；(2)𝑡∈𝐿𝑜𝑢𝑡（𝑠）；(3)𝐿𝑖𝑛（𝑡）∩𝐿𝑜𝑢𝑡（𝑠）=∅，是否满足以下情况之一，即我们可以通过确定是否至少存在一个共同的hop𝑢来计算是否可以从𝑠获得𝑡。基于2跳索引的索引[7,8,13,18,25,26,29,39,49,55]的索引技术。请注意，与树覆盖索引不同，2跳索引可以直接应用于一般图。
对于具有𝑛个顶点的图，2跳索引的索引大小为I𝑛𝑖=1|𝐿𝑜𝑢𝑡（𝑣𝑖）|+|𝐿𝑖𝑛（𝑣𝑖）|。最小的2跳索引是索引大小最小的索引。计算最小的2跳索引是np硬的[14]。在2跳指数的原始工作中，提出了一种近似算法。然而，时间复杂度是𝑂（𝑛4），这对于大型图是不可行的。
有效地计算2跳索引，同时最大限度地降低索引大小一直是一个长期存在的问题。已经提出了高级启发式方法，包括TFL [13]、DL [25]、PLL [49]和TOL [55]。TOL是一种计算以顶点总顺序为输入的2跳索引的通用方法，TFL、DL和PLL是TOL的实例化，即，每个方法都使用总顺序的实例化。让𝑜是𝑉上严格的总顺序，𝑜（𝑣）是𝑜中𝑣的排名。TOL应用于每个顶点𝑣∈𝑉，对于𝑣访问的每个顶点𝑢，只有当𝑢∈𝑉满足𝑜（𝑢）>𝑜（𝑣）时，TOL才将𝑣分别添加到𝐿𝑜𝑢𝑡（𝑢）和𝐿𝑖𝑛（𝑢）。如果一个顶点𝑤使得𝑜（𝑤）<𝑜（𝑣）被来自𝑣的前后向BFSs访问，则BFSs立即终止，即根据总阶𝑜修剪计算进出每个𝑣的可达性路径的搜索空间。𝑜的实例是DAG的拓扑顺序（在合并所有SCCs后获得），这是TFL中使用的策略。𝑜的另一个实例是基于顶点度，在DL和PLL中采用。已经证明了DL和PLL是等价的[25]。
基于2跳索引的一些工作也研究了如何适应动态图。TOL可以通过利用顶点的总顺序来处理插入和删除。DBL [29]是最近基于仅为插入设计的2跳索引的建议。U2-跳[7]方法和Ralf等人[39]的方法研究了动态图上的维护，但已经证明它们不能扩展到大图[55]。
有一些2跳索引的扩展。早期的工作用图结构替换了可达性路径中的中间顶点，即3跳索引[26]中的链和路径索引[8]中的树。尽管这些方法可以进一步减少索引的大小，但与最近的2跳索引相比，它们需要更多的时间来构建索引。O‘Reach [18]是最先进的索引之一，它通过选择𝑘个顶点来构建一个部分的2跳索引，并以扩展的拓扑顺序处理查询。

3.3 Approximate Transitive Closure

设𝑂𝑢𝑡（𝑣）是图中从𝑣可以到达的所有顶点的集合（注意，这与前面定义的𝐿𝑜𝑢𝑡（𝑣）不同）。然后，对一个图的TC的计算基本上是计算图中每个顶点𝑣的𝑂𝑢𝑡（𝑣），这在实践中是不现实的。近似TC的直觉是在有效地计算出𝑂𝑢𝑡（𝑣）的近似版本。我们使用𝐴𝑃（）来表示近似函数。请注意，|𝐴𝑃（𝑂𝑢𝑡（𝑣））|≪|𝑂𝑢𝑡（𝑣）|。𝐴𝑃（）函数需要仔细设计，以便它提供正确的查询结果，而不是随机的查询结果。𝐴𝑃（）的设计可以通过以下观察结果来指导。如果已知顶点𝑡可以从图中的顶点𝑠到达，则使用𝑂𝑢𝑡（𝑡）⊆𝑂𝑢𝑡（𝑠）。如果𝐼𝑛（𝑣）被定义为对偶的，即它包含了到达𝑣的所有顶点，则可以得到类似的观察结果，即，如果𝑡是可以从s到达的，则𝐼𝑛（𝑠）⊆𝐼𝑛（𝑡）。虽然这个观察结果没有意义，因为它与处理𝑄𝑟（𝑠，𝑡）相矛盾，但事实证明，反正条件可以被利用：如果𝑂𝑢𝑡（𝑡）不是𝑂𝑢𝑡（𝑠）的子集，那么从图中的𝑠无法访问𝑡。因此，只要𝐴𝑃（）函数保留了反向阳性条件——如果𝐴𝑃（𝑂𝑢𝑡（𝑡））不是𝐴𝑃（𝑂𝑢𝑡（𝑠））的子集，那么𝑂𝑢𝑡（𝑡）就不是𝑂𝑢𝑡（𝑠）的子集——使用𝐴𝑃（）函数构建的近似TC就不会提供假阴性。
𝐴𝑃（）函数的第一个设计使用了k-min级的独立排列，导致IP索引[46,47]，然后使用BFL [41]中的Bloom滤波器，这是最先进的纯可达性索引技术之一。使用IP或BFL的查询处理没有假阴性，因为相应的𝐴𝑃（）函数可以保留反向阳性条件。然而，可能存在假阳性，这就需要额外的图遍历。类似于基于树覆盖框架的部分索引技术的情况，可以通过递归查询索引来修剪图的遍历，也就是说，如果v的所有的邻居(当前通过从源顶点的遍历访问的顶点)没有到达目标顶点，那么可以在遍历中跳过𝑣。

3.4 Other Techniques

提出了一些图约简技术来加速可达性索引，包括圣龟子[23]、ER [54]和RCN [53]。这些约简技术与索引技术是正交的。其他一些不使用前面讨论的三个索引框架的技术也存在于文献中，包括HL [25]、Feline [45]和Preach [31]。通常，这些索引都有自己的设计来处理可达性查询。一些早期的工作研究了在动态图上的传递闭包或SCCs的维护，包括[19,34,35]，但这些方法不能扩展到大型图[55]。

4 PATH-CONSTRAINED REACHABILITY INDEXES

支持路径约束可达性查询的可达性索引𝑄𝑟（𝑠，𝑡，𝛼）通常是为特定类型的路径约束表达式𝛼而设计的。基于𝛼的规范，有两种类型的路径约束的可达性查询：基于交替的查询，其中𝛼=（𝑙1∪𝑙2∪…）∗，∀𝑙𝑖∈𝐿[12,21,33,44,56]，和基于连接的查询，其中𝛼=（𝑙1·𝑙2·…）∗，∀𝑙𝑖∈𝐿[52].不幸的是，目前没有索引可以支持这两个查询类；已经为其中一个或另一个提出了索引，如表2所示。如表中所示，有三个索引类支持基于交替的查询：(1)基于树的查询、(2) 2-hop和(3) GTC。前两个是普通图的对应对象的扩展，而GTC是一个扩展TC，由该查询类型的边缘标签信息丰富。只有一个索引。在其余的部分中，我们将讨论每个这些索引类。

4.1 Indexes for Alternation-Based Queries

边缘标签的交替定义了一组标签 L′ ⊆ L，并且Qr （s， t， α） 中的路径约束强制要求 s-t 路径只应包含带有 L 格式标签的边′，例如，如果 α = （friendOf ∪以下）∗
，然后按 L′ = {friendOf， follows}，和 Qr （A，G， α） =f alse在图1（b）中。基于交替的可访问性查询也是称为标签约束可访问性 （LCR） 查询。
足够的路径标签集。Jin等人的[21]首先研究了基于不同范围的可达性查询的索引问题，其中提出了基于索引这些查询的边缘标签信息的两个基础。第一个基础是，如果有两条𝑠-𝑡路径，边缘标签集为𝑆1、𝑆2和𝑆1⊆𝑆2，那么𝑆2是冗余的，这意味着在索引中记录𝑆1就足够了。边缘标签集，如因为𝑆1被表示为充分的路径标签集（SPLS）。例如，在图1(b)中，顶点M可以通过两条路径从顶点L到达：𝑝1=（L、工作、C、工作、M）和𝑝2=（L，跟随，K、工作、M），𝑝1的标签集是𝑝2的标签集的一个子集，这样前者是从𝐿到𝑀的SPLS。第二个基础是，通过计算顶点𝑠到顶点𝑢和顶点𝑢到顶点𝑡的路径的交叉积（SPLSs的传递性），可以得到从顶点𝑠到顶点𝑡的SPLSs。例如，在图1(b)中，从A到M的SPLS是{遵循，工作sFor}，可以使用从A到L的SPLS，即{遵循}，以及从L到M的SPLS，即{worksFor}。

4.1.1 Tree-Based Indexes

第一种索引方法是由Jin等人[21]提出的，该方法包括一个富含SPLSs的基于树的索引和一个非树边路径的部分GTC。一般的想法是将图中的路径描述为两种情况：情况(1)路径中的第一条或最后一条边是树边，情况(2)第一条边和最后一条边都不是树边。预先计算了一个包含SPLSs的部分GTC，以处理在情况(2)中由路径引起的可达性。情况(1)中路径的可达性是通过组合生成树和部分GTC来处理的，即访问生成树中源的后继者和目标的前任，然后对每个可能的后继者-前任对检查部分GTC。提出了两种优化技术来加快查询处理的速度。第一个优化是基于区间标记，以有效地找到生成树中的后继者和前身。第二个优化是记录从生成树的根𝑟到生成树中的每个顶点的路径的SPLSs中单个边缘标签的出现情况。然后，可以通过从树中𝑟-𝑡路径的SPLS减去𝑟-𝑠路径的SPLS来计算生成树中𝑠-𝑡路径的SPLS。
Chen等人的[12]提出了最先进的指标之一。该方法使用生成树对边缘进行分类，并区分由不同类引起的可达性。具体来说，在𝐺中计算生成树（或森林）𝑇后，将有向边（𝑢，𝑣）分为四个不相交的类： (1)树边（𝑢，𝑣）是𝑇中的边；(2)𝑣是𝑇中𝑢的后代是前边；(3)𝑣是𝑇中𝑢的祖先是后边；(4)如果𝑣在𝑇中既不是𝑢的祖先或后代，则是交叉边。树边和前边组合在一起形成树状结构，记为T。T中的可达性信息可以通过区间标记方法进行有效编码。更准确地说，在𝑇已经有一个路径为每个前沿T，间隔标签建立𝑇能够编码普通可达性信息T为了有效地记录T，第二优化技术方法之前讨论[21]，即记录T的根T的路径和每个𝑣每个SPLS边标签的出现。然后，压缩𝐺，只保留可以传递由交叉边引起的可达性信息的顶点和边，从而得到一个摘要𝐺𝑐。因此，𝐺被分解为（T，𝐺𝑐）。然后将𝐺𝑐作为输入，记为𝐺1，并进一步分解为（T1，𝐺𝑐1），分别为𝐺1的树状结构和图摘要。该方法采用递归分解方法，直到𝐺𝑖的分解只包含一个树状结构T𝑖。分解的一系列以结果作为该方法的指标。在每个分解结果（T𝑖，𝐺𝑖𝑐），𝐺𝑖后边缘引起的可达性信息考虑通过执行在线搜索的优化，例如，后边缘（𝑢𝑣）和（𝑢，𝑣），如果𝑢是𝑣的后代，那么他们被链接到一个路径（𝑢，𝑣）。最后，将𝑄𝑟（𝑠，𝑡，𝛼）递归分解为子查询，这些子查询通过在线搜索对序列（T，T 1，…）进行评估，如果使用T𝑖可以找到满足𝛼的𝑠-𝑡，则返回查询结果𝑡𝑟𝑢𝑒。

4.1.2 GTC-Based Indexes

Zou等人对基于交替可达性查询的GTC问题进行了广泛的研究。基本步骤是计算单源GTC，例如，计算从源顶点可到达的所有顶点和相应的spls。提出了一种类似于dijkstra的算法，利用路径标签集中不同标签的数量来模拟顶点之间的距离。考虑从图1(b).中的顶点𝐿计算单源GTC从𝐿可以通过两条路径访问𝐻：𝑝3=（𝐿、𝐻、𝐶、𝐻、𝐻）和𝑝4=（𝐿、𝐻、𝐷、𝐻fof、𝐻）。Path𝑝3比𝑝4更短，因为𝑝3只有一个不同的标签，而𝑝4有2个。因此，𝑝3被扩展为计算从𝐿到𝐺的SPLS，而忽略𝑝4。首先将输入图转换为DAG，然后按照DAG的拓扑顺序进行计算，以自底向上的方式共享顶点的单源GTC。基于交替的可达性的一般图到DAG的转换比第3节中讨论的普通可达性的转换要复杂得多，因为由于不同的SCCs中的路径是不等价的。每个SCC都被一个具有入口内顶点和入口外顶点的二部图所取代。SCC中的一个顶点𝑣是入口内（或出入口），如果𝑣至少有一条来自SCC外的顶点的传入（或输出）边。然后，计算从入口内到入口外顶点的spls，并记录在索引中。在计算每个SCC内的可达性信息时，通过从高度顶点开始计算，进一步优化了类dijkstra算法的计算；利用这些顶点的单源GTC来修剪后续计算的搜索空间。并讨论了动态图上的索引维护问题。
提出了一个在线BFS的部分索引[44]。部分索引是图中顶点子集的一组单源gtc。顶点的子集被选择为top-𝑘度排名的，称为地标顶点。𝑄𝑟（𝑠，𝑡，𝛼）是通过在从𝑠遍历期间击中地标顶点时，利用部分索引加速执行BFS来处理的。如果一个地标顶点𝑣的单源GTC被来自𝑠contains𝑡的BFS击中，那么该方法返回true。否则，在约束𝛼下从地标𝑣可到达的所有顶点都可以在后续的搜索中进行修剪。此外，通过计算从非地标顶点到地标顶点的路径的可达性和SPLSs，进一步改进了查询过程，其中索引路径的数量由一个预定义的参数控制。

4.1.3 2-Hop-Based Indexes

P2H+ [33]是一个基于2跳的可达性索引，用于基于交替的可达性查询。该索引利用2跳索引作为框架，并添加spls来处理路径约束。2跳索引算法是一种扩展通过利用2跳可达性和SPLSs的传递性来建立P2H+指数。P2H+的索引算法根据顶点度（从高到低）排序的顶点进行后向和前向BFSs，期间采用剪枝规则跳过冗余遍历。此外，索引算法可以保证构建的索引不包含任何冗余，这是通过优先访问的边缘标签已经包含的路径从𝑣当前边界顶点BFS从每个顶点𝑣。
DLCR [10]是最先进的索引之一，它扩展了P2H+，以支持图形更新，包括边缘插入和删除。当一条边被更新时，DLCR将识别出一组需要执行反向和正向BFSs的节点，以将更新反映到索引中。为边缘更新执行的BFS只需要遍历包含已更新边的路径。在BFS遍历期间，DLCR进一步识别需要额外索引更新的受影响的顶点，以删除冗余（在边缘插入的情况下）或保持索引正确（在边缘删除的情况下）。一般来说，在边插入的情况下，新插入的边可能会使现有的索引项冗余，需要删除。对于DLCR中的每个索引条目𝐼𝐸，可能都有由于𝐼𝐸而冗余的索引条目，因此这些被称为𝑅𝐼𝐸的冗余索引条目集不包含在DLCR中。但是，如果反映由被删除的边缘引起的更改的更新需要删除𝐼𝐸，那么𝑅𝐼𝐸中的索引条目可能会变得非冗余，因此需要将它们插入DLCR以保持索引正确。

4.2 Indexes for Concatenation-Based Queries

串联的边缘标签定义了一个序列，和相应的路径约束𝑄𝑟（𝑠，𝑡，𝛼）强制𝑠-𝑡路径的边缘标签序列必须是任意数量的重复序列的连接边缘标签定义在𝛼Kleene操作符，例如.，𝑄𝑟（𝐿，𝐵，工作·朋友）∗)=𝑡𝑟𝑢𝑒在图1(b).基于连接的可达性查询也被称为递归标签连接（RLC）查询。
Zhang等人[52]首先研究了基于连接的可达性查询问题，提出了RLC索引。为了索引这些查询，将记录边缘标签序列的最小重复次数（MR），例如，路径的先生（L、工作、D、友谊、H、工作、G、工作、B）是（工作、朋友），并且先生对processing𝑄𝑟（𝐿、𝐵、工作、友谊）∗)有帮助。RLC索引利用了2跳索引框架，并记录了边缘标签序列的MRs。记录MRs可能是禁止的，因为存在无限的𝑠-𝑡路径，作为定向循环的路径的结果。为了解决这一挑战，我们利用了𝛼中Kleene算子下的连接长度来指导MRs的计算。第二个挑战是，先生不一定有传递属性，例如，它是不可行的先生𝑠-𝑡路径的内存𝑠-𝑢路径和𝑢-𝑡路径（𝑙1）和（𝑙2），分别。因此，RLC索引的索引算法将索引构建过程分为两个阶段：第一阶段计算任何阶段（𝑠，𝑡）的所有可能的MRs，第二阶段选择传递的MRs来构建索引。提出了剪枝规则，以避免冗余计算和记录。

5 OPEN CHALLENGES

最先进的简单可达性索引可以有效地为一个大型图构建，例如，BFL可以在几秒钟内就可以在具有数百万个顶点的图上构建，而索引大小只有几百兆字节。主要的挑战是这些先进的索引技术，即具有引导图遍历的部分索引，主要是为静态图设计的。唯一可以处理图形更新的方法是匕首[51]、IP [47]和DBL [29]。然而，IP中采用的动态方法是基于匕首，并不比BFS [55]快，DBL只能支持只插入图。拥有部分索引，可以高效地处理查询和处理插入和删除的图更新，这是非常有趣的。
部分索引只在输入图中记录部分可达性信息，以便它们可以缩放到大型图。𝑄𝑟（𝑠，𝑡）可以通过执行在线遍历来处理，这可以通过在部分索引中使用索引查找来指导。设𝑣为𝑠在线遍历过程中的当前边界顶点。在没有假阳性的部分索引中，如果评估𝑣到𝑡可达性的索引查找返回true，在线遍历可以立即终止。在没有假阴性的部分索引的情况下，如果用来评估从𝑣到𝑡的可达性的索引查找返回false，则在线遍历不需要访问𝑣的传出邻居。从过去三十年来普通可达性索引技术的发展来看，我们观察到部分索引在使可达性索引扩展到大型图方面发挥着重要作用，即，以现实的索引成本获得有效的查询处理。更重要的是，仅使用索引查找（如GRAIL、法拉利、IP和BFL）在查询结果中没有假阴性的部分索引具有明显的优势。这是因为如果一个顶点𝑡不能从𝑠到达，𝑄𝑟（𝑠，𝑡）可以立即停止，并且在现实世界的图中会有许多这样的顶点𝑠。
根据表2，路径约束可达性查询的唯一部分索引是地标索引。但是，地标索引是没有假阳性的部分索引，这意味着如果索引返回false，则必须继续进行查询处理的在线遍历。如上所述，在现实世界的图中，很可能会有许多顶点可能无法从给定的源顶点到达，因此，对于路径约束的可达性查询，有一个没有假阴性的部分索引是很有趣的。同样重要的是，我们观察到路径约束可达性指数的索引构建成本很高，并且对于具有数百万顶点[10,12,33,52]的图需要数小时的索引。这也要求设计没有假阴性的部分索引。类似地，在集成到gdbms中时，还应该考虑到动态图更新的实际问题。
路径约束可达性索引的另一个重要挑战是，现有的解决方案只能处理特定类型的路径约束𝛼，如表2所示。然而，真实世界的查询日志分析[6]已经表明，实际的路径约束有更多的类型。对一般路径约束使用一种索引技术，从而实现常规路径查询[5]的整个片段，这将是非常有趣的。
最后，索引的并行计算（例如，并行2跳索引[22]）也值得探索。文章来源地址https://www.toymoban.com/news/detail-771679.html

到了这里，关于【论文阅读】An Overview of Reachability Indexes on Graphs的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！