Counting triangles and the curse of the last reducer

By Siddharth Suri, Sergei Vassilvitskii. The Web Conference, 2011

455 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/f089c8c603bb4d35b874f769a73036bac54d6f53

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

Asynchronous Distributed ADMM for Consensus Optimization (2014, background): “In particular, it is shown that when the proposed asynchronous 1This problem (sometimes called “the curse of the last reducer” (Suri & Vassilvitskii, 2011)) is also widely known in MapReduce, which requires a similar full synchronization in its reduce step. algorithm reduces to a synchronous one,…”
Distributed GraphLab: A Framework for Machine Learning in the Cloud (2012, background): “niformly partitioned. For example, natural graphs encountered in real-world applications have power-law degree distributions which can lead to highly skewed running times even with a random partition [36]. Furthermore, the actual work required for each vertex could depend on the data in a problem sp”
Handbook of Big Data (2016, unknown): “The mechanism for selecting reference variables is by ﬁrst selecting them with highlight strips (Section 6.4.5), and then hitting • R to turn the strip variables into reference variables.”
PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs (2012, unknown): “2 we provide comparisons of the PowerGraph sys-tem with published results on similar data for PageRank, Triangle Counting [36], and collapsed Gibbs sampling for the LDA model [34].”
GraphChi: Large-Scale Graph Computation on Just a PC (2012, unknown): “GraphChi counts the triangles of the twitter2010 graph in less then 90 minutes, while a Hadoop-based algorithm uses over 1,600 workers to solve the same problem in over 400 minutes [43].”
Truss Decomposition in Massive Networks (2012, methodology): “Note that the complexity, both time and space, of Algorithm 2 in the worst case is the same as the lower-bound complexity for triangle listing [30].”
Wedge sampling for computing clustering coefficients and triangle counts on large graphs † (2013, methodology): “Recent work by Cohen [16] and Suri and Vassilvitskii [17] give MapReduce implementations of these algorithms.”
Distributed large-scale natural graph factorization (2013, background): “More specifically, uneven load distribution can lead to considerable inefficiencies in the bulk synchronous setting [24].”
Distributed GraphLab: A Framework for Machine Learning in the Cloud (2012, background): “For example, natural graphs encountered in real-world applications have power-law degree distributions which can lead to highly skewed running times even with a random partition [36].”
Mining of Massive Datasets (2011, methodology): “PIG [15] is an implementation of relational algebra on top of Hadoop.”
NOMAD: Nonlocking, stOchastic Multi-machine algorithm for Asynchronous and Decentralized matrix completion (2013, background): “The second issue is that they suﬀer from what is widely known as the the curse of last reducer [4, 24].”