Oral
Parallel and Streaming Algorithms for K-Core Decomposition
Hossein Esfandiari · Silvio Lattanzi · Vahab Mirrokni

Thu Jul 12th 01:50 -- 02:10 PM @ K11

The k-core decomposition is a fundamental primitive in many machine learning and data mining applications. We present the first distributed and the first streaming algorithms to compute and maintain an approximate k-core decomposition with provable guarantees. Our algorithms achieve rigorous bounds on space complexity while bounding the number of passes or number of rounds of computation. We do so by presenting a new powerful sketching technique for k-core decomposition, and then by showing it can be computed efficiently in both streaming and MapReduce models. Finally, we confirm the effectiveness of our sketching technique empirically on a number of publicly available graphs.

Author Information

Hossein Esfandiari (Harvard University)
Silvio Lattanzi (Google Zurich)
Vahab Mirrokni (Google Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors