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

简介：《软件学报》（CN：11-2560/TP）是一本有较高学术价值的大型月刊，自创刊以来，选题新奇而不失报道广度，服务大众而不失理论高度。颇受业界和广大读者的关注和好评。

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社