Data Science & AI Lecture Series
Dynamic Graph Sketching: To Infinity And Beyond
David Tench
Dynamic Graph Sketching: To Infinity And Beyond
| When | Wednesday, September 13, 2023, 10:30 AM – 11:45 AM (MT) |
|---|---|
| Where | FASB 295 |
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 explore what is needed to make graph sketching algorithms practically useful, and as a case study present a sketching algorithm for connected components and a corresponding high-performance implementation. Finally, I will give an overview of the many open problems in this area, focusing on improving query performance of graph sketching algorithms.
Speaker
David Tench
Berkeley Lab
David is the 2023 Grace Hopper Postdoctoral Fellow at Lawrence Berkeley Lab and his research focuses on compact, dynamic, and memory-hierarchy-aware algorithms for large-scale data science. Prior to that, he was a CRA Computing Innovation Postdoctoral Fellow working with Martin Farach-Colton at Rutgers University. He earned his PhD at UMass Amherst working with Andrew McGregor.
Tags: algorithms & theory networks & graphs
Part of the Data Science & AI Lecture Series. Something wrong on this page? Edit _data/talks/2023-09-13-david-tench.toml.