Timezone: »

 
Poster
Massively Parallel Algorithms and Hardness for Single-Linkage Clustering under $\ell_p$ Distances
Grigory Yaroslavtsev · Adithya Vadapalli

Thu Jul 12 09:15 AM -- 12:00 PM (PDT) @ Hall B #157
in Posters Thu »
We present first massively parallel (MPC) algorithms and hardness of approximation results for computing Single-Linkage Clustering of n input d-dimensional vectors under Hamming, $\ell_1, \ell_2$ and $\ell_\infty$ distances. All our algorithms run in O(log n) rounds of MPC for any fixed d and achieve (1+\epsilon)-approximation for all distances (except Hamming for which we show an exact algorithm). We also show constant-factor inapproximability results for o(\log n)-round algorithms under standard MPC hardness assumptions (for sufficiently large dimension depending on the distance used). Efficiency of implementation of our algorithms in Apache Spark is demonstrated through experiments on the largest available vector datasets from the UCI machine learning repository exhibiting speedups of several orders of magnitude.

Author Information

Grigory Yaroslavtsev (Indiana University)

Grigory Yaroslavtsev is the founding director at IU Center for Algorithms and Machine Learning and an assistant professor of Computer Science at Indiana University. Prior to that he was a postdoctoral fellow at the Warren Center for Network and Data Sciences at the University of Pennsylvania. He was previously a Postdoctoral Fellow in Mathematics at Brown University, ICERM. He received his Ph.D. in Theoretical Computer Science in 2014 from Pennsylvania State University and an M.Sc. in Applied Mathematics and Physics from the Academic University of the Russian Academy of Sciences in 2010. Grigory works on efficient algorithms for sparsification, summarization and testing properties of large data, including approximation, parallel and online algorithms, learning theory and property testing, communication and information complexity and private data release.

Adithya Vadapalli (INDIANA UNIVERSITY)

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