一种改进的RDF数据k—hop划分算法

林培裕

摘要：RDF数据k-hop划分算法是基于RDF大图顶点划分的算法，通过数据复制冗余以优化分布式RDF查询处理系统在特定SPARQL查询模式下的查询性能。针对算法可能会导致的数据倾斜及数据过量冗余问题，提出一种改进的RDF数据k-hop划分算法。该算法通过引入实体顶点的结构与语义特征，将具有相似特征的图顶点均匀分布到集群中，降低数据冗余量，提升算法的时间与空间性能。实验结果表明，改进后的算法是高效的。

关键词：RDF；SPARQL；分布式系统；k-hop算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）01-0015-03

1 概述

随着越来越多的项目与机构采用RDF数据模型来表示它们的公共知识库等静态数据集，原先单节点式的RDF查询处理系统已难以满足海量数据的查询需求，因此分布式RDF查询处理技术已经成为当前语义网领域的一大重点。分布式RDF查询处理一般包含数据划分、查询分解与子查询中间结果合并三个阶段[1]，其中数据划分算法会在一定程度上影响网络IO的开销。k-hop数据划分算法[2]通过数据复制冗余以优化SPARQL查询中的Star与Linear型模式[3]查询，然而该算法没有利用RDF数据本身的语义与图结构信息，导致划分结果冗余较大且会产生数据倾斜。本文提出了一个k-hop算法的改进方法，该方法能在一定程度上降低数据复制冗余量并提升查询性能。

2 RDF数据k-hop划分算法

RDF数据集中的每一条三元组都可以被看做是图的一条边，因此整个RDF三元组集形成了一张大图，顶点即主体或客体，统称为实体。k-hop算法是一个基于顶点哈希划分的算法，具体过程如下：

1） 对于顶点集V中的所有实体进行随机哈希分配到机器中，，其中count为集群的机器个数；

2） 设，遍历每台机器上当前顶点集，将与其中每个顶点连通且路径长度在k之内的顶点同样复制到该机器上；

3） 递增k，并重复步骤2），直到k大于预先设置的阈值；

4） 遍历每台机器上的最终顶点集，将以其中某个实体顶点为主体或客体的三元组分配到该机器上。

k-hop算法对长度在k之内的Linear型SPARQL查询模式较为友好，然而该算法需要对该长度阈值范围内的实体顶点进行跨机器复制，数据冗余量较大，且前期的顶点哈希分配没有考虑到顶点的语义与结构特征，可能会导致严重的数据倾斜。

3 RDF图顶点向量学习

针对k-hop算法没有考虑到RDF数据的语义与图结构特征的问题，在顶点哈希分配之前引入一道新流程，提出基于SPARQL查询模式的随机游走模型，并通过该模型学习得到实体顶点的向量表示，以表征实体顶点的语义与结构特征。

3.1 SPARQL查询模式

一条SPARQL查询语句可以由多条带有变量的三元组构成，根据变量的位置可以将SPARQL语句分解成多条如图1所示的不同查询模式[3]的子查询语句。Star型查询模式出现频次较高，大多数的分布式RDF数据管理系统都会针对这种查询模式进行优化。在将以RDF数据集中三元组的主体为中心顶点分布到不同机器上的同时，会将与相应主体相连的客体同时划分到与主体相同的机器上以满足Star型查询模式的需要。Linear型查询模式可以被看做是以某一主体为起始点的深度优先遍历。Snowflake型查询是由多条Star型查询语句与一条连接各中心顶点的Linear型查询语句组成，从图遍历的角度来说可以被看做是one-hop的广度优先遍历。

3.2 基于查询模式的有偏随机游走模型

对于RDF有向图以及随机游走顶点序列，是游走过程中的第个顶点，是的相邻顶点集合。与传统随机游走过程不同的是，将以一定的概率从中选取，而不仅仅是：

其中是对应三元组的权重（大多数数据集中不含权重概念，默认为1），是由顶点遍历到的非标准转移概率，以及是归一化因子。转移概率对随机游走过程的顶点采样会有较大的影响，如果恰好依次走过顶点和，则将会从或者中选择，分别对应了广度优先遍历与深度优先遍历。比較直观的确定该转移概率值的方法是让其与三元组的权重和成正比，然而这种办法很难仅仅通过调整三元组权重来找到广度遍历与深度遍历之间的折中点，从而不能很好的同时反映顶点之间在RDF图中的结构与语义上的相似度。因此两个参数Linear型查询模式权重与Snowflake型查询模式权重被引入来引导游走偏向性。这两个权重值能够相对容易地从分布式RDF数据管理系统的查询语句分解阶段统计得到。转移概率定义如下：

在某种意义上，参数控制了游走过程中离开当前顶点并向深处探索的速率，而参数决定了徘徊于当前顶点与周边相邻顶点的时间长短。当时，游走过程退化为one-hop的广度优先遍历，生成的游走路径类似于Snowflake。经多次迭代后从全局看类似于完整的广度优先遍历，采样生成的顶点序列能表现出顶点的局部结构特征。当时，游走过程则变成类深度遍历的过程，主要表征出顶点的语义特征。因此通过调整这两个参数值，我们的有偏随机游走模型能够为RDF图上的深度优先与广度优先遍历间提供比较平滑的过渡过程。

3.3 实体顶点向量学习

给定RDF有向图，将映射到低维向量空间的问题被称为图顶点向量学习。对于类似的问题，自然语言处理领域已经有比较成熟的解决办法，如word2vec的Skip-gram model。将上述随机游走模型经多次迭代后生成的路径线性连接作为word2vec的输入，同时调整滑动窗口大小参数以界定顶点的邻接范围。模型输出的顶点向量表示可以从一定程度上反映顶点之间的结构与语义相似度。

4 改进的k-hop RDF数据集划分算法endprint

4.1 基准点集

考虑到分布式SPARQL查询所需的高性能与均衡负载，在对RDF数据集进行k-hop划分之前，一种特殊的基准点集需首先要被均匀划分在集群中的不同机器上。基准点的选择对带有复制三元组特性的RDF数据分布算法的划分均衡性具有较大的影响。假设有两台机器的集群，对于子查询语句，如果我们将选为基准点，则部分如可能会被在多台机器上复制。在此划分基础上，对于另一条子查询语句，如果需要尽量降低两条子查询语句join期间机器内部的通信开销，也需随在多台机器上复制，这将造成严重的数据倾斜，然而将作为基准点则不会形成这种情况。

在这里我们简单地将连接度较大的顶点作为基准点，主要是基于这样的事实：随机游走期间从任意两个顶点出发相遇在连接度较大的顶点的概率较于其他顶点更大。因而如果这些连接度较大的顶点均匀分布在集群中，伴随着将k-hop遍历过程中遇到的顶点放置在同一机器上，则顶点集中的大部分点都会被涵盖。这种划分方式能有效减少k-hop算法的复制数据量，并降低数据倾斜的可能性。RDF图中顶点的连接度与顶点的出入度密切相关，即与以某实体作为三元组主体或客体的频次有着密切联系。对于，设为顶点v的出入度和，为三元组中以v为主体的不同谓词集合，为以v为主体的和p为谓词的客体集合，则顶点v的连接度定义如下：

连接度计算示例如图2所示。对于顶点s1，谓词p1的分数是（2+3）/2=2.5，谓词p2的分数是5，因此。RDF数据集中每个实体顶点的连接度值可以简单的通过遍历三元组集合统计得到。一般而言，连接度较高的顶点更容易被选为基准点。基准点集可以通过K-means算法得到。基于上一节得到的实体顶点向量进行聚类，生成的各聚类中的实体顶点在结构与语义上相似，同时拥有最高平均连接度的实体顶点聚类可被选择为基准点集。

4.2 改进算法流程

本文对传统k-hop划分算法的改进思想就是将具有相似结构与语义特征的实体顶点尽量均匀划分到分布式集群中，并且优先选择基准点集进行划分，以尽可能减少复制数据量以及数据倾斜的可能。算法的具体流程如下：

1） 遍历RDF数据集三元组集合，计算实体顶点的连接度；利用word2vec学习得到实体顶点向量；

2） 根据实体顶点向量进行K-means聚类，计算生成的各聚类的平均连接度，并从大到小进行排序；

3） 选取聚类集合中平均连接度最大的聚类，利用随机哈希将该聚类中的实体顶点均匀划分到集群中，并将以该实体顶点为主体或客体的三元组划分到同一机器上；

4） 利用k-hop算法對每一台机器上的实体顶点集与三元组集进行扩展，并从各聚类中移除扩展的实体顶点；

5） 将当前使用的聚类从聚类集合中移除，重复3）至5）步骤，直至RDF数据集中所有的实体顶点与三元组集合被划分到相应机器上。

5 实验与结果分析

本文实验采用的数据集为LUBM标准测试集[4]。LUBM是一种标准RDF数据集生成器，可根据参数大学个数生成不同大小的标准测试数据集。本文分别选取大学个数为100、500、1000生成3个标准测试集，具体信息如表1所示。实验采用的集群大小为包含6台物理机器，每台机器的配置为：Intel E5620处理器，16GB内存及1TB 7200转硬盘。

5.1 数据负载分布

如表2和表3所示为采用传统k-hop算法与改进算法时划分的数据分布情况（经统计分析，设置查询模式参数以及k-hop算法参数可以达到最好的切分与查询效果）。可以看出，传统算法产生的分布结果的数据负载有一定的抖动，不如改进算法的数据分布均匀，数据负载较重的存储节点往往会成为分布式查询处理过程中的瓶颈。同时，改进算法产生结果的平均数据负载量要小于传统算法，这能在一定程度上提升分布式SPARQL查询性能。

5.2 查询性能对比

本实验选取LUBM1000测试集与前7个LUBM提供的SPARQL查询语句进行SHARD[5]、传统k-hop算法与改进算法实现的查询系统（查询分解与中间结果合并过程均相同[6]）的性能对比测试。对比结果如图3所示，查询耗费时间均为系统运行5次的平均值。从图中可以看出，相比于SHARD系统，传统k-hop与改进算法都具有较大的性能优势，究其原因是SHARD将三元组集存储为一个大HDFS文件，每次查询都需要耗费大量的无用I/O操作，严重影响系统查询性能。而k-hop算法将数据划分后分别存储在不同的机器上，I/O操作被分散，无需每次扫描完整的三元组数据集。同时，由于改进算法较传统k-hop算法拥有更小的复制数据量与更平衡的数据负载，查询性能也较传统算法有所提升。

6 结论

改进算法和传统k-hop算法拥有相同的时间复杂度并共享相同的查询分解与中间结果合并流程。相比之下，通过添加向量学习和基准点集选择等流程降低了每台机器上的数据量，数据分布更加均衡，相当于降低了算法空间复杂度的常数因子，从而提高了查询性能。

参考文献：

[1] 杜方，陈跃国，杜小勇.RDF数据查询处理技术综述[J].软件学报，2013（6）：1222-1242.

[2] Mikolov T， Sutskever I， Chen K. Distributed Representations of Words and Phrases and their Compositionality[J].Advances in Neural Information Processing Systems，2013（26）：3111-3119.

[3] Lee K， Liu L. Scaling queries over big RDF graphs with semantic hash partitioning[J]. Proceedings of the Vldb Endowment，2013，6（14）：1894-1905.

[4] Guo Y， Pan Z， He?in J. LUBM： A benchmark for OWL knowledge base systems[J]. Web Semantics Science Services & Agents on the World Wide Web，2005，3（23）：158-182.

[5] Rohloff K， Schantz R E. Clause-iteration with MapReduce to scalably query datagraphs in the SHARD graph-store[J].International Workshop on Data-Intensive Distributed Computing.ACM， 2011：35-44.

[6] Huang J， Abadi D J， Ren K. Scalable SPARQL querying of large RDF graphs[J].Proceedings of the Vldb Endowment，2011，4.endprint