Dynamic Graph Connectivity: To Infinity And Beyond

Speaker: David Tench , Rutgers University

Date: Wednesday, September 14, 2022

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: https://mit.zoom.us/meeting/register/tJMtdOqgrTwsGNV_k0Nk6JjLMk-G6GFzTRyk

Event Type: Seminar

Room Description: https://mit.zoom.us/meeting/register/tJMtdOqgrTwsGNV_k0Nk6JjLMk-G6GFzTRyk

Host: Julian Shun, MIT CSAIL

Contact: Linda Lynch, lindalynch@csail.mit.edu

Relevant URL: http://fast-code.csail.mit.edu/

Speaker URL: https://www.davidtench.com/

Speaker Photo:
None

Reminders to: fast-code-seminar@lists.csail.mit.edu, seminars@csail.mit.edu, pl@csail.mit.edu, commit@lists.csail.mit.edu

Reminder Subject: TALK: Dynamic Graph Connectivity: To Infinity And Beyond

******************IMPORTANT NOTE ABOUT REGISTRATION******************
- The registration link for Fall 2022 is the same as the link from Spring 2022.
- Please save the Zoom link that you receive after you register. This link will stay the same for all subsequent Fast Code seminars.
- Zoom does not recognize a second registration, and will not send out the link a second time. The organizers will not be notified of any second registration.
- If you have any problems with registration, please contact lindalynch@csail.mit.edu by 3pm on the day of the seminar, so that we can try to resolve it before the seminar begins.
*********************************************************************

Abstract: Existing graph stream processing systems must store the graph explicitly in RAM which limits the scale of graphs they can process. The graph semi-streaming literature offers algorithms which avoid this limitation via linear sketching data structures that use small (sublinear) space, but these algorithms have not seen use in practice to date. In this talk I will present GraphZeppelin, a streaming graph system for computing the connected components of a dynamically changing graph. I will show how GraphZeppelin uses linear sketching to efficiently process graphs too large to store explicitly in RAM, and why existing linear sketching algorithms for this and other graph problems fall short in practice. Finally, I will discuss what these results mean for the semi-streaming model and what is required for linear sketching algorithms to be practical.

Bio: David Tench is an NSF Computing Innovation Postdoctoral Fellow at Rutgers University.

Research Areas:
Algorithms & Theory, Systems & Networking

Impact Areas:
Big Data

This event is not part of a series.

Created by Julian J. Shun at Tuesday, September 06, 2022 at 5:21 AM.