大规模图数据的正则路径查询
Regular Path Queries on Large Graph Data

摘要 提出一种基于大规模RDF查询引擎gStore的分而治之方法, 对查询的正则表达式进行划分。在对定长字符串预处理的基础上, 再处理带有通配符的即时路径查询。该方法能够在开始阶段对搜索空间进行大量剪枝, 可以提高查询性能, 还能很好地解决正则表达式在RDF图中的路径匹配问题, 保证了对大规模图数据的支持。在DBpedia和LUBM上的实验表明, 该方法能够平均在秒级时间内返回路径查询结果。
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.