基于大规模图数据k步可达性索引技术研究现状

◆宋亚青

（河北工业大学计算机科学与软件学院 天津 300401）

基于大规模图数据k步可达性索引技术研究现状

◆宋亚青

（河北工业大学计算机科学与软件学院 天津 300401）

随着大数据时代的来临，数据规模呈指数级速度增长，越来越多的复杂结构数据需要用图数据结构模型来表示。如何高效而快速地检索大图数据成为研究的热点。现阶段，大部分k步可达性查询都是通过构建索引来实现的。研究发现，构建索引的时间、空间消耗和查询时间之间存在瓶颈，如何合理地构建索引成为研究的热点问题。

图数据; k步可达性查询; 索引

0 前言

随着互联网技术的高速发展，大量数据每天不断涌现，“大数据”这个名词已经逐步融入我们的日常生活，伴随着海量数据出现的是数据结构的多样化。图[1]做为一种特殊的数据结构，在处理大规模数据的时候有着广泛的应用。由于往日研究的可达性查询存在着很大的局限性，因此能够为用户提供更多信息的k步可达性查询将成为研究的重点和难点问题[2]。在许多实际问题中，k步可达性查询具有更加重要的研究意义[3]。所有的查询都是通过构建索引来实现的。研究发现，构建索引的时间、空间消耗和查询时间之间存在瓶颈。但是随着科学技术的进步，计算机的配置变得越来越高，存储容量也变得越来越大，空间消耗不再是制约算法查询效率的首要考虑因素，因此本着空间换取时间的原则，通过创建索引可以有效地提高算法的查询效率，下面主要介绍了5类基于不同索引的查询算法。

1 索引介绍

现阶段k步可达性查询研究中的查询方法主要包括：基于图遍历的查询方法、基于区间标签的查询方法、基于最短路径的查询方法、基于k步索引的查询方法、基于双向搜索的查询方法。其中第一类方法不需要构建索引来实现，后四种算法是基于构建的索引实现的。

1.1 基于图遍历的查询方法

图的遍历指的是从图中某一顶点出发访问遍图中其余所有顶点，且使每一个顶点仅被访问一次，通常有两条遍历图的路径：深度优先搜索和广度优先搜索。基于这两种遍历方式，可以解决k步可达性查询问题。

深度优先搜索算法的核心思想是：判断顶点u到顶点v是否k步可达，从u出发，访问u的任意一个未被访问过的邻接点v0，即判断顶点v0是否k-1步可达顶点v，此时需要遍历v0的任意一个未被访问过的邻接点，依次类推，直至走完k步为止，若一直没有判断出结果，则回溯到上一个访问过的顶点，对该顶点未访问过的其他邻接点继续进行遍历，直至遍历完所有邻接点为止。若中途，判断出顶点u是k步可达顶点v的，则直接返回; 否则要遍历与顶点u相连接长度为k的所有路径。

广度优先搜索算法的核心思想是：判断顶点u到顶点v是否k步可达，需要访问和顶点u相连接的所有邻接点qi，然后从这些邻接点qi出发，依次判断qi是否k-1步可达顶点v，重复上述操作，直至遍历完所有邻接点。若中途，判断出顶点u是k步可达顶点v的，则直接返回; 否则需要遍历完与顶点u相连接的长度为k的所有路径。

1.2 基于区间标签的查询方法

该类查询算法主要包括GRAIL、GRIPP和PathTree，典型算法是2010年Jin等人提出的GRAIL索引方法，该方法的基本思想是:为了降低判断过程中的误判率，该算法按照从左到右和从右到左两种不同的深度优先遍历方式为每个顶点w构建双区间标签，记为Lw1和Lw2。给定有向无环图G，判断u→kv是否成立，只有满足条件时，则得出结论顶点u不可达顶点v，对于所有没有通过区间标签判断出可达性的顶点需要通过递归判断u的孩子顶点是否（k-1）步可达顶点v。

该算法的缺点是大量的递归操作带来的时间开销和空间开销会严重影响系统的查询效率。

1.3 基于最短路径的查询方法

该类方法的算法主要有PLL、TEDI和IS-LABEL，而典型的算法是Akiba等人提出的PLL算法，这个算法需要为每个顶点构建两个区间标签分别记为Lin（u）和Lout（u），判断w→ku是否成立，首先需要得到顶点w的出度标签Lout（w）和顶点u的入度标签Lin（u）标签，然后将Lout（w）与Lin（u）两个标签取交集，将取交运算的结果相加得到从顶点w到顶点u的路径值，最后从这些路径值中取最小值作为两顶点之间的最短路径值d。如果d≤k，则说明顶点w在k 步之内到达顶点u; 否则不可达。该方法的缺点是两顶点对不可达时，求解代价比较高，严重影响系统的查询性能。

1.4 基于k步索引的查询方法

该方法是Cheng等人首次提出专门用于解决k步可达性查询问题的，基本思想是:求出给定图的一个顶点覆盖集，根据覆盖集来建立k步索引，基于建立的索引实现k步可达性查询。

k步可达性查询处理的核心思想:假设判断顶点u到顶点v是否k步可达，可以分为以下三种情况:（1）要查询的两个顶点u和v都是最小顶点覆盖集S中的顶点，则需要判断在覆盖集中，两顶点之间是否存在边连接; （2）起始顶点u和终止顶点v只有一个在顶点在覆盖集中，假设顶点u（或v）在覆盖集中，则要求出顶点v的入度顶点集（或u的出度顶点集），之后判断在顶点覆盖集S中，顶点u（或v）和顶点v的入度顶点集（或是顶点u的出度顶点集）中是否存在路径长度d≤ k-1，若存在，则顶点u到顶点v是k步可达的，否则k步不可达; （3）两顶点都不在顶点覆盖集S中。计算出顶点u的出度顶点集中到顶点v的入度顶点集中是否存在路径长度d≤ k-2。若存在，则u→kv成立，否则不成立，该方法的缺点在于:只适合小规模的图数据。

1.5 基于双向搜索的查询方法

2015年，周等人在GRAIL算法的基础上提出了BiRch算法，该算法的核心思想是:判断两顶点是否k步可达时，首先根据GRAIL算法中的双区间标签，快速判断出不可达顶点对，然后比较起始顶点u的出度和目标顶点v的入度，始终从度小的一方开始查询，周等人在BiRch算法的基础上进一步提出了BiRch-BTL算法，BiRch-BTL算法的特点是通过四种剪枝策略过滤掉部分不可达顶点对，提高了算法的查询效率，但这两种算法存在问题是:无法记录已查询过的不可达顶点对，出现大量冗余顶点对的重复判断现象，因此严重影响系统的查询性能。

2 结束语

伴随着海量数据出现的是数据结构的多样化，如何在种类繁多的数据中获得有用信息是急需解决的问题。尽管目前针对大规模图数据提出了一些有效的索引方法，但在实际应用中仍存在许多亟待解决的问题，本文讨论了k步可达性索引技术的应用前景，对研究者改进k步可达性查询算法有着重要的意义。

[1]Fan Wen-fei，Wang Xin，Wu Ying-hui.Querying big graphs within bounded resources[C].In:Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data.Utah，USA，2014.

[2]Cheng J，Shang Z，Cheng H.Efficient processing of k-hop reachability queries.VLDB Journal，2014.

[3]Hua Wen，Zheng Kai，Zhou Xiao-feng.Microblog entity linking with social temporal context[C].In:Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data.Melbourne，Australia，2015.