-
题名大规模RDF图数据上高效率分布式查询处理
被引量：9
- 1
-
-
作者
王鑫
徐强
柴乐乐
杨雅君
柴云鹏
-
机构
天津大学智能与计算学部
天津市认知计算与应用重点实验室
数字出版技术国家重点实验室
中国人民大学信息学院
-
出处
《软件学报》
EI
CSCD
北大核心
2019年第3期498-514,共17页
-
基金
国家自然科学基金(61572353
61402323
+3 种基金
61472427)
天津市自然科学基金(17JCYBJC15400)
数字出版技术国家重点实验室开放课题
北京自然科学基金(4172031)~~
-
文摘
知识图谱是智能数据的主要表现形式,随着知识图谱领域的不断发展,大量的智能图数据以资源描述框架(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%.
-
关键词
星形分解
分布式
基本图模式匹配
大规模RDF
图
MAPREDUCE
-
Keywords
star decomposition
distributed
basic graph pattern matching
large scale RDF graphs
MapReduce
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
