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

龙源期刊网 http://www.qikan.com.cn

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

作者：林培裕

来源：《电脑知识与技术》2018年第01期

摘要：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大于预先设置的阈值；