论文部分内容阅读
随着知识图谱领域的不断发展,大量的数据以资源描述框架(RDF)形式发布出来,RDF图的规模往往可以达到数亿条边,超过了单机的处理能力,因此如何在这种大规模的RDF图上进行高效的数据查询变得尤为重要。本文设计两种高效的RDF图上分布式子图匹配查询方法。第一种方法基于MapReduce高效回答RDF图上的子图匹配查询,首先利用RDF数据内嵌的语义和结构信息作为启发式信息将查询图分解为星形的集合,可以在更少次迭代内得到查询结果。同时本文的分解算法给出中间结果较少的星形匹配顺序,基于此顺序,每轮MapReduce操作通过连接操作匹配一个新的星形,直至产生最终的答案。同时通过布隆过滤器编码顶点的邻居信息减少数据输入,并推迟笛卡尔积提高查询性能。本文的另一个方法基于Pregel模型分布式处理RDF图上的子图匹配查询。将最短路径将SPARQL查询图转化为一个变种的SP-Tree,利用Pregel处理SPARQL查询,并提出两个优化策略来提高算法的有效性。一个技术通过RDF属性过滤本地计算和消息传递,另一个优化技术推迟笛卡尔积减少查询匹配过程中的中间结果。最后,在标准合成RDF数据集和真实RDF数据集上进行大量的实验评估。实验结果表明本文所提基于星形分解的分布式算法SDec和基于Pregel的SPTree算法能够高效回答SPARQL查询,查询时间比SHARD和S2X算法的查询时间平均提高一个数量级,且优化算法的查询时间与基本算法相比显著提高。