大规模图数据的正则路径查询  

Regular Path Queries on Large Graph Data

作　　者：张雨 曾立 邹磊 ZHANG Yu;ZENG Li;ZOU Lei(School of Electronics and Computer Science,Peking University,Beijing 100871)

机构地区：[1]北京大学信息科学技术学院,北京100871

出　　处：《北京大学学报（自然科学版）》2018年第2期236-242,共7页Acta Scientiarum Naturalium Universitatis Pekinensis

基　　金：国家重点基础研究发展计划(2016YFB1000603)资助

摘　　要：提出一种基于大规模RDF查询引擎g Store的分而治之方法,对查询的正则表达式进行划分。在对定长字符串预处理的基础上,再处理带有通配符的即时路径查询。该方法能够在开始阶段对搜索空间进行大量剪枝,可以提高查询性能,还能很好地解决正则表达式在RDF图中的路径匹配问题,保证了对大规模图数据的支持。在DBpedia和LUBM上的实验表明,该方法能够平均在秒级时间内返回路径查询结果。The authors propose a divide-and-conquer based solution over gStore,an existing RDF search engine,to process property path query on large scale graph data.In proposed solution,regular expression is partitioned within the path query and then preprocess strings of fixed length.The authors handle the search over those subqueries of wildcards.The proposed method is able to filter lots of unpromising search and efficient on solving the regular path match problem over large scale graph data.The corresponding experiments on DBpedia and LUBM confirm that proposed method can response for queries in seconds on average.

关 键 词：属性路径 正则表达式 SPARQL RDF gStore 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]