Changes

In the second part of the talk, we will discuss Ligra, a shared-memory graph processing system that we recently developed. The framework has two very simple routines, one for mapping over edges and one for mapping over vertices. The routines can be applied to any subset of the vertices, which makes the framework useful for many graph traversal algorithms that operate on subsets of the vertices. Based on recent ideas used in a very fast algorithm for breadth-first search (BFS), the routines automatically adapt to the density of vertex sets.  We implement several algorithms in this framework, including BFS, betweenness centrality, graph radii estimation, graph connectivity, PageRank and single-source shortest paths.  Our algorithms expressed using this framework are very simple and concise, and perform almost as well as highly-optimized code. Furthermore, they get good speedups on multicore machines and are sometimes significantly more efficient than previously reported results using graph frameworks on machines with many more cores.

In the second part of the talk, we will discuss Ligra, a shared-memory graph processing system that we recently developed. The framework has two very simple routines, one for mapping over edges and one for mapping over vertices. The routines can be applied to any subset of the vertices, which makes the framework useful for many graph traversal algorithms that operate on subsets of the vertices. Based on recent ideas used in a very fast algorithm for breadth-first search (BFS), the routines automatically adapt to the density of vertex sets.  We implement several algorithms in this framework, including BFS, betweenness centrality, graph radii estimation, graph connectivity, PageRank and single-source shortest paths.  Our algorithms expressed using this framework are very simple and concise, and perform almost as well as highly-optimized code. Furthermore, they get good speedups on multicore machines and are sometimes significantly more efficient than previously reported results using graph frameworks on machines with many more cores.