计算机领域有丰富的数据存储格式，然而对于许多数据格式，需要一定的专业知识才能查找指定内容的相关信息. 不过人们发现，往往能通过对数据元素与关系的表达，使一种数据格式转化为图数据. 因此，可以设计一种通用的方法，方便普通用户在复杂数据上查询信息，这种方法便是关键字检索. 在图上关键字检索问题中，每个节点都拥有若干字符串作为信息，称为节点的标签，另外有若干字符串作为问题的输入，称为关键字. 查询标签带有关键字信息的相关节点的问题称为关键字检索问题. 根据结果形式的不同，图上关键字检索问题可以分为2类：基于树的查询语义与基于图的查询语义. 斯坦纳树（Steiner tree）是树查询语义的一种常见形式^[1]，是原图上包含所有指定关键字的最小子树. 而r-团（r-clique）则是图查询语义的一种形式^[2]，是原图上包含所有关键字且所有点对的距离均不超过r的点集. 图上关键字的Steiner tree与r-cliques检索问题都已经被证明是NP-难问题，这意味提出解决这些问题的高性能算法是一种挑战. 而在大数据时代中，人们须处理的数据规模正日益增长，如何在这样的背景下高效地解决关键字检索问题，是一个研究热点.

现有研究致力于从不同的角度出发解决图上关键字检索问题. BANKS算法^[3]提出一个将关系型数据转化为图数据进行关键字查询的系统，通过减少搜索空间的方式提高计算效率. BLINKS算法^[4]引入一种评分机制，提出更加高效的索引与剪枝技术. r-cliques ^[2]基于分治的思想，提出一个多项式时间复杂度的近似算法. 这些现有研究都是在中央处理器（central processing unit，CPU）上展开的，受限于CPU的架构，在大规模图数据上进行关键字检索的表现不甚理想. 而图形处理器（graphics processing unit，GPU）由于其架构的特殊性可以快速进行大量简单的并行计算. 而且近几年来，GPU计算也被应用到诸多图问题的研究中，其中就包括了图计算库Gunrock^[5]. 以经典排名算法PageRank^[6]为例，其在Tesla T4上的速度可以达到CPU架构上的13倍，而在2080Ti上更是达到了25倍. 因此，本研究利用GPU计算来提高图上关键字检索问题的算法效率.

基于Steiner tree查询语义，提出关键字检索问题，利用传统多源最短路径算法设计基本算法BaseCPU，并进一步扩展到GPU上提出算法BaseGPU，使算法性能得到提升；分析基本算法，结合基本算法的缺陷，基于索引技术和单源最短路径的松弛更新思想，提出优化算法AdvGPU；对上述算法进行扩展，提出GPU上的r-cliques分支定界算法；结合在真实数据集上开展的大量实验证明优化算法的优越性.

定义1　属性图. 给定图 $G(V,\;E)$表示节点带有标签的属性图. $V$表示节点的集合， $E$表示带权边的集合，设 $n = |V|$， $m = |E|$.

定义2　内容节点. 对节点 $v$，定义 ${{{\rm{{{Label}}}}} _v}$表示 $v$的标签集. 当关键字 $w \in {{{\rm{Label}}} _v}$时，称 $v$为 $w$的内容节点. 对关键字集 $Q$，若存在 $w \in Q$，且 $v$为 $w$的内容节点，则称 $v$为 $Q$的内容节点.

定义3　答案树. 给定属性图 $G$与关键字集 $Q$，定义有根树 $T(V,\;E,\;r)$表示 $G$上关于 $Q$的答案树. $V$、 $E$、 $r$表示点集、边集与根， $\forall w \in Q$，在 $T$上都存在节点为 $w$的内容节点. 称与关键字一一对应的内容节点为 $T$的关键节点，组成的序列表示为序列 ${{{K}}_T}$.

定义4　节点分数. 给定属性图 $G$与关键字集 $Q$， $G$上关于 $Q$的答案树 $T$的分数 $ {{{\rm{Score}}} _T} $为根到各关键节点的距离之和，节点 $v$的答案树 ${T_v}$为所有根为 $v$的答案树中分数最小者，且该树的分数即为 $v$的分数 $ {{{\rm{Score}}} _v} $.

以图1为例，设关键字集 $Q = \{ {\rm{b}},{\rm{c}}\} $，如图1(b)所示的树就是 ${v_2}$关于 $Q$的一棵分数为 $9$的答案树. 而答案树 $T(\{ {v_2},{v_4},{v_5}\} ,\{ {v_2} \to {v_4},{v_4} \to {v_5}\} ,r = 2)$的分数为 $2$，是所有以 ${v_2}$为根的答案树中分数最小的，因此 $ {{{\rm{Score}}} _{{v_2}}} = 2 $.

问题定义如下：给定一个有向属性图 $G(V,E)$和一个关键字集， $\forall v \in V$，求解 $v$关于 $Q$的分数 ${{{\rm{Score}}} _v}$，以及其答案树各关键节点组成的序列 ${{K}}_{T_v}$.

在图1(a)上对关键字集Q={b, c}求解的结果如表1所示.

设节点 $u$到节点 $v$的距离为 ${d_{(u,v)}}$，关键字w的所有内容节点组成的集合为C_w，给出一个定理.

定理1　任取图 $G$上一个节点 $u$， $\forall w \in Q$， ${v_w}$为w的一个内容节点，满足d（u，v_w）=min{d（u，v）| $\forall $v∈C_w}，则 ${T_u}$以全体 ${v_w}$为关键节点，且 ${{{\rm{Score}}} _u} = $ $ \displaystyle \sum\nolimits_{w \in Q} {{d_{(u,{v_w})}}} $.

证明　假设有关键字 $w' \in Q$，答案树 $T{' _u}$以全体 ${v_w}$（ $w \ne w' $）以及某一节点 $v' $（ $v' \ne {v_{w' }}$）为关键节点，则 ${{{\rm{Score}}} _{T{' _u}}} = \displaystyle \sum\nolimits_{w \in Q(w \ne w' )} {{d_{(u,{v_w})}} + {d_{(u,v' )}}} $，由于 ${v_{w' }}$为距离 $u$最近的内容节点， ${d_{(u,{v_{w' }})}} < {d_{(u,v' )}}$，有 ${{{\rm{Score}}} _u} < $ $ {{{\rm{Score}}} _{T{' _u}}}$，得证.

基于定理1，可以得知求解节点答案树时每个关键字对关键节点的选取是独立的，即 $\forall w,w' \in Q,w \ne w' $， ${v_w}$的选取不影响 ${v_{w' }}$对答案树分数的贡献. 因此，本问题求节点分数的过程就可以转化为求节点到各关键字所有内容节点距离的过程. 根据以上推论，对本问题提出一个基本思路. 先使用Floyd-Warshell算法^[7]在图上求出所有点对之间的距离，存储在距离矩阵 ${\boldsymbol{D}}$中. 之后对每个节点 $u$分别枚举所有关键字，并计算 $u$到各关键字内容节点最小距离之和作为 $u$的分数，且取这些最近的内容节点作为 $u$答案树的关键节点. 该过程的伪代码如下.

算法1 　Base CPU

输入：属性图 $G(V,E)$, 关键字集 $Q$;

输出：各节点分数 ${{{\rm{Score}}} _v}$, 关键节点序列 ${{{K}}_{T_v}}$.

1. ${\boldsymbol{A}} \leftarrow $adjacency matrix of $G(V,E)$

2. ${\boldsymbol{D}} \leftarrow {\boldsymbol{A}}$

3. for $k \leftarrow 1$ to $n$ do

4. for $i \leftarrow 1$ to $n$ do

5. for $j \leftarrow 1$ to $n$ do

6. ${D_{i,j}} = \min\;\; ({D_{i,j}},{D_{i,k}} + {D_{k,j}})$

7. for $u \in V$ do

8. for $w \in Q$ do

9. $v \leftarrow v \in {C_w}$, ${D_{u,v}}$ is minimal

10. ${{{\rm{Score}}} _u} \leftarrow {{{\rm{Score}}} _u} + {D_{u,v}}$

11. ${{\boldsymbol{K}}_{{T_u}}}[w] \leftarrow v$

以图1为例，根据该图的邻接矩阵，求出距离矩阵 ${\boldsymbol{D}}$：

(1) $ {\boldsymbol{D}} = \left[ {\begin{array}{*{20}{c}} 0&3&2&4&5 \\ \infty &0&5&1&2 \\ \infty &2&0&3&3 \\ \infty &5&{10}&0&1 \\ \infty &4&9&5&0 \end{array}} \right] . $

接下来，以 ${v_2}$为例枚举所有节点求答案树.对于关键字b，包含它的节点有 ${v_2}$、 ${v_4}$、 ${v_5}$， ${v_2}$到它们的距离分别为0、5、1，显然它到自身的距离是最小的，因此选择 ${v_2}$自身作为关键字b的关键节点；对于关键字c，包含它的节点为 ${v_3}$和 ${v_5}$， ${v_2}$到它们的距离为5和2，因此选择距离更小的 ${v_5}$作为关键字c的关键节点. 由此可得， ${v_2}$的分数 ${{{\rm{Score}}} _{{v_2}}} = {D_{2,2}} + $ $ {D_{2,5}} = 2$，关键字b、c的关键节点为2、5.

定理2 　算法1的时间复杂度为 $O({n^2}(n + |Q|))$，空间复杂度为 $O({n^2})$.

证明　算法1先使用Floyd-Warshell算法计算距离矩阵，时间复杂度为 $O({n^3})$，然后对各节点求答案树，这个过程对所有节点到所有关键字的内容节点进行枚举，时间复杂度为 $O({n^2}|Q|)$，因此算法1的时间复杂度为 $O({n^2} (n + |Q|))$. 算法1使用规模为 $n \times n$的矩阵与规模为 $n$的向量存储数据，空间复杂度为 $O({n^2})$.

由算法1的时间复杂度可知，该算法的性能瓶颈主要来源于时间复杂度为 $O({n^3})$的计算距离矩阵部分. 因此将Floyd-Warshell算法替换为其GPU版本^[8]，即可使本过程移植到GPU上. 替换后过程的伪代码如下：

算法2 　BaseGPU

输入：属性图 $G(V,E)$, 关键字集 $Q$;

输出：各节点分数 ${{{\rm{Score}}} _v}$, 关键节点序列 ${{\boldsymbol{K}}_{{T_v}}}$.

1. ${\boldsymbol{A}} \leftarrow $adjacency matrix of $G(V,E)$

2. ${\boldsymbol{D}} \leftarrow {\boldsymbol{A}}$

3. for $k \leftarrow 1$ to $n$ do

4. for each $i,j \in [1,\;n]$ in parallel do

5. ${D_{i,j}} = \min \;\;({D_{i,j}},{D_{i,k}} + {D_{k,j}})$

6. for $u \in V$ do

7. for $w \in Q$ do

8. $v \leftarrow v \in {C_w}$, ${D_{u,v}}$ is minimal

9. ${{{\rm{Score}}} _u} \leftarrow {{{\rm{Score}}} _u} + {D_{u,v}}$

10. ${{\boldsymbol{K}}_{{T_u}}}[w] \leftarrow v$

并行化可以使距离矩阵的求解效率显著增加. 但由于只有内容节点的距离值会在求解答案树时被使用，该过程实际上存在着大量的冗余计算. 因此，即使使用GPU进行加速，该过程仍然有着较大缺陷，无法良好地应用到实际生产中，须进一步改进.

针对上述问题，对解决本问题的算法进行重新设计，使其相较于基本过程在时间效率和空间占用方面均有明显优化，且对GPU并行架构具有更强的适应性.

基本过程存在着大量对非内容节点进行判断和反复调用点对距离的操作，导致它的时间效率较低. 因此，基于索引技术，建立2个存储点与关键字信息的矩阵. 当算法需要一个节点与一个关键字之间的信息时，只须在 $O(1)$时间内对这2个矩阵进行查询即可获取. 首先对于 $u$到 $w$内容节点的距离给出一个定理：

定理3　设图 $G$上关于关键字 $w$的内容节点集为 $C$，假设在 $G$上增加一个节点 $v' $， $\forall v \in C$，有一条长度为 $0$的边 $v \to v' $，则对图 $G$上任意节点 $v$，有 ${\min _{u \in C}}\;{d_{(u,v)}} = {d_{(u,v' )}}$.

证明　设 ${v_0}$为该最短路径上与终点 $v' $相邻的点，由于 $v' $只包含以内容节点为起点的入边，有 ${v_0} \in C$，又因为 $\forall v \in C$， $v \to v' $的边长为 $0$，从 $u$经过任意内容节点 $v$到 $v' $的距离就等于 $u$到 $v$的距离. 根据定义， $u$经过 ${v_0}$到 $v' $是 $u$到 $v' $的最短路径，有 $u$到 ${v_0}$是 $u$到所有内容节点距离最近的，得证.

结合定理3，基于Bellman-Ford算法^[9-10]的松弛思想，对 $G$进行反向搜索建立索引结构，其包含点-关键字内容节点矩阵 ${{\boldsymbol{C_{\rm{VK}}}}}$与点-关键字距离矩阵 ${{\boldsymbol{D}}_{\rm{VK}}}$，分别用于存储节点v_w（v_w∈C_w，且d(v, v_w)=min {d(v, v')| $\forall $v'∈C_w})及距离值d(v, v_w). 对于一个关键字 $w$，将 $w$所有内容节点的距离值均初始化为 $0$，然后在GPU上以每个节点为一个线程并行对 $G$的边反向进行松弛更新，直到所有节点距离值都不再改变，最后将各节点到 $w$最短路径的终点和长度更新到 ${{\boldsymbol{D}}_{{\rm{VK}}}}$与 ${{\boldsymbol{C}}_{{\rm{VK}}}}$中，就完成了矩阵中关于 $w$信息的建立.

定理4　在图 $G$上，设对于关键字 $w$，至少与 $w$的一个内容节点连通的节点集为 ${C_w}$，即 $\forall v \in {{{C}}_w}$， ${{{{\boldsymbol{D}}}}_{{\rm{VK}}}}(v,w) \ne \infty$，则对于 $Q$， $G$所有拥有答案树的节点集 $A = \bigcap\nolimits_{w \in Q} {{{{C}}_w}}$.

根据树的定义，根节点到树上其他节点是连通的，因此定理4的正确性是显然的. 因此可以在求信息矩阵时对各节点到关键字的连通情况进行统计，通过这一点快速判断节点是否属于节点集 $A$，使答案树的计算只在有效的节点上进行，以减少无效的计算量.

答案树的求解过程在GPU上以每个节点为一个线程并行进行，利用3.1节中建立的信息矩阵加速节点到关键字距离信息的获取. 根据定理1，节点 $v$答案树的关键节点即为各关键字的内容节点，其中关键字w的内容节点v_w满足d(v，v_w)=min {d(v, v')| $\forall $v'∈C_w}，即 ${{{\rm{Score}}} _v} = \displaystyle \sum\limits_{w \in Q} {{{{D}}_{{{\rm{VK}}} }}(v,w)} $，且关键字 $w$对应的关键节点即为 ${{{C}}_{{\rm{VK}}}}(v,w)$. 由此即可得到待求解的结果.

算法3 　AdvGPU

输入. 属性图 $G(V,E)$, 关键字集 $Q$;

输出. 各节点分数 ${{{\rm{Score}}} _v}$, 关键节点组成的序列 ${{{K}}_{{T_v}}}$.

1. for each $w \in Q$ do

2. $\;\; U \leftarrow {C_w}$

3. $\forall v \in {C_w}$, ${{{\rm{dis}}} _v} = 0$, ${{{\rm{ctv}}} _v} = v$

4. ${{\bf{dis}}}' = {{\bf{dis}}}$, ${{\bf{ctv}}}' = {{\bf{ctv}}}$

5. while $U \ne \varnothing$ do

6. for each $u \in V$ in parallel do

7. for each neighbour $v$ of $u$ do

9. if ${{\rm{dis}}} {' _u} < {{{\rm{dis}}} _v} + {{{\rm{length}}} _{u \to v}}$ then

10. $ {{\rm{dis}}} {' _u} \leftarrow {{{\rm{dis}}} _v} + {{{\rm{length}}} _{u \to v}} $

11. ${{\rm{ctv}}} {' _u} \leftarrow {{\rm{ctv}}} {' _v}$

12. $U \leftarrow \varnothing$

13. for each $v \in V$ in parallel do

14. if ${{\rm{dis}}} {' _u} < {{{\rm{dis}}} _u}$ then

15. ${{{\rm{dis}}} _u} \leftarrow {{\rm{dis}}} {' _u}$, ${{{\rm{ctv}}} _u} \leftarrow {{\rm{ctv}}} {' _u}$

16. insert $u$ into $U$

17. ${{\bf{dis}}} = {{\bf{dis}}}' $, ${{\bf{ctv}}} = {{\bf{ctv}}}' $

18. column of $w$ in ${{\boldsymbol{D}}_{{{\rm{VK}}} }} \leftarrow {{\bf{dis}}}^{\text{T}}$

19. column of $w$ in ${{\boldsymbol{C}}_{{{\rm{VK}}} }} \leftarrow {{\bf{ct}}}{{{\bf{v}}}^{\text{T}}}$

20. for each $v \in \bigcap\nolimits_{w \in Q} {{C_w}} $ in parallel do

21. ${{{\rm{Score}}} _v} \leftarrow \displaystyle \sum\nolimits_{w \in Q} {{{\boldsymbol{D}}_{{\rm{VK}}}}(v,w)}$

22. ${{\boldsymbol{K}}_{{T_v}}} \leftarrow ({{\boldsymbol{C}}_{{\rm{VK}}}}{(v,w)_{w \in Q}})$

以图1为例，对算法过程进行举例说明. 仅以关键字b的第1轮松弛更新为例建立信息矩阵. b的内容节点有 ${v_2}$、 ${v_4}$、 ${v_5}$ 3个，因此开始时 ${{\bf{dis}}} = $ $ [\infty ,0,\infty ,0,0]$， ${{\bf{ctv}}} = [{v_0},{v_2},{v_0},{v_4},{v_5}]$. 建立临时副本 $ {{\bf{dis}}}' $与 ${{\bf{ctv}}}' $，首先进行一轮松弛操作，对于 ${v_1}$， ${v_2}$为它的邻接节点且邻边长为 $3$，此时 $ {{\rm{dis}}} {' _1} = \infty $， ${{{\rm{dis}}} _2} + $ $ 3 = 3$， ${{\rm{dis}}} {' _1} > {{{\rm{dis}}} _2} + 3$，因此 ${{\rm{dis}}} {' _1}$、 ${{\rm{ctv}}} {' _1}$变为 $3$与 ${v_2}$，其他节点同理. 结束时 ${{\bf{dis}}}' = [3,\;0,\;2,\;0,\;0]$， ${{\bf{ctv}}}' = [{v_2},\;{v_2},\; $ $ {v_2},\;{v_4},\;{v_5}]$，再将 ${{\bf{dis}}}' $、 ${{\bf{ctv}}}' $的值更新给 ${{\bf{dis}}}$与 ${{\bf{ctv}}}$. 本轮中 ${v_1}$与 ${v_3}$被更新了，因此还须继续下一轮操作. 最终，图1关于关键字集 $Q = \{ b,c\} $建立的信息矩阵如下：

(2) $ {{\boldsymbol{D}}_{{\rm{VK}}}} = {\left[ {\begin{array}{*{20}{c}} 3&0&2&0&0 \\ 2&2&0&1&0 \end{array}} \right]^{\text{T}}} . $

(3) $ {{\boldsymbol{C}}_{{\rm{VK}}}} = {\left[ {\begin{array}{*{20}{c}} {{v_2}}&{{v_2}}&{{v_2}}&{{v_4}}&{{v_5}} \\ {{v_3}}&{{v_5}}&{{v_3}}&{{v_5}}&{{v_5}} \end{array}} \right]^{\text{T}}} . $

根据信息矩阵（式(2)、(3)）， ${{\boldsymbol{D}}_{{\rm{VK}}}}$各行的累加结果 $5$、 $2$、 $2$、 $1$、 $0$为各节点的分数， ${{\boldsymbol{C}}_{{\rm{VK}}}}$各行 $({v_2},{v_3})$、 $({v_2},{v_5})$、 $({v_2},{v_3})$、 $({v_4},{v_5})$、 $({v_5},{v_5})$为各节点答案树的关键节点序列，如此即可得到待求的结果.

定理5　算法3的空间复杂度为 $O(n|Q|)$.

证明　算法3使用规模为 $n {\text{|}}Q|$的矩阵与规模为 $n$的向量存储数据，空间复杂度为 $O(n |Q|)$.

得益于将同一关键字的所有内容节点看成一个整体、以这个整体作为起点在图上进行反向搜索的思路，本算法显著减少了冗余的计算量. 另外，本算法中信息矩阵在空间占用方面也有着显著的优化. 除此之外，在每次调用核函数时以每个节点为一个线程，本算法共使用GPU的 $n$个线程加强了算法对GPU硬件的利用率. 综上所述，本算法在更大规模的输入图上仍有较佳的求解能力.

树查询语义是比较常见的关键字检索问题模型，而这种模型对查询结果结构的稠密性不敏感，在特定的应用场景下效果不佳，因此一些对结果图稠密性进行约束的图查询语义模型也被提出.

$r$-cliques关键字检索问题是基于图查询语义的关键字问题. 一个 $r$-clique是图上的一个点集，其中节点的标签覆盖给定的关键字集，且任意一对点对距离不超过 $r$. 问题定义如下：给定一个无向属性图 $G$、一个关键字集 $Q$以及一个整数 $r$，求解 $G$上关于 $Q$所有的 $r$-clique. 如图2所示，图2(b)中标出了图2(a)上关于关键字集{a, c, d}、 $r = 2$的一个 $r$-clique.

$r$-cliques问题是一个NP-难问题，这一点在文献[2]中已有证明，且文献[2]给出了在CPU上求解 $r$-cliques问题的分支定界算法，枚举各关键字内容节点的所有组合进行搜索与剪枝. 该算法的最坏情况的时间复杂度为 $O(|Q{|^2} |C|_{{{\rm{MAX}}} }^{|Q| + 1})$. （ $|C{|_{{\rm{MAX}}}}$为所有关键字中的最大内容节点数），是一个非多项式时间复杂度的过程. 文献[2]在介绍该算法时，定义了一个集合 ${{\rm{rList}}} $，用于表示候选的 $r$-clique点集. 而在GPU存储集合结构较为困难，因此本研究针对 ${{\rm{rList}}} $的表示方法进行修改，提出一个GPU上求解该问题的思路，以提高它在更大规模图数据上的计算效率.

定理6　在 $r$-cliques问题的求解过程中，对于一个关键字，其内容节点的枚举以及一个内容节点对 ${{\rm{rList}}} $中每个节点集的可行性判断是互不影响的.

根据定理6，可以将该算法移植到GPU上并行执行. 算法对图上所有关键字按顺序进行枚举操作，对于一个关键字，以每个内容节点对当前 ${{\bf{rList}}} $中每个节点集的判断为一个线程在GPU上并行执行. 为了简化集合在GPU中的使用，本研究改变了 ${{\bf{rList}}} $与其临时副本 ${{\bf{rList}}} '$的存储方式：设当前求解第 $i$个关键字，由于 ${{\bf{rList}}} $中的每个节点集在每一次求解后都会新增一个节点， ${{\bf{rList}}} '$中每个节点集的大小一定为 $i$. 此外，在最坏情况下， ${{\bf{rList}}} '$是对 ${{\bf{rList}}} $中的每个节点集都追加图上的每个节点生成的，即 $|{{\bf{rList}}} '| = |{{\bf{rList}}} | n$. 因此，只须将 $ {{\bf{rList}}} ' $设置为规模为 ${n^i} i$的矩阵，即可用数组来模拟这2个集合. 该算法的伪代码如下.

算法4 　rGPU

输入：属性图 $G(V,E)$, 关键字集 $Q$, 整数 $r$;

输出：所有的 $r$-clique.

1. ${{\bf{rList}}} \leftarrow (\varnothing)$

2. for each $i \in [1,\;|Q|]$, $w \leftarrow {Q_i}$ do

3. ${{\bf{rList}}}{\boldsymbol{'}} \leftarrow $matrix of ${n^i} \times i$

4. $l = 0$

5. ${C_w} \leftarrow $set of content vertices of $w$

6. for each $u \in {C_w}$, $R \in $columns of ${{\bf{rList}}}$

in parallel do

7. if $\forall v \in {\boldsymbol{R}}$, ${d_{(u,v)}} \leqslant r$ then

8. $l = l + 1$

9. push u to the end of R

10. $l$-th column of $ {{\bf{rList}}}{\boldsymbol{'}} \leftarrow $ ${\boldsymbol{R}} + u$

11. ${{\bf{rList}}} \leftarrow {{\bf{rList}}}{\boldsymbol{'}}$

12. return ${{\bf{rList}}}$

选择5组节点规模、关键字类型、稠密度与形状均不相同的真实数据集进行实验.

实现了BaseC、BaseG、AdvG 3种方法，分别对应本研究中的算法BaseCPU、BaseGPU与AdvGPU. 将程序的运行时间约束为1 h，用符号“INF”表示无法在约束时间内完成计算的方法.

使用5个真实数据集进行实验，如表2所示为它们的统计数据. 数据集D₁取自电影推荐系统MovieLens 100K数据集（ https://grouplens.org/datasets/movielens/100k/），取电影、流派、用户、性别、职业作为节点生成该数据集的属性图. D₂取自基于位置的社交网络数据NYC Restaurant Rich Dataset^[11-12]，取场地、用户作为节点，根据登记和评价事件制定边关系. D₃取自计算机领域的文献索引服务DBLP^[13]，取文献、作者、杂志、年份作为节点. D₄取自电影资料库IMDb（ https://www.imdb.com/interfaces/），取电影、导演、剧作、主演、流派、年份作为节点. D₅取自大型合作知识库Freebase的一个归档Freebase Easy^[14]，取实体作为节点，根据事实连接边. 在每个数据集上查询100个规模为1、2、3的关键字集，所有关键字集将各关键字在数据集上按词频从大到小组合选取，并人工排除在原数据集上明显不具备意义的关键字组合.

操作系统：Linux 64位，CPU：i7-9700，内存：16 G，显卡：2080Ti，硬盘：Seagate ST2000DM005，编程环境：Rust 1.15.0 with rustacuda

算法性能通过3种算法在各数据集上的计算时间表现，每个算法对每个数据集仅生成一次矩阵，同数据集的查询均在同一个矩阵上进行.

如图3(a)所示为各算法在各数据集上生成矩阵（距离矩阵或信息矩阵）的时间t_g. 其中BaseG在这个过程中花费的时间大约仅为BaseC的1/100，说明GPU并行优化对算法的加速有着较明显的帮助. 而AdvG又比BaseG在时间上进一步降低，且随着数据规模扩大，两者花费的时间差距逐渐变大. 在较大规模数据上，BaseC与BaseG已经超出了规定的时间限制，而AdvG仍有较好的性能表现，说明AdvG更能适应对大图数据的处理. 另外，虽然D₄的点边规模均大于D₃，但D₄图数据中常见独立的连通块，而D₃图的整体连通性更高，因此在D₄上算法反而更容易达到松弛更新的结束条件. 同时，D₄查询的关键字重复率也高于D₃，因此AdvG在D₄上生成矩阵与查询答案的时间均更少. 这也证明了图的连通性与查询关键字的重复率会对AdvG算法的实际计算时间造成影响.

如图3(b)~(d)分别为各算法在各数据集上查询100个不同关键字集答案的平均、最小与最大时间 ${\bar {t}_{\rm{q}}}$、 $ t_{\rm{q}}^{\rm{min}} $、 $t_{\rm{q}}^{\rm{max}} $. BaseC与BaseG查询答案的部分是相同的，因此运行时间几乎相等. 而基于索引技术优化的AdvG则在这一过程上有着较大的性能优势，且随着数据规模增长差距明显扩大. 即使在较大规模数据上，AdvG对于单次查询仍能在较短的时间内得到结果，拥有较高的效率. 以上证明了AdvG是一个在大图数据上具有实用价值的关键字检索算法.

使用AdvG在数据集D₃上查询2020年发表在杂志VLDB J.上标题中包含keyword一词的文献，即查询关键字集{VLDB J., 2020, keyword}，目的是验证AdvG的查询结果具备查询相关内容的意义. 如图4所示为计算结果中分数最小的2棵答案树，它们的根节点均为一篇标题包含keyword一词的文献，且均连接杂志VLDB J.的节点与年份2020的节点. 经验证，2个根节点所表示的文献均是符合查询条件的文献，说明AdvG能够查询到与关键字相关性较高的结果，因此认为AdvG是具备关键字检索意义的.

通过对数据集D₃的图数据进行不同百分比规模的截取，展示AdvG对于相同的关键字集在图规模逐渐上升时性能表现的变化，如图5、6所示. 图中，n、m分别为节点、边数量规模. 由图5可以看出，当节点规模增长时，AdvG生成矩阵与查询答案的时间按照近似相等的比例增长. 由图6可以看出，当边规模等差增长时，AdvG生成矩阵的时间也近似等差增长，而查询答案的时间则近似以二次函数逐渐趋近于100%规模时的时间. 因此可以认为，当查询的关键字集不变时，AdvG生成矩阵与查询答案时间随节点规模与边规模的增长趋势总体是平缓的. 这意味着AdvG时间开销的增长趋势不会随图规模的增加而有明显提升，使得其在规模较大的图上仍然能够在较能接受的时间内得到结果，具有实际的大图上的应用价值.

关键字检索问题是研究如何方便普通用户查询数据信息的问题，Aggarwal等^[15]将关键字检索的数据形式分为3类. 1) 可扩展标记语言（extensible markup language，XML）数据：一种使用XML标签层级表示关系的数据形式，是一种树状的结构. 2) 关系型数据库：一种包含数据条目和选择、投影、连接等关系模型的数据形式. 3) 图数据：一种使用节点表示数据、用边表示关系的数据形式.

当前图上关键字检索的研究主要集中在结果形式、评分机制、领域延伸等方向. 关系型数据库上关键字检索的研究可以追溯到DBXplorer系统^[16]，它是一套能够在传统数据库上直接进行关键字搜索的架构. 之后，BANKS系统^[3]得到启发，将关系型数据转化为图数据，利用启发式算法进行基于关键字的最小花费group Steiner tree^[1]的求解. BLINKS^[4]利用双层索引和图划分来对算法进行剪枝加速和空间优化. 受前者启发， $r$-cliques^[2]将结果建模为图，以增加模型上的信息及紧密程度，并提出一个多项式延迟的近似算法加速求解. 基于这些思路，后续研究者们在更多相关方向上展开研究. 其中不乏针对资源描述框架（resource description framework，RDF）上关键字检索的研究内容^[17]，也有图关键字检索排名函数^[18]、知识图谱关键字检索^[19]、映射集匹配的密文检索^[20]、自然语言问答与关键字检索的结合^[21]等方向的探索实践.

GPU通用计算（general-purpose computing on GPU，GPGPU^[22-24]）是利用GPU硬件强大的并行处理能力实现计算任务的技术，可以将GPU使用在图形学之外的数据处理中. 基于GPU对图论算法加速优化是一个新兴的研究方向，Harish等^[8]率先提出在统一计算架构（compute unified device architecture，CUDA）上实现广度优先搜索、单源与多源最短路径的并行算法. 受此启发，后续研究者开始在图的连接性^[25]、图的分割^[26]、图的分量标记^[27]、图的着色^[28]、动态图存储^[29]等各方面引入GPU计算平台，也有研究尝试在多GPU架构上进行图数据插补^[30]，或是在GPU平台上进行图神经网络的训练^[31]. 另一方面，基于GPU的图处理框架这一研究方向也被重视. CuSha框架^[32]采用G-Shards与邻接窗口代替传统压缩稀疏行（compressed sparse row，CSR）存储格式，并以节点为中心进行图的处理过程. WolfPath框架^[33]使用可以广泛使用于任何图结构的分层边列表来存储图，并使用它加速图上迭代遍历算法. WolfGraph框架^[34]则用邻接边表作为图的存储结构，以边为中心进行图处理.

本研究创造性地使用GPU通用计算，针对经典最小花费group Steiner tree模型提出问题，并设计基本算法，然后结合GPU架构提出优化算法，进一步提高了算法检索效率. 对于现有基于 $r$-cliques的关键字检索问题，本研究也提出了GPU上的解决思路.

本研究针对图上关键字检索问题，对该领域问题设计了基于GPU的解决方案. 提出一个图上关键字检索问题，并基于索引优化和松弛更新思想提出适应于GPU架构的算法. 根据在真实数据集上的实验结果，本研究算法即使在较大数据规模上仍有不俗的表现，相比基本求解过程更好地发挥了GPU并行架构的优势. 除此之外，本研究还对 $r$-cliques关键字检索问题进行了引申研究，对原文非多项式时间复杂度的分支定界法进行了可并行化的证明，并提出一个GPU上的算法思路. 在未来研究中，将把问题扩展至动态图中，进一步研究动态图上基于GPU的关键字检索算法.