Parallelizing Graph Structural Recursion with BSP
Parallelizing Graph Structural Recursion with BSP
复制标题
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Chong Li;Le-Duc Tung;N. Duong;S. Hidaka;Zhenjiang Hu
中科院分区：
文献类型：
--
作者：
Chong Li;Le-Duc Tung;N. Duong;S. Hidaka;Zhenjiang Hu
如今，不断增长的数据量迫切需要可扩展的系统来有效地处理大数据。图结构可以自然地扩展到大型数据集，因为它不需要关系数据库查询经常需要的昂贵的连接操作。然而，在大型图上的复杂查询仍然是非常昂贵的计算。此外，不同查询的优化算法还需要进行个案研究。递归可以用结构递归来表示，就像用传递闭包扩展的一阶逻辑。这给我们提供了一种新的思路，即图查询可以用结构递归的方式进行推广。因此，可以通过优化结构递归以有效的方式系统地评估查询。本文首次实现了结构递归的并行实现。因此，提出了一种新的框架，基于批量同步并行（BSP），以评估大型图查询。它提供了一个系统的方法来处理一般的图形查询。框架的实现将结构递归付诸实践，完成了许多理论无法涵盖的不明确部分。性能评估表明，BSP可以有效地处理大型图查询，具有良好的可扩展性。我们的框架的验证是一个系统的大型分布式图，我们可以应用规则自动推理程序的算法发展的重要一步。
The ever-increasing size of data today creates a critical need for scalable systems that can process large data efficiently. Graph structure can scale naturally to large datasets, as it does not require expensive join operations that are often needed by relational database querying. However, a complex query on a large graph is still very expensive in computation. Moreover, optimizing algorithms of different queries is still needed to study case by case. Queries can be expressed by structural recursion like first-order logic extended with transitive closures. It gives us a new thinking that graph queries can be generalized in a structural-recursion way. Therefore, querying can be systematically evaluated in an efficient way by optimizing the structural recursion. In this paper, the structural recursion is first time implemented in parallel. A novel framework, based on Bulk Synchronous Parallelism (BSP), is thus proposed to evaluate large-graph queries. It provides a systematic way to deal with general graph queries. The implementation of the framework puts the structural recursion into practice and completes many unclear parts that cannot be covered by the theory. The performance evaluation shows that BSP can handle large-graph querying efficiently with a good scalability. The validation of our framework is an important step towards a systematic development of algorithms on large distributed graphs in which we can apply rules to automatically reasoning about programs.