大数据 ›› 2019, Vol. 5 ›› Issue (4): 16-26.doi: 10.11959/j.issn.2096-0271.2019029

• 专题:大数据的系统结构 • 上一篇    下一篇

基于图查询系统的图计算引擎

柯学翰,陈榕   

  1. 上海交通大学软件学院并行与分布式系统研究所,上海 200240
  • 出版日期:2019-07-15 发布日期:2019-08-09
  • 作者简介:柯学翰(1996- ),男,上海交通大学软件学院并行与分布式系统研究所硕士生,主要研究方向为分布式图计算系统。|陈榕(1981- ),男,博士,上海交通大学软件学院并行与分布式系统研究所副教授,主要研究方向为并行与分布式系统、内存计算等。
  • 基金资助:
    国家自然科学基金资助项目(61772335)

Graph processing engine based on graph query system

Xuehan KE,Rong CHEN   

  1. Institute of Parallel and Distributed Systems,Software School,Shanghai Jiao Tong University,Shanghai 200240,China
  • Online:2019-07-15 Published:2019-08-09
  • Supported by:
    The National Natural Science Foundation of China(61772335)

摘要:

在目前的研究中,图查询和图计算系统是相互独立的,但在实际应用中两者通常是同时存在的。为解决相互独立的系统带来的存储空间浪费、数据一致性维护等问题,基于图查询系统设计了一种图计算引擎,使得在单一系统中支持查询和计算操作。通过为键值对存储增加图计算索引、基于拉取模式的数据更新等方式,有效地提高系统中数据遍历的性能和减少数据传输的成本,同时针对数据更新和负载均衡等方面提出了相关优化。实验表明,该图计算引擎能够达到与传统图计算系统PowerLyra和Gemini相近或比其更优的性能,且具有较好的可扩展性。

关键词: 分布式系统, 图计算, 图查询, 键值对存储

Abstract:

Recently,graph query and graph processing are emphasis of graph-structured data research.However,independent graph system mismatched combining applications,which needed both query and processing.To avoid some issues brought by independent system,such as wasting resource and data inconsistency,a method that providing a graph processing engine based on graph query system was proposed,in order to support query and processing operation in a unified system.Through adding index for graph processing and applying pull-based graph propagation method to over locality issue,the performance of the computation and transmission was largely improved.Besides,some optimization approaches were put forward for message updating and work balanced.The experimental results show that the processing engine can provide close(reduced by no more than 1x) or even better (up to 20x) performance compared to specific graph processing systems (e.g.,Gemini and PowerLyra) by leveraging new designs and optimizations,and also has good scalability.

Key words: distributed system, graph processing, graph query, key-value store

中图分类号: 

No Suggested Reading articles found!