BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Colloquium: Provably Efficient and Scalable Shared-Memory Graph
  Processing
DTSTART:20210329T160000
DTEND:20210329T170000
DTSTAMP:20260508T135611Z
UID:557a58a2a528f349f5f79781b5148fa03b650d570a4576d6af3342a6
CATEGORIES:Conferences - Seminars
DESCRIPTION:By: Laxman Dhulipala - MIT\nIC Faculty candidate\n\nAbstract\n
 Graph processing is a fundamental tool in many computational disciplines d
 ue to the widespread availability of graph data. However\, processing larg
 e graphs quickly and cost-effectively is a major challenge\, and existing 
 approaches capable of processing very large graphs often have high computa
 tional cost\, only solve a limited set of problems\, and possess poor theo
 retical guarantees. Similarly\, existing approaches for dynamic or streami
 ng graphs often employ ad-hoc algorithms with unknown theoretical costs an
 d suboptimal performance. This talk will show how shared-memory algorithms
  can serve as the foundation for a graph processing toolkit for static and
  evolving graphs that is cost-effective\, has strong theoretical guarantee
 s\, and achieves state-of-the-art performance.\n\nIn the first part of thi
 s talk\, I will describe a shared-memory approach for static graph process
 ing. I will describe a rich interface for parallel graph processing which 
 extends the Ligra interface with provably-efficient primitives. This inter
 face enables simple and provably-efficient shared-memory implementations o
 f over 20 fundamental graph problems. The implementations\, which are publ
 icly available as part of the Graph Based Benchmark Suite\, solve these\np
 roblems on the largest publicly available graph\, the WebDataCommons hyper
 link graph\, with over 200 billion edges\, in a matter of seconds to minut
 es using a commodity multicore machine. Compared to existing large-scale g
 raph processing results\, our results apply to a much broader set of probl
 ems\, use orders of magnitude fewer resources\, and in many cases run an o
 rder of magnitude faster.\n\nIn the second part of this talk\, I will desc
 ribe a provably-efficient approach for streaming graph processing. I will 
 describe a new compressed purely-functional tree data structure\, called a
  $C$-tree\, which admits efficient parallel batch updates and enables a dy
 namic graph representation based on nested trees. Using this representatio
 n\, I will describe a serializable graph-streaming system called Aspen tha
 t can concurrently apply updates and queries. Compared to existing work\, 
 Aspen achieves orders of magnitude higher update rates\, while using less 
 memory. Aspen scales to the largest publicly available graphs\, and can co
 ncurrently update and analyze the WebDataCommons hyperlink graph on a sing
 le commodity multicore machine with a terabyte of memory.\n\nBio\nLaxman i
 s a Postdoctoral Researcher at MIT CSAIL where he works with Prof. Julian 
 Shun. He recently received his Ph.D. from Carnegie Mellon University\, whe
 re he was advised by Prof. Guy Blelloch. He works on high-performance para
 llel algorithms and systems for static\, dynamic\, and streaming graphs\, 
 with a focus on both practical and theoretical efficiency. His work on gra
 ph processing has been recognized by a Best Paper Award at SPAA'18 and the
  Distinguished Paper Award at PLDI'19.\n\nMore information
LOCATION:https://epfl.zoom.us/j/82644409927?pwd=K1gwWStkNmxYSGEwdVNrelAvak
 pZdz09
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR