Dynamic Graph Sketching: To Infinity And Beyond

A Google TechTalk, presented by David Tench, 2023-04-06 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 potential applications for truly massive-scale graph computation. About the Speaker: David is a CRA Computing Innovation Postdoctoral Fellow working with Martin Farach-Colton at Rutgers University and will soon join Lawrence Berkeley National Labs as the 2023 Grace Hopper Postdoctoral Fellow. He earned his PhD at UMass Amherst working with Andrew McGregor. A Google Talk Series on Algorithms, Theory, and Optimization