Graph Programming Interface (GPI): A Linear Algebra Programming Model for Large Scale Graph Computations
Graph Programming Interface (GPI): A Linear Algebra Programming Model for Large Scale Graph Computations
复制标题
图编程接口 (GPI)：用于大规模图计算的线性代数编程模型
DOI：
10.1007/s10766-016-0481-y
复制
发表时间：
2016
影响因子：
1.5
通讯作者：
Hao Yu
中科院分区：
文献类型：
--
作者：
William P. Horn;Manoj Kumar;Joefon Jann;J. Moreira;P. Pattnaik;M. Serrano;Gabriel Tanase;Hao Yu
图处理正在成为分析社会和生物网络、欺诈检测和情感分析等许多应用领域中出现的大数据的关键组件。因此，在文献中已经提出了许多用于图分析的计算模型，以帮助用户编写高效的大规模图算法。在本文中，我们提出了一种使用基于线性代数的规范来实现图算法的替代模型。我们首先指定一组线性代数基元，允许用户通过线性代数运算的组合来表示图算法。然后，我们使用C++\Documentclass[12pt]{Minimum}\usepackage{amsath}\usepackage{wa ysym}\usepackage{amsfonts}\usepackage{amsbsy}\usepackage{mathsfs}\usepackage{upgreek}\setlong{\oddsidemargin}{-69pt}\Begin{Document}$++$$\end{Document}以及随后与Spark框架的集成来描述这些原语的高性能实现，以实现大型系统所需的可扩展性。我们概述了我们的实现，并将用我们的方法实现的各种算法的表现力和性能与这些算法的当前Spark GraphX实现的表达能力和性能进行了比较和对比。
Graph processing is becoming a crucial component for analyzing big data arising in many application domains such as social and biological networks, fraud detection, and sentiment analysis. As a result, a number of computational models for graph analytics have been proposed in the literature to help users write efficient large scale graph algorithms. In this paper we present an alternative model for implementing graph algorithms using a linear algebra based specification. We first specify a set of linear algebra primitives that allows users to express graph algorithms by composition of linear algebra operations. We then describe a high performance implementation of these primitives using C++\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$++$$\end{document} and subsequently its integration with the Spark framework to achieve the scalability we need for large systems. We provide an overview of our implementation and also compare and contrast the expressiveness and performance of various algorithms implemented with our approach with that of the current Spark GraphX implementation of those algorithms.