Title: Parallel Local Graph Clustering

Speaker: Julian Shun , EECS Department - UC Berkeley

Date: Friday, November 18, 2016

Time: 2:00 PM to 3:00 PM Note: all times are in the Eastern Time Zone

Refreshments: 1:45 PM

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host: Charles E Leiserson, MIT CSAIL

Contact: Cree Bruins, cbruins@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to: sys-fac@lists.csail.mit.edu, toc-faculty@csail.mit.edu

Reminder Subject: TALK: Title: Parallel Local Graph Clustering

Graph clustering has many important applications in computing, but due to growing sizes of graphs, even traditionally fast clustering methods such as spectral partitioning can be computationally expensive for real-world graphs of interest. Motivated partly by this, so-called local algorithms for graph clustering have received significant interest due to the fact that they can find good clusters in a graph with work proportional to the size of the cluster rather than that of the entire graph. This feature has proven to be crucial in making such graph clustering and many of its downstream applications efficient in practice. While local clustering algorithms are already faster than traditional algorithms that touch the entire graph, they are sequential and there is an opportunity to make them even more efficient via parallelization. In this talk, I will show how to parallelize some of these algorithms in the shared-memory multicore setting. I will present comprehensive experiments on large-scale graphs showing that the parallel algorithms achieve good parallel speedups on a modern multicore machine, thus significantly speeding up the analysis of local graph clusters in the very large-scale setting. This talk is based on work published in VLDB 2016.

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.

Research Areas:

Impact Areas:

This event is not part of a series.

Created by Cree Bruins Email at Monday, November 14, 2016 at 4:04 PM.