专场5.6-分布式知识图谱管理技术介绍-彭鹏.pptx

《专场5.6-分布式知识图谱管理技术介绍-彭鹏.pptx》由会员分享，可在线阅读，更多相关《专场5.6-分布式知识图谱管理技术介绍-彭鹏.pptx（71页珍藏版）》请在三个皮匠报告上搜索。

1、分布式知识图谱管理技术介绍,彭鹏湖南大学 信息科学与工程学院 副教授,背景介绍集群式系统联邦型系统总结,目录,3,背景介绍,Part 1,4,RDF 简介,5,资源描述框架（Resource Description Framework）,它是一种被广泛用于知识库的数据模型所有东西都是唯一命名的资源可以定义资源的属性可以定义与其他资源的关系,dbpedia:Zayed_Khan,dbpedia:name Zayed Khanendbpedia:dateOfBirth 1980-07-05,dbpedia:birthPlace,dbpedia:Maharashtra,RDF 知识图谱,6,RDF数

2、据集可以表示为图，进而构成知识图谱,RDF知识图谱上的查询模型,7,查询模型SPARQL查询语言SPARQL查询是一组带有变量的三元模式,Select?x where?yresidence?z.?ybirthPlace?x.?xfoundingDate1947-08-15.,RDF知识图谱上的查询模型,8,回答SPARQL查询=使用同态的子图匹配,*,RDF知识图谱规模,9,现在，基于RDF的知识图谱数据集变得越来越大,Leipzig UniversityUniversity of MannheimOpenLink Software,Max-Planck-Institute,Metaweb C

3、ompanyacquired by Google in 2010,95亿三元组,2.84亿个三元组,24亿三元组,设计一个分布式RDF系统来管理大型RDF数据集非常重要,集群式系统,Part 2,10,分布式RDF知识图谱管理系统体系结构,11,基于划分的分布式架构,通过对RDF知识图谱的划分将其分不到不同的站点目标：并行化查询处理，尽可能少的站点间通信,分布式查询执行模型,12,对数据和查询进行划分，以尽量减少分区间连接,相关工作,13,RDF知识图谱划分方法可以分为三种类型:,顶点不相交：将每个顶点放在一个分区中现有方法的目标是最小化切边，而不是最小化分区间连接边不相交：将每条边放在一个分

4、区中现有基于大数据计算平台的系统广泛使用，以删除不相关的分区，并避免在大数据计算平台中进行过多的扫描，但没有关注避免分区间连接其他：考虑额外的信息，比如查询日志,H-RDF-3X Huang et al.,VLDB 2011,14,使用METIS对数据进行分区使用n-hop保证复制顶点如果Q的半径不大于n，则每个站点都可以对Q进行本地执行如果Q的半径大于n，则将Q分解为几个可独立求值的子查询Qi；然后将它们的结果连接起来,SHAPE Lee et al.,VLDB 2013,15,按照点生成边组 语义哈希边组：URI引用通常具有层次结构，具有共同祖先的URI引用通常连接在一起，因此SHAPE将

5、此类URI引用(顶点)放在同一个分区中 允许在不同分区之间复制一些数据,示例三元组,16,黑色子图是一个基于subject的三元组 红色子图是一个基于object的三元组 整个图是一个基于subject-object的三元组,最小属性切 Peng et al.,ICDE 2022,17,我们提出了一种新的点划分方案，最小属性切（Minimum Property-Cut，MPC），用于分布式SPARQL查询处理,内部和跨界属性,当且仅当一个属性与该属性至少有一条跨界边时，该属性被称为跨界属性；否则，它被称为内部属性,18,设计目标,19,分布式SPARQL执行中的主要性能瓶颈是分区间连接如果查询

6、中的所有属性都是内部的，则在每个分区上独立执行，不需要分区间连接设计目标：内部属性的数量最大化可能增加切边，但减少唯一属性切边的数量,不同分区的比较示例,20,最小属性切,示例RDF知识图谱划分,问题定义,21,给定RDF知识图谱G和正整数k,G的最小属性切割(MPC)分区是一个分区F=F1,F2,.,Fk 跨界属性|Lcross|的数量最小化(即内部属性|Lin|的数量最大化);对于每个Fi,Fi(即|Vi|)的大小不大于(1+)|V|/k，其中是用户定义的分区的最大不平衡比率(即分区的相对大小可以有多大差异)。,MPC复杂度,22,定理:MPC划分问题是NP完全的。证明:我们将NP完全最小