Julian Shun, Laxman Dhulipala, Guy Blelloch

Abstract

There has been significant recent interest in large-scale graph analytics due to the constantly growing volume of unstructured data. As such, various high-level frameworks have been developed to enable programmers to easily write efficient solutions to their graph problems. This tutorial will introduce the Ligra abstraction for designing graph algorithms in shared memory based on mapping functions over subsets of vertices and/or edges in graphs. Attendees will learn how to write standard graph algorithms, such as breadth-first search, single-source shortest paths, and PageRank, in Ligra, and run them on real-world graphs. A comparison with other graph processing frameworks such as Pregel, GraphLab, and CombBLAS, will be presented. The tutorial will also present graph compression techniques that can improve the space usage as well as the parallel performance of graph algorithms. These techniques are integrated into Ligra+, an extension of the Ligra system using the same abstraction. Finally, the tutorial will show how Ligra can be used to efficiently and accurately estimate eccentricities in large real-world graphs, which is a useful application in social network analysis.

Outline

• Abstractions for graph algorithms
• The Ligra interface: VertexSubset, VertexMap, and EdgeMap
• Direction-optimizing breadth-first search and its generalization
• Examples: Breadth-first search, PageRank, single-source shortest paths
• Other abstractions for graph algorithms: Pregel, GraphLab, CombBLAS, etc.
• Performance comparison of Ligra to optimized code and other frameworks
• Parallel Processing of Compressed Graphs
• Graph representations
• Variable-length codes for compression
• Ligra+: extending the Ligra system with compressed graphs
• Comparison of space/time performance of Ligra+ with Ligra
• Application: Graph Eccentricity Estimation
• Real-world applications
• Exact and approximate algorithms
• Implementation of algorithms in Ligra
• Experimental comparison among different algorithms

Prerequisites

Familiarity with C++ and Unix.

Tutorial Website

http://jshun.github.io/ligra

Who

Julian Shun is currently a Miller Research Fellow (post-doc) at UC Berkeley. He obtained his Ph.D. in Computer Science from Carnegie Mellon University, and his undergraduate degree in Computer Science from UC Berkeley. He has developed large-scale parallel algorithms for graph processing, and parallel text algorithms and data structures. He has also designed methods for writing deterministic parallel programs and benchmarking parallel programs.

Laxman Dhulipala is currently a Computer Science Ph.D. student at Carnegie Mellon University. He obtained his undergraduate degree in Computer Science from Carnegie Mellon University. Most recently, he spent a year working on distributed graph algorithms in Apache Giraph at Facebook.

Guy Blelloch is a Professor of Computer Science at Carnegie Mellon. He received a BA from Swarthmore College in 1983 and a PhD degree from MIT in 1988. His research interests are in programming languages and algorithms and how they interact, with an emphasis on parallel computation. He is an ACM Fellow for his contributions in parallel computation, and for the past four years was General Chair of the ACM Symposium on Parallelism in Algorithms and Architecture (SPAA).

http://www.eecs.berkeley.edu/~jshun/ligra.pdf