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

北京大学学报(自然科学版) 第 54 卷 第 2 期 2018 年 3 月 Acta Scientiarum Naturalium Universitatis Pekinensis, Vol. 54, No. 2 (Mar. 2018) doi: 10.13209/j.0479-8023.2017.151 大规模图数据的正则路径查询 张雨 曾立 邹磊† 北京大学信息科学技术学院 , 北京 100871; † 通信作者 , E-mail: zoulei@ 摘要 提出一种基于大规模 RDF 查询引擎 gStore 的分而治之方法, 对查询的正则表达式进行划分。在对定 长字符串预处理的基础上, 再处理带有通配符的即时路径查询。该方法能够在开始阶段对搜索空间进行大量 剪枝 , 可以提高查询性能, 还能很好地解决正则表达式在RDF 图中的路径匹配问题, 保证了对大规模图数据 的支持。在DBpedia 和 LUBM上 的实验表明, 该方法能够平均在秒级时间内返回路径查询结果。 关键词 属性路径 ; 正则表达式; SPARQL; RDF; gStore 中图分类号 TP391 Regular Path Queries on Large Graph Data † ZHANG Yu, ZENG Li, ZOU Lei School of Electronics and Computer Science, Peking University, Beijing 100871; † Corresponding author, E-mail: zoulei@ Abstract 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. Key words property path; regular expression; SPARQL; RDF; gStore 随着语义网的发展, 网络上涌现大量的资源描 本文提出的基于 gStore[6]引擎的正则路径检索 述框架[1](resource description framework, RDF)数据 方法 ,