Communication-efficient k-means for Edge-based machine learning

Hanlin Lu, Ting He, Shiqiang Wang, Changchang Liu, Mehrdad Mahdavi, Vijaykrishnan Narayanan, Kevin S. Chan, Stephen Pasteris

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


We consider the problem of computing the k-means centers for a large high-dimensional dataset in the context of edge-based machine learning, where data sources offload machine learning computation to nearby edge servers. k-Means computation is fundamental to many data analytics, and the capability of computing provably accurate k-means centers by leveraging the computation power of the edge servers, at a low communication and computation cost to the data sources, will greatly improve the performance of these analytics. We propose to let the data sources send small summaries, generated by joint dimensionality reduction (DR) and cardinality reduction (CR), to support approximate k-means computation at reduced complexity and communication cost. By analyzing the complexity, the communication cost, and the approximation error of k-means algorithms based on state-of-the-art DR/CR methods, we show that: (i) in the single-source case, it is possible to achieve a near-optimal approximation at a near-linear complexity and a constant communication cost, (ii) in the multiple-source case, it is possible to achieve similar performance at a logarithmic communication cost, and (iii) the order of applying DR and CR significantly affects the complexity and the communication cost. Our findings are validated through experiments based on real datasets.

Original languageEnglish (US)
Title of host publicationProceedings - 2020 IEEE 40th International Conference on Distributed Computing Systems, ICDCS 2020
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages11
ISBN (Electronic)9781728170022
StatePublished - Nov 2020
Event40th IEEE International Conference on Distributed Computing Systems, ICDCS 2020 - Singapore, Singapore
Duration: Nov 29 2020Dec 1 2020

Publication series

NameProceedings - International Conference on Distributed Computing Systems


Conference40th IEEE International Conference on Distributed Computing Systems, ICDCS 2020

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Communication-efficient k-means for Edge-based machine learning'. Together they form a unique fingerprint.

Cite this