大规模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

共 22 条

[1] Graph X:graph processing in a distributed dataflow framework. GONZALEZ J E,XIN RS,DAVE A,et al. OSDI . 2014
[2] MapReduce[J] . Jeffrey Dean,Sanjay Ghemawat. &nbspCommunications of the ACM . 2008 (1)
[3] gStore: a graph-based SPARQL query engine[J] . Lei Zou,M. Tamer ?zsu,Lei Chen,Xuchuan Shen,Ruizhe Huang,Dongyan Zhao. &nbspThe VLDB Journal . 2014 (4)
[4] The complexity of counting graph homomorphisms. Martin Dyer,Catherine Greenhill. Random Structures and Algorithms . 2000
[5] RDF-3X: a RISC-style engine for RDF. Thomas Neumann,Gerhard Weikum. Proceedings of the VLDB Endowment . 2008
[6] Heuristics-based query processing for large RDF graphs using cloud computing. Husain, Mohammad Farhan,McGlothlin, James,Masud, Mohammad Mehedy,Khan, Latifur R.,Thuraisingham, Bhavani. IEEE Transactions on Knowledge and Data Engineering . 2011
[7] Efficient subgraph matching on billion node graphs. Zhao Sun,Hongzhi Wang,Haixun Wang,Bin Shao,Jianzhong Li. Proceedings of the VLDB Endowment . 2012
[8] DREAM:Distributed RDF engine with adaptive query planner and minimal communication. Hammoud M,Rabbou D A,Nouri R,et al. Proceedings of the VLDB Endowment . 2015
[9] High-performance, massively scalable distributed systems using the MapReduce software framework:the SHARD triple-store. Rohloff K,Schantz R E. Programming Support Innovations for Emerging Distributed Applications . 2010
[10] S2RDF:RDF querying with SPARQL on Spark. Schatzle A,Przyjaciel-Zablocki M,Skilevic S,et al. Proceedings of the VLDB Endowment . 2016

← 1 2 3 →