- This event has passed.
A Framework for Processing Large Graphs in Shared Memory
July 25, 2016 @ 6:30 pm
Julian Shun, Miller Research Fellow, UC Berkeley
ACM Doctoral Dissertation Award
*** Bring ID (e.g. Driver’s License) for eBay Security ***
6:30 Doors Open, Food & Networking
*** Please arrive by 7 PM due to Security ***
In this talk, I will discuss Ligra, a shared-memory graph processing framework that 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 and automatically adapt to their density, which makes the framework useful for many graph traversal algorithms that operate on subsets of the vertices. Ligra is able to express a broad class of graph algorithms including breadth-first search, betweenness centrality, eccentricity estimation, connectivity, PageRank, single-source shortest paths, and local clustering algorithms. I will describe implementations of parallel algorithms in Ligra and present performance results. I will also discuss Ligra+, an extension of Ligra that uses graph compression to reduce space usage and improve parallel performance.
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 is interested in developing large-scale parallel algorithms for graph processing, and parallel text algorithms and data structures. He is also interested in designing methods for writing deterministic parallel programs and benchmarking parallel programs. He has received the ACM Doctoral Dissertation Award, CMU School of Computer Science Doctoral Dissertation Award, Miller Research Fellowship, Facebook Graduate Fellowship, and a best student paper award at the Data Compression Conference.
Event page provided by ACM