实验室动态

[2019 ICDE] Accelerating Partial Evaluation in Distributed SPARQL Query Evaluation

局部计算(Partial Evaluation)最近已经被用于分布式环境下大规模RDF图上的SPARQL查询处理。然而,之前的方法在处理复杂查询的时候效率很低。在本工作中,我们在提供性能保证的基础上进一步提高分布式RDF数据图上基于“局部计算与归并”的SPARQL查询处理框架的效率。我们的核心想法在于发现局部解的内部结构特性来剪枝掉一些无关的局部解,同时提供在数据通信和响应时间方面性能保证。我们也提出了一个高效的归并算法来利用局部解特性进行局部解合并以找到最终解。为了进一步提高局部解求解效率,我们还提出了一个优化策略来通信变量的候选以避免重复计算。此外,尽管我们的方法是独立于数据划分的,但是不同划分依然对效率有不同影响,所以我们评估了不同划分策略对我们方法影响。在真实和人造数据集合上的实验验证了我们方法的优越性。