大规模RDF图数据上高效率分布式查询处理

被引：9

作者：

王鑫 ^{[1
,2
]}

徐强 ^{[1
,2
]}

柴乐乐 ^{[1
,2
]}

杨雅君 ^{[1
,2
,3
]}

柴云鹏 ^{[4
]}

机构：

[1] 天津大学智能与计算学部

[2] 天津市认知计算与应用重点实验室

[3] 数字出版技术国家重点实验室

[4] 中国人民大学信息学院

来源：

软件学报 | 2019年 / 30卷 / 03期

基金：

天津市自然科学基金;

关键词：

星形分解; 分布式; 基本图模式匹配; 大规模RDF图; MapReduce;

D O I：

10.13328/j.cnki.jos.005696

中图分类号：

TP311.13 []; TP18 [人工智能理论];

学科分类号：

1201 ; 081104 ; 0812 ; 0835 ; 1405 ;

摘要：

知识图谱是智能数据的主要表现形式,随着知识图谱领域的不断发展,大量的智能图数据以资源描述框架(resourcedescriptionframework,简称RDF)形式发布出来.RDF图上的SPARQL查询语义对应于图同态,是一个NP-完全问题.因此,如何使用分布式方法在大规模RDF图上有效回答SPARQL查询是一个富有挑战性的问题.目前已有研究使用MapReduce计算模型处理大规模RDF数据,但其将SPARQL查询拆分成单个的查询子句,没有考虑RDF数据的丰富语义和自身的图特性,导致Map Reduce迭代次数过多.首先,利用RDF数据内嵌的语义和结构信息作为启发式信息,将查询图分解为星形的集合,可以在更少次迭代内得到查询结果.同时,分解算法给出中间结果较少的星形匹配顺序,基于此顺序,每轮Map Reduce操作通过连接操作匹配一个新的星形,直至产生最终的答案.最后,在标准合成数据集WatDiv和真实数据集DBpedia上进行大量的实验评估.实验结果表明:所提基于星形分解的分布式SPARQLBGP匹配算法能够高效回答查询,查询时间比SHARD和S2X算法的查询时间平均提高一个数量级,且优化算法的查询时间与基本算法相比缩短了49.63%～78.71%.

引用

页码：498 / 514

页数：17