《BLINKS: Ranked Keyword Searches on Graphs》——论文笔记

ABSTRACT

目前关键词查询的技术缺陷：poor worst-case performance, not taking full advantage of indexes, and high memory requirements.
本文方法：BLINKS, a bi-level indexing and query processing scheme for top-k keyword search on graphs.
BLINKS遵循的搜索策略保证了性能下限，另外二级目录可帮助进行剪枝和加速查询。二级目录是为了减少目录的大小，首先将目录分块，二级目录只存储块级的信息。

1 Introduction

现在有各种各样的图数据。
树结构或图结构数据上的关键词搜索流行的原因：

1. 对用户友好
2. 很多图结构数据没有schema，很多查询语言不适用

we focus on implementing efficient ranked keyword searches on schemaless node-labeled graphs.

Challenges 利用了树的层级结构应用于XML的方法不再适用。另外缺少schema也排除了一些在编译阶段的优化。之前的工作有以下缺点：

• 现有的许多算法采用启发式的图搜索策略，缺乏性能的保证。
• 现有算法没有充分利用index。他们只用index确定点集中有没有包含关键字，找子结构连接的节点依靠图遍历。但是naive的目录会导致很高的存储需求。

Contributions BLINKS (Bi-Leval INdexing for Keyword Search)

• Better search strategy. 基于cost-balanced expansion——一个新的backward search strategy。增加了参数m（关键词个数）后，效果提升很多。
• Combining indexing with search. 索引预先计算并保存了一些最短路的信息。不仅为backward search提速，还支持forward search。BLINKS是第一个在通用图上广泛使用索引加速关键字搜索的方式。
• Partitioning-based indexing. 保存所有最短路信息的目录太大了，BLINKS把图分为几份，二级目录保存块级信息。可以在空间和搜索效率上得到平衡。

实验证明了BLINKS取得了数量级上的领先，以及BLINKS支持复杂的scoring functions。

The rest of the paper is organized as follows. We formally define the problem and describe our scoring function in Section 2. We review existing graph search strategies and propose the new cost-balanced expansion policy in Section 3. To help illustrate how indexing helps search, we present a conceptually simple (but practically infeasible) single-level index and the associated search algorithm in Section 4. In Sections 5 and 6, we introduce our full bi-level index and search algorithm. We discuss optimizations in Section 7 and present results of experiments in Section 8. Finally, we survey the related work in Section 9 and conclude in Section 10.

2 Problem Definition

Data and Query

Definition 1. Given a query $q=(w_1,...,w_m)$and a directed graph $G$, an answer to q is a pair $<r, (n_1,...,n_m)>$, where $r$ and $n_i$’s are nodes (not necessarily distinct) in $G$ satisfying the following properties:
(Coverage) For every i, node $n_i$ contains keyword $w_i$.
(Connectivity) For every i, there exists a directed path in $G$ from r to $n_i$.

$r$是答案的root，$n_i$’s 是答案的matches。连通性使得答案必须为一个根节点能达到所有关键词的子树。

Top-k Query

Definition 2. Given a query and a scoring function $S$, the (best) score of a node $r$ is the maximum S(T) over all answers $T$ rooted at $r$ (or 0 if there are no such answers). An answer rooted at $r$ with the best score is called a best answer rooted at $r$. A top-k query returns the k nodes in the graph with the highest best scores, and , for each node returned, the best score and a best answer rooted at the node.

上述定义中返回的k个答案root并不同。原因如下

• 避免了某个指向很多带有关键词的子节点的节点作为根的情况。
• 这样会使目录更加有效。（在第七节会讨论）

Scoring Function. 本文主要关注索引和查询处理，因此并不对scoring function进行深入研究。
本文的得分函数同时考虑了图结构和内容，并且包含了数据库和IR社区最先进的测量方法。对于$T=<r,(n_1,...,n_m)>$和查询$(w_1,...,w_m)$得分函数为

$$S(T)=f(\bar S_r (r)+\sum_{i=1}^m \bar S_n(n_i,w_i)+\sum_{i-1}^m \bar S_p (r,n_i))$$
其中 $\bar S_p (r,n_i))$表示从root $r$到match $n_i$的距离。
$f(\cdot)$的输入是三个部分的和，即(1) the answer root. (2) the matches. (3) the paths from the answer root to the matches.
得分函数的两个properties:

• Match-distributive semantics.在S(T)的定义中，matches和paths from the answer root to the matches被累加计算，即每个路径单独的作用于得分函数，即便有公共边。这种计算方式偏向于图2的右侧结果。
• Graph-distance semantics. $\bar S_p(r,n_i)$被定义为从root到matches的最短路径，这样吧关键词搜索问题归约成最短路径问题。

An Assumption for Convenience. 为了表示简单，我们忽略掉root和match对得分的贡献，只考虑path部分，即$\sum^m_{i-1} \bar S_p(r,n_i)$。现在算法归约成找k个节点，其中每个节点都能达到所有的查询关键词，而且到这些关键词的距离还要最小。

3 Towards Optimal Graph Search Strategies

Backward Search 在没有索引提供超过一跳的图连接信息的情况下，我们可以从包含至少一个关键词的节点开始图搜索。这种节点可以被inverted-list index轻松识别。该方法导致了后向搜索算法：

1. 让$E_i$代表能够到达关键词$k_i$的节点。$E_i$——the cluster for k.
2. $E_i$来自$O_i$。$O_i$是直接包含关键词$k_i$的点集。$O_i$——the cluster origin。$O_i$的节点——keyword nodes。、
3. 每一步搜索，我们都根据$E_i$的入边进行扩展。
4. 判断root节点是否找到——对于每个$E_i$要么$x\in E_i$要么x有边连接到$E_i$

第一个后向关键词搜索算法被Bhalotia等人提出，他们主要使用以下两种策略：

• Equi-distance expansion in each cluster: 决定扩展keyword时，访问哪个节点。找距离$O_i$最近的点，为了增加到the cluster origin距离。
• Distance-balanced expansion across clusters: 决定哪个关键词被拓展。为了平衡各个关键词到边界的距离，每次扩展$(u,E_i)$中距离最小的。

下面对上述两个策略进行优化，首先是equi-distance expansion in each cluster策略。

Theorem 1. An optimal backward search algorithm must follow the strategy of equi-distance expansion in each cluster.

但是这个定理对于第二个策略不成立，如图三所示。按照第二个策略，我们会访问所有距离k1小于100的节点，然后再轮到k2。

Bidirectional Search Kacholia等人通过启发式的activation factors确定节点的优先级。虽然在很多情况下有效，但是无法证明其最坏的表现性能，原因在于启发式的activation factors依赖部分已知图。
Our Approach 一个具有好的表现性能的简单搜索策略，主要基于两点：

• we propose a new , cost-balanced strategy for controlling expansion across clusters. 可以保证性能
• 使用目录支持搜索中的前向跳跃。

Cost-balanced expansion across clusters: the cluster $E_i$ to expand next is the cluster with the smallest cardinality. The algorithm attempts to balance the number of accessed nodes (i.e., the search cost ) for expanding each cluster.

Algorithm A: Equi-distance expansion in each cluster + Cost-balanced xpansion across clusters.
Algorithm P: Equi-distance expansion in each cluster + “magically” knows the right amount of expansion for each cluster.

Theorem 2. The number of nodes accessed by A is no more than m times the number of nodes accessed by P, where m is the number of query keywords.

因为大部分查询只包含很少的关键词，所以A的cost通常是最优算法的常数倍。

4 Searching with a Single-Level Index

该方法在小图上适用，完整的BLINKS在5，6节适用于大图。

4.1 A Single-Level Index

Motivation and Index Structure 如果使用equi-distance后向扩展，需要得到一个以距离关键词$k_i$的优先队列。但其规模可能成倍的增长，另外时间复杂度也很高，找到最优先的节点需要$O(\log _n)$的复杂度。
提高在线性能的常用方法是进行离线计算。我们为预先计算了节点到每个关键词（指包含关键词的节点）的距离。这个结果集成为keyword-node lists。每一条有四个field——(dist, node, first, knode)。
另外为了前向搜索，我们为每个点u预先计算了u到每个关键词的距离，即node-keyword map。

但是这样存储的话规模太大，keyword-node lists和node-keyword map都有$N\cdot K$个条目，其中N是节点数，K是关键词的数量。在很多应用中，K和N差不多，因此目录的空间复杂度很高。
Index Construction 目录的建立是对N个节点同时进行Dijkstra算法。时间复杂度是$O(N^2)$
另外单级目录对于只计算root和match的得分函数适用，对于需要计算root到match之间path的得分函数不适用。

4.2 Search Algorithm with Single-Level Index

搜索算法SLINKS，利用单级目录搜索。该算法的得分函数只和root和match相关，与距离无关。

Expanding Backward 用游标对keyword-node list $L_{KN}(w_i)$进行遍历。通过循环的方式，对每个cluster应用cost-balanced expansion。
Expanding Forward 我们使用node-keyword map $M_{NK}$。对于每个node，查找到其他关键词之间的距离。
Stopping 使用阈值$\tau_{prune}$——当前第k个最短距离。但是如果当前游标的距离的和，都要比$\tau_{prune}$大，则程序可以停止（第8行）。
Discussion 与不使用index的工作相比，空间和时间上都有了很大的提升。：

1. 图搜索的状态用游标而不是优先队列。
2. 通过游标比通过优先队列找下个节点快很多。
3. 使用node-keyword map进行前向扩展，能更早地结束算法。

Connection to the Threshold Algorithm TA算法目的在于找到最高分的对象。总分数有m个分数组成，每个属性有一个分数。对每个属性存在一个按分数降序排列的对象列表。TA通过并行访问m个有序列表找到前k个结果。TA在访问对象的数量上是最优的。
通过单机索引，关键字搜索问题可以转化为TA。关键词搜索的equi-distance expansion across keywords 对应着TA中的降序排列，cost-balanced expansion across clusters对应着TA中的并行访问。第3节中，我们证明如果遵循两个规则，则关键字搜索算法最优。

Although we had arrived at this optimality result for general keyword search without assuming indexing, our conclusion coincides with the optimality of the TA algorithm when a single-level index is used.

这里不懂。。。

5 Bi-Level Indexing in BLINKS

因第4节中的目录太大，BLINKS采用分治法创建了二级目录。
Partitioning by Portal Nodes 采用基于点的划分的原因：

• separators的数目比基于边划分要少。因此存储分离器的花费少，在搜索过程中穿过更少的分离器，更加高效。
• 搜索策略认为节点是扩展的最小单元，因此基于点的划分使得应用更加容易。

Definition 3. in a node-based partitioning of a graph, we call the node separators portal nodes (or portals for short). A block consists of all nodes in a partition as well as all portals incident to the partition. For a block, a portal can be either “in-portal” or “out-portal” or both.
In-portal: it has at least one incoming edge from another block and at least one outgoing edge in this block.
Out-portal: it has at least one outgoing edge to another block and at least one incoming edge from this block.

对于块$b_1$，$v_5$是一个out-portal。$v_3$既是in-portal又是out-portal对于块$b_1$和$b_2$来说。

5.1 Intra-Block Index

对于每个块b，IB-index包含下列数据结构：

• Intra-block keyword-node lists: 对于每个关键字$w$，$L_{KN}(b,w)$代表b中能够不离开块b到达w的节点列表，按照距离降序排列。
• Intra-block node-keyword map: 对于$u\in b$，$M_{NK}(b,u,w)$指能够不离开块b从u到w的最短距离。
• Intra-block portal-node lists: 对于b的每个out-portal p，$L_{PN}(b,p)$表示b中能够不离开块b到达p的节点，按照距离降序排列。
• Intra-block node-portal distance map: 对于$u\in b$，$D_{NP}(b,u)$表示从节点u到b中最近的out-portal的最短距离。

Keyword-Node Lists and Node-Keyword Map 和第4节中介绍的基本一致，不过限制范围在一块中。然后利用4.1节中的方法构建单级目录，此时目录的空间复杂度为$O(N_b \cdot K_b)$，假设$K_b=O(N_b)$，则复杂度为$O(N_b^2)$，实际中要远远小于这个值，因为并不是每个节点和关键词都相连。
Portal-Node Lists and Node-Portal Distance Map $L_{PN}$和$L_{KN}$相似。对于一个out-portal node $p\in b$，在$L_{PN}(b,p)$中的每个条目包含(dist, node, first)，dist指最短距离，node指节点，first指最短路径上第一个节点。$L_{PN}$的主要目的在于支持跨快的后向搜寻。因为方向主要是后向，所以没有对于in-portals和nodes的列表。
$D_{NP}$主要在搜索算法的下界节点搜索距离中被使用，对剪枝很有用。
$L_{PN}$通过对块中out-portal应用单源最短路径算法构建。$D_{NP}$可以通过最短路径算法的结果构建。$L_{PN}$的大小为$O(N_b\cdot P_b)$。因为$P_b$通常小于$N_b$，因此这些列表大小远远小于keyword-node lists。$D_{NP}$的大小是$O_(N_b)$

5.2 Block Index

两部分组成：
- Keyword-block lists: 对于每个关键词w，$L_{KB}(w)$表示包含该关键词的块。用作搜索算法在相关块开始后向搜索。
- Portal-block lists: 对于每个portal p, $L_{PB}(p)$表示有p作为out-portal的块的列表。用作搜索算法指导跨块的后向搜索。

Block Index 的构建略去。
空间复杂度：$L_{KB}——O((N/\bar N_b)\bar K_b)$
$L_{PB}——O((N/\bar N_b)\cdot P)$

5.3 Graph Partitioning

本节首先讨论好的划分的guidelines，然后描述两个划分方法。

Theorem 3. Suppose a graph with N nodes is partitioned into B blocks. Let $N_b$ denote the size of block b, and assume that the number of keywords in b is $O(N_b)$. The overall size of the two-level index is $O(\Sigma_bN_b^2+BP)$

虽然划分的表现性能很难衡量，两条指导性规则是通用的：

• 保证portals的数量（P）尽量小。空间上考虑的话，Theorem3中P是空间复杂度的一项。搜索性能上考虑的话，portals越多跨边界的搜索越多。
• 尽量保证块间平衡。根据Theorem3，$\Sigma_bN_b^2$当$N_b$相等时最小。

进一步考虑的话，找到最优的图划分是NP完全的。如果用启发式的规则的话复杂度达到了$O(N^{3.5})$，因此，我们提出两种算法——都先用边划分，然后转化为点划分。

BFS-Based Partitioning 为了得到一个新的块，我们从未分配的节点开始执行BFS，我们把未分配的点放到块中，直到块达到合适的大小。如果达到了BFS的终点，但块大小还是太小，我们从另一个未标注的节点，重复上述工作。最后得到一个基于边的分区。
为了转换成基于点的分区，对于连接块$b_1, b_2$的edge separator $(u_1,u_2)$，把块边界移到$u_1$或$u_2$。有如下规则——choosePortal logic:

• 假设$s_1$ and $s_2$是对应着$u_1$和$u_2$edges separators的数量。
• 选择$s_i+\delta |b_i|$值更大的点作为portal，其中$\delta$是一个可变常量。

choosePortal算法寻求块大小的平衡和最小化portal的数量。如果$s_i$越大，则去除的edge separator越多。完整的算法如算法2所示。

METIS-Based Partitioning 使用基于BFSDE分区方法 缺点在于第一阶段可能产生大量的edge separator。本方法旨在最小化edge separators 的数量。整个处理过程仍如算法2所示，不过第二行使用METIS而不是BFS进行边划分。
实验中，两种方法有各自的优点。

6 Searching with the Bi-Level Index

因为两层目录，不能得到全局的距离信息而带来的挑战：

• 单个游标不足以应对单个关键词的后向扩展。因为多个块可能有共同的关键词。
• 当遇到in-portal时，后向扩展可能会进入多个块。
• 块内的node-keyword maps存储的距离信息并不是全局的最短路径。

Backward Expansion with Queues of Cursors 对每个关键词使用游标队列(a queue $Q_i$ of cursors)。第4行使用keyword-blocklist找到包含$w_i$的所有块。第5行为每个块内的关键词赋予游标。
找到当前块的一个in-portal u时，需要通过portal-block list找到以u为out-portal的块（第12行）。对于每个块b，用一个新的游标对u进行遍历（第13行）。
BLINKS搜索过程中可能多次遇到同样的portal node u，主要有两种情况：

1. u能被包含同样关键词却不在同样块的节点达到。
2. u可以把包含不同关键词的节点达到。

对于第一种情况，由于我们在第一次从u到关键词$w_i$访问的时候，就得到了全局的最短距离。因此我们使用一个bitmap crossed去保存该结果。（第11和14行）。该优化得到的结论如下：

Lemma 1. The number of cursors opened by searchBLINKS for each query keyword is $O(P)$, where P is the number of portals in the partitioning of the data graph.

因此，即便searchBLINKS不能一个关键词一个游标，但现在只需要有$O(|P|)$就可以，也是远远小于不用目录而使用整个搜索边界的优先队列。

Implementing Optimal Backward Search Strategy 第7行的 pickKeyword选择explored node数量最少的keyword。此处应用了cost-balanced expansion strategy。
对于每个关键词，游标每次都移到距离最小的项。这里应用了equi-distance expansion strategy。
Expanding Forward 虽然块内node-keyword maps的距离信息并不是全局的，但是如果该距离小于u到任何out-portal的距离，就可以认为是最短距离了。（第26,27行）
Pruning and Stopping 首先how to lower bound a node’s combined distance to the keywords。对于被访问过但并未确定是答案的u点，我们计算$sumLBDist(u)=\sum_{j=1}^m LBDist_j(u)$作为到各个关键词的距离lower bounds的和。其中$R[u]=<u,dist_1,dist_2,...,dist_m>$，因为并不是每个$dist_i$都已知，但我们让$LBDist_j(u)=max\{d_1,d_2\}$：

• (Bound from search)$d_1=Q_j.top().peekDist(), \ or \ \infty$ if $Q_j$ is empty.
• (Bound from index)$d_2=min\{M_{NK}(b,u,w_j),D_{NP}(b,u)\}$，如果u到$w_i$的最短路径在块内，则是$M_{NK}(b,u,w_j)$，否则至少是$D_{NP}(b,u)$

如果节点的下限都比$\tau_{prune}$要大，则不会是top k的答案，可被剪枝（第28,29行）。
算法停止条件（第16行）：We stop if every unvisited node must have combined distance greater than τprune (same condition as in searchSLINKS), and every visited non-answer node can be pruned.

7 Optimizations and Other Issues

Evaluating Pruning and Stopping Conditions 函数sumLBDist(u)的计算量很大，因为$Q_j.top().peekDist()$的quantity在搜索中会经常变化。我们在计算量和剪枝&停止的有效性之间做了平衡。只有在访问到u点时，才计算sumLBDist(u)。我们还保留了一个优先队列，去追踪在所有的备选答案中最小的下界。

Batch Expansion 游标间频繁切换数据以及代码的局部可达性很差限制了性能。因此我们允许一个游标内一些节点被扩展，放宽了equi-distance expansion strategy。

Recovering Answer Trees 算法中返回的只有根节点，实际中往往需要知道结果树。keyword-node lists & node-keyword maps的knode字段可以帮助顺利找到答案。

Handling the Full Scoring Function 对于得分函数来说，我们只关注了path部分，root和match部分可以忽略。因为加上root 和match部分的得分剪枝和停止部分的工作也是正确的。因为得分非负。

Effect of Ranking Semantics
如果得分函数是一个黑盒函数，则没有办法进行预计算和存储而优化。
- Distinct-root semantics. 要求每个节点至多一个答案。我们可以为每个节点预先计算一些信息并存储。
- Match-distributive semantics.如果没有该semantic，则边的权重不管引出了多少边，只计算一次，那么和group Steiner tree problem问题相同。有了该语义我们可以支持多关键字查询，每个关键字和节点互相独立。
- Graph-distance semantics. 因为该semantic，我们可以把一条root-to-match的路径分为多段，并为每段独立地进行预计算和存储。利用该semantic，我们可以使用二级目录将图划分为几块。跨块的距离信息可以被来自不同块的路径组装在一起。如果没有该semantic，我们需要预先计算所有的root-to-match paths。

8 Experimental Results

本文算法：BLINKS.
对比算法：the Bidirectional search algorithm.

8.1 DBLP dataset

Graph Generation 首先从DBLP XML数据（http://dblp.uni-trier.de/xml/）产生node-labeled directed graph。原始的XML数据是一个树，每个paper都是其子树。我们加了两种边：
- 通过引用将论文连接在一起。
- 不同论文的相同作者共享一个节点。
另外，我们还
- 去掉了关键词搜索中每个paper中不感兴趣的元素，如url，ee等。
- 去掉了没有引用其他论文或没被其他论文引用的论文。

Search Performance


图7展示了Bidirectional算法和BLINKS算法的四种配置（$|b|=1000,300$），每一条都表示两个值，找到任一答案和找到前十个答案的时间。为了避免时间太长，我们在90秒后强制返回结果。
查询时间的影响因素：

• 关键词的数量。决定初始的边界。
• 查询时边界扩展的大小。查询时，优先队列的大小可能急速增长。因此$Q_6$的Bidirect算法比$Q_1-Q_5$时间都长。
• 何时能停止搜索。这依赖剪枝的有效性。

虽然查询空间由很多因素决定，但是关键词越多，查询空间一般越大。虽然基于BFS的一般优于基于METIS的，但也不总是这样。块的大小也和性能没有必然联系。
Index Performance

块越大则条目越多，建立索引的时间越长——图a和图c的前四条。
基于BFS的方法的特殊是因为数据集包含a very flat and broad tree以及一些连接的边，因此BFS的方法很容易得到flat and broad 的块，而且块内的路径比较短。块内索引的建立主要是在块内的路径游走，因此c图中可以看到，基于BFS的时间也很少。

8.2 IMDB Dataset

Graph Generation 使用了IMDB数据(http://www.imdb.com)。图包含68K nodes，248K edges， and 38K distinct keywords。
Search Performance

图9展示了平均的应答时间。这里基于BFS的不如基于METIS。另外块越大，性能越好。
Index Performance

因为IMDB图相对较小，所以图划分很快，但图索引建立很慢，因为图的结构比较复杂。
Comparing Figures 8 and 10, we note that the graph topology plays an important role on BLINKS: BFS works fine on simpler graphs, but experiences difficulty on highly-connected graphs.

9 Related Work

最相关的工作——BANKS在第3节有讨论。
[10,5,14,20,22]解决XML上的关键词搜索，虽然相似但其问题更加简单。他们只关注树结构，有着很多优化的机会。另外连接信息也容易被编码。
[1,3,17,16,23]关注关系数据库上的关键词搜索。数据库可以被视为labeled graph，其中tuple被认为是节点，用外键连接。但是这样的图有着固定的架构，因为schema限制了节点的连接。

图上的关键词搜索同时考虑了节点标签和图结构，有很多的策略去对答案排序。不同策略关注不同方面。

• 关注搜索的有效性，即排序函数是否满足用户需求。[16,2,13,23]使用了IR-style answer-tree ranking strategies。和本文不同，他们并不考虑搜索的效率，在IR-style的排序中，边权重往往依赖排序使得难以建立索引
• 提高搜索效率。一些如BANKS的系统提出方法降低搜索空间。一些方法将答案的得分定义为边权重之和，将问题转化为group Steiner tree，成为了一个NP-hard问题，很难精确找到top k个答案。[21]表示在数据复杂度不高的情况下，使用该得分定义可以用多项式进行枚举。[6]提出基于动态规划的方法，旨在查询中关键词较少的情况。BLINKS提出另一种评分机制，避免问题归约为group Steiner tree问题，还通过目录和剪枝降低复杂性。

在距离可以被图划分索引到这个意义上，我们的portal概念和[12]中的hub nodes类似。Hub nodes为了计算任意两点距离而设计。有一张全局的hub index保存了hub node之间的最短距离。BLINKS中我们并不预先计算这些全局信息，只是通过portal导航找到最佳答案。

10 Conclusion

本文关注图数据上的关键词搜索。问题如下

• 难以直接对通用的，schemaless的图建立索引，目前的方法很依赖运行时的图遍历。
• 缺乏关于图结构的信息使得搜索中的剪枝十分低效。

为解决以上问题，我们提出了一个新的得分函数，使得问题适合索引，提出了两层目录并用块大小来控制目录的复杂度。We also propose the cost-balanced expansion policy for backward search, which provides good theoretical guarantees on search cost. Our search algorithm implements this policy efficiently with the bi-level index, and further integrates forward expansion and more effective pruning.

Future work主要有两方面：

• 图更新，索引也需要更新。BLINKS本地化存储，更新应该更容易。
• 动态的选择改变图划分和编排目录的方式。

1

1