【论文笔记】Landmark Indexing for Evaluation of Label-Constrained Reachability Queries

Our contributions
在我们的工作中,我们弥补了这种情况,提出了第一个LCR指数解决方案,规模大图。我们的方法利用了基于陆landmark记的索引这一概念简单的思想,这一思想已被证明对于标准(无约束)可达性查询处理是成功的[1,2,19,33]。简而言之,我们的方法选择少量的landmark顶点,并预先计算从landmark回答关于LCR的查询所需的所有信息。在查询时,我们基本上执行一个基于标签的广度优先搜索(BFS),但是我们尽可能利用存储的信息来获得从landmark到目标顶点的捷径。
为了进一步提高查询性能,我们提出了两个扩展:一个是为了在BFS期间更快地找到landmark,另一个是为了即使从找到的landmark到目标顶点没有捷径,也能有效地找出不相关的顶点。
我们证明了我们的方法可以将更大的图缩放到几个数量级,并且比当前解决方案的查询评估速度快几个数量级。此外,我们的解决方案不是过于复杂,因此具有良好的实际影响潜力。

4.1 Overall idea



仅这一观察不足以使索引时间和索引大小足够小。为了进一步减少索引时间和索引大小(以查询时间为代价),我们只为少量顶点构建索引,称为landmark。给定一个查询(s,t,L),我们从s开始进行一个BFS(考虑标签)。当我们到达一个构造了索引的landmark s时,我们使用它来立即获得答案。

4.2 Indexing algorithm
我们的索引算法的目标是,在选择一小组landmark之后,构建一个索引,使得landmark的索引是complete and sound的,而非landmark的索引是空的。有了这样一个索引,我们可以立即通过检查我们是否有一些L0⊆ L的(t,L0) ∈ Ind(s)来回答一个landmarks的查询(s,t,L)。虽然非landmark的索引在这一点上是不相关的,但我们将为它们构造合理但不完整的索引,以使我们的方法在第5节中更有效。





4.5 Space and time complexity
在这一节中,我们分析了我们方法的空间和时间复杂性。为了简单起见,我们假设O(logn)位和O(|L|)位适合一个寄存器,我们可以在恒定时间内对寄存器执行操作。
我们首先分析我们的方法的索引大小。每个标志最多需要存储n-1个顶点,每个顶点最多存储2|L|个标签集。由于标志的数量为k,索引中的条目总数为O(nk2|L|)。由于每个条目需要0(logn+| L |)位,因此总索引大小为0(nk2 | L |(logn+| L |))位。
接下来,我们分析了索引构建的时间复杂度。对于每个地标v ∈ VL,我们可以将n2 | L |个条目推送到优先级队列。每次推送需要0(logn)时间。对于每个标签集L,我们可以遍历每个边。因此,除了对TryInsert和ForwardProp的调用之外,我们需要O((nlogn + m)2|L|)时间。请注意,每次调用TryInsert都需要O(2|L|)时间。ForwardProp对TryInsert的每次调用都是在没有ForwardProp的情况下进行的。因此,转发不会增加总的时间复杂度。总结一下,总时间复杂度为O(k((nlogn+m)2 | L |+N2 | L | 2 | L |)= O((n(logn+2 | L |)+m)k2 | L |)。
最后,我们分析了处理查询的时间复杂度。在最坏的情况下,我们在图O(n + m)上做一个完整的BFS,并可能为k个地标中的每一个运行QueryLandmark。每次调用QueryLandmark都会将L与最多2 | L |个标签集进行比较。因此,处理查询的时间复杂度为O(n + m + k2|L|)。

5.EXTENDED LANDMARK INDEX
5.1Indexing non-landmarks

LI方法的第一个问题是,给定一个查询(s,t,L),可能需要很长时间才能找到一个地标。
我们通过为非地标建立一个合理但不完整的索引来解决这个问题。





5.2Pruning for accelerating false-queries
第二个问题是,真查询和假查询之间的性能可能有很大的不对称。这与一个事实有关,即真查询可以在找到地标后立即停止,而假查询通常需要在返回假之前探索图形的更大部分。


为所有L ⊆ L计算和存储RL(v)是不切实际的。因此,对于每个地标v ∈ VL,我们引入一个集合reachableBy(v),并且只为L ∈ L保留RL(v)的子集。reachableBy(v)的每个条目是一对(s,l),这意味着S ⊆ RL(v)。我们将保证每个条目(S,L)满足|L| ≤ |L|/4 + 1。这有三个原因。首先,我们不想存储所有的2 | 1 |组合,因为这会占用大量内存。其次,如果|L|很小,那么|S|很可能很大,因此我们可以标记更多的顶点。第三个原因是,如果|L|很小,那么我们就有更多的机会使用该条目进行修剪,因为只要查询(s,t,L0)满足L ⊆ L0,我们就可以使用它。



5.4 Query algorithm
现在我们解释我们的查询算法(算法5)。我们使用索引NL-Ind和reachableBy来加速回答查询的过程。

当标记的(v)设置为真时,顶点v不再与我们的查询相关,也就是说,要么我们访问了它,要么我们修剪了它。

主要利用了非landmark 的索引,首先对非landmark中进行遍历找到对应结束顶点的landmark,再通过对landmark和该结束顶点是否存在路径来进行确定。


在最后的查询算法中利用reachableBy(v)对已有的一些点进行剪枝,去除这些点,减少我们接下来的不正确查询

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注