ICML 2018oral43 citations
Parallel and Streaming Algorithms for K-Core Decomposition
Hossein Esfandiari, Silvio Lattanzi, Vahab Mirrokni
Abstract
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.
BibTeX
@InProceedings{pmlr-v80-esfandiari18a,
title = {Parallel and Streaming Algorithms for K-Core Decomposition},
author = {Esfandiari, Hossein and Lattanzi, Silvio and Mirrokni, Vahab},
booktitle = {Proceedings of the 35th International Conference on Machine Learning},
pages = {1397--1406},
year = {2018},
editor = {Dy, Jennifer and Krause, Andreas},
volume = {80},
series = {Proceedings of Machine Learning Research},
month = {10--15 Jul},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v80/esfandiari18a/esfandiari18a.pdf},
url = {https://proceedings.mlr.press/v80/esfandiari18a.html},
abstract = {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.}
}