Clustering stora dataset är ett grundläggande problem med ett antal tillämpningar inom maskininlärning. Data samlas ofta in på olika platser och kluster måste utföras på ett distribuerat sätt med låg kommunikation. Vi vill att kvaliteten på klusterbildningen i den distribuerade miljön ska motsvara den i den centraliserade miljö där alla data finns på en enda plats. I detta arbete studerar vi både graf- och geometriska klusterproblem i två distribuerade modeller: 1) en punkt-till-punkt-modell och 2) en modell med en sändningskanal. Vi ger protokoll i båda modellerna som vi visar är nästan optimala genom att visa nästan matchande kommunikation lägre gränser. Vårt arbete belyser den överraskande kraften i en sändningskanal för klusterproblem; grovt taget, att spektralt kluster n punkter eller n hörn i en graf som distribueras över s servrar, för en värsta fall partitionering kommunikationen komplexitet i en punkt-till-punkt modell är n · s, medan i sändningsmodellen är det n + s. Ett liknande fenomen innehar för den geometriska inställningen också. Vi implementerar våra algoritmer och demonstrerar detta fenomen på verkliga datauppsättningar, vilket visar att våra algoritmer också är mycket effektiva i praktiken.
Tanken på att använda sparifiering för att minska kommunikations komplexiteten för att klusterera en graf i den distribuerade inställningen föreslogs först av REF.
Communication-Optimal Distributed Clustering