Quanquan C. Liu (MIT)
Wednesday, March 31, 2021
Virtual via Bluejeans - 11:00 am
Title: Parallel Algorithms for Graph Computations
Abstract: Parallel algorithms are often used in practice for their concrete speed-ups compared to standard sequential algorithms in today's data processing architecture. Algorithms for problems such as triangle counting and k-core decompositions are used in applications such graph visualization, community detection, and graph clustering algorithms. In this talk, I will discuss several novel parallel algorithms for graph computations (in both the static and dynamic settings) that operate in the work-depth (the standard model for shared-memory multicore systems) and the massively parallel computation (MPC) model (the standard for large-scale multi-machine distributed architectures). I will discuss in detail two specific algorithms. In the static setting, I will discuss a O(log log n)-round MPC algorithm that exactly counts the number of triangles and performs in O(n^{\delta}) (for any constant \delta) space per machine, and total space O(m \alpha) where \alpha is the arboricity of the graph.
In the dynamic, work-depth setting, I will talk about some very recent work on parallel (2+\epsilon)-approximate k-core decompositions, a central subroutine in many different types of applications. All discussed algorithms improve upon the theoretical guarantees of previous work. In addition, we implemented all algorithms under experimental settings and found they exhibit improved performances compared to previous implementations on graphs obtained from the Stanford Large Network Dataset Collection (SNAP). I will conclude with some interesting future work.
----------------------------------
Videos of recent talks are available at: http://arc.gatech.edu/node/121
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
]]>