Near-Optimal Clustering in the k-machine model

Sayan Bandyapadhyay; Tanmay Inamdar; Shreyas Pai; Sriram Pemmaraju

doi:10.1145/3154273.3154317

Back

Conference proceeding

Near-Optimal Clustering in the k-machine model

Sayan Bandyapadhyay, Tanmay Inamdar, Shreyas Pai and Sriram Pemmaraju

Proceedings of the 19th International Conference on distributed computing and networking, pp.1-10

ICDCN '18

01/04/2018

DOI: 10.1145/3154273.3154317

View Online

Abstract

The clustering problem, in its many variants, has numerous applications in operations research and computer science (e.g., in applications in bioinformatics, image processing, social network analysis, etc.). As sizes of data sets have grown rapidly, researchers have focused on designing algorithms for clustering problems in models of computation suited for large-scale computation such as MapReduce, Pregel, and streaming models. The k-machine model (Klauck et al., SODA 2015) is a simple, message-passing model for large-scale distributed graph processing. This paper considers three of the most prominent examples of clustering problems: the uncapacitated facility location problem, the p-median problem, and the p-center problem and presents O (1)-factor approximation algorithms for these problems running in Õ (n/k) rounds in the k -machine model. These algorithms are optimal upto polylogarithmic factors because this paper also shows Ω (n/k) lower bounds for obtaining poly(n)-factor approximation algorithms for these problems. These are the first results for clustering problems in the k -machine model. We assume that the metric provided as input for these clustering problems in only implicitly provided, as an edge-weighted graph and in a nutshell, our main technical contribution is to show that constant-factor approximation algorithms for all three clustering problems can be obtained by learning only a small portion of the input metric.

Clustering

distributed clustering

Facility location

k -center

k -machine model

k -median

large-scale clustering

Details

Title: Subtitle: Near-Optimal Clustering in the k-machine model
Creators: Sayan Bandyapadhyay - University of Iowa
Tanmay Inamdar - University of Iowa
Shreyas Pai - University of Iowa
Sriram Pemmaraju - University of Iowa
Resource Type: Conference proceeding
Publication Details: Proceedings of the 19th International Conference on distributed computing and networking, pp.1-10
Publisher: ACM
Series: ICDCN '18
DOI: 10.1145/3154273.3154317
Language: English
Date published: 01/04/2018
Academic Unit: Computer Science
Record Identifier: 9984259425802771

Metrics

4 Record Views

7 Times Cited - Web of Science