大规模RDF图数据上高效率分布式查询处理

知识图谱是智能数据的主要表现形式,随着知识图谱领域的不断发展,大量的智能图数据以资源描述框架(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%.

Goldfish:基于矩阵分解的大规模RDF数据存储与查询系统

随着互联网应用的迅猛发展和语义网技术研究的深入,语义数据呈现出爆炸性增长趋势.一方面,对于语义数据实现高效存储和查询是语义网应用的重要基础,越来越多的语义应用可以依赖于此以提供更好的服务;另一方面,语义数据的爆炸性增长,对大数据环境下的语义数据的存储与查询技术提出了新的挑战.传统的基于关系型数据库的语义数据与查询系统已难以满足大规模语义数据的存储与查询需求.该文针对大规模RDF数据的存储与查询问题,以OpenRDF Sesame框架为基础,采用分布式分层式存储架构,提出并实现了属性表存储结构来进行语义数据的存储.在此基础上,针对布尔矩阵分解算法在对大规模语义数据构造属性表较慢的问题,基于Spark分布式计算框架提出并实现了并行化频繁项集挖掘算法求解大规模矩阵分解,以加速属性表的构造过程.并且,在查询层增加了基于哈希转换等查询优化.最后,基于该文所提出的索引结构和优化方法设计实现了原型系统Goldfish,并在大规模合成和真实数据集上进行了实验对比.结果表明,Goldfish原型系统比Rainbow系统查询性能平均提升约6倍,比Jena-HBase查询性能平均提升约500倍,比基于MapReduce的RDF查询系统SHARD性能平均提升约1200倍.

基于图聚类算法的大规模RDF数据查询方法研究

提出一种针对大规模RDF(Resource Description Framework)数据的高效而又准确的查询方法,此方法基于图聚类算法.首先利用已被证明在处理大规模图数据时效果最好的图聚类算法对大规模RDF数据进行划分,得到一个划分结果.这个划分结果满足,划分子集内部连接非常紧密而划分子集之间连接非常稀疏.然后根据RDF查询请求对划分结果进行特定的筛选,在筛选所得的RDF数据子集上执行查询操作,从而节省大量查询响应时间,提高查询效率.我们实现了这一查询方法,并选取几个具有代表性的大规模RDF数据集进行了性能实验.实验证明,相比单纯运用目前效率最高的RDF-3X查询引擎进行查询的方法,本文提出的方法在保证较高查全率和查准率的前提下,能够大大提高查询效率.

基于Spark和Redis的大规模RDF数据查询系统

随着语义Web技术的不断发展,RDF数据量增长迅速,单机RDF查询系统已经难以满足现实需要,研究和构建分布式RDF查询系统已经成为学术界与工业界的研究热点之一.现有的RDF查询系统主要是基于Hadoop或通用分布式技术.前者磁盘I/O太高;后者则可扩展性较差.且两种系统在基本图模式查询时,效率都较低.针对上述问题,本文设计了基于Spark和Redis的分布式系统架构,并改进了查询计划生成算法,最后实现了原型系统RDF-SR.该系统使用Spark减少了磁盘I/O,借助Redis提高了数据映射速率,利用改进的算法减少了数据混洗次数.实验表明,相比于现有的其他系统,RDF-SR既保持了较高可扩展性,又在基本图模式查询时,具有更高的性能.