An Efficient Graph Query Framework with Structural Recursion. (4th July 2017)

• Record Type: Journal Article
• Authors: Meng, Xiaodong; Guo, Minyi; Zhang, Jingyu
• Is Part Of: Computer journal. Volume 61:Number 1(2018)
• Page Start: 144
• Page End: 157
• Publication Date: 2017-07-04
• Subjects: graph query -- structure recursion -- distributed graphs -- bulk semantics; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxx062
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: The potential to promote market value by analysing graph-structured data is increasingly attracting businesses from a variety of industries, ranging from Internet companies to traditional enterprises. However, the query over large graphs easily and efficiently is still a critical problem in large scale distributed systems. Many proposed systems have to use low-level programming model, like Pregel, which requires a large amount of code optimization and maintenance work by developers. Although structural recursion has been studied as an efficient high-level programming model for graph transformations, it is not well exploited in practice to accelerate the parallel graph computing. To address the above problem, in this paper, we propose optimizations of structure recursion for distributed graphs to reduce the number of iterations during graph query processing in a distributed system. In order to improve query response time and throughput, subgraph based computation on structure recursive functions are used to replace typical vertex based evaluation approach. Meanwhile, we propose several redundancy rules to reduce graph size in parallel. We verify the performance of our system through evaluation on real datasets. The results show that, compared to the state-of-the-art approach (Tung and Hu (2015) Towards systematic parallelization of graph transformations over pregel, pp. 1–20. Springer), our algorithm achieves speedup over two times on query response time.