Faculty Recruiting Support CICS

Massive Graph Analysis in the Data Stream Model

18 Mar
Monday, 03/18/2019 12:00pm to 2:00pm
CS 140
PhD Thesis Defense


Graphs have become the abstraction of choice in modeling highly-structured data. The need to compute graph-theoretic properties of datasets arises in all applications that involve entities and pairwise relations between them. However, in practice the datasets in question can be too large to be stored in main memory, distributed across many machines, or changing over time. Moreover, in the increasing number of applications the algorithm has to make real time decisions as the data arrives, which puts further limitations on the time and space that can realistically be used. These characteristics render classical algorithmic approaches obsolete and necessitate the development of new techniques. The streaming model of computation takes these challenges into account, providing a trade-off between the resources used by the algorithm and its accuracy. A graph stream is defined by a sequence of edge insertions (and sometimes deletions) into an initially empty graph, with the objective of computing a certain property of the graph at the end of the stream. In this model, we explore fundamental graph-theoretic problems that also serve as important primitives in massive graph analysis: counting the number of triangles, computing matchings, vertex cover, and others.

Advisor: Andrew McGregor