Detta papper ger nya algoritmer för distribuerad klusterbildning för två populära center-baserade mål, k-median och k-medel. Dessa algoritmer har påvisbara garantier och förbättrar kommunikationens komplexitet jämfört med befintliga metoder. Efter en klassisk strategi i kluster av [16], vi minskar problemet med att hitta en kluster med låga kostnader till problemet att hitta en kärna av liten storlek. Vi tillhandahåller en distribuerad metod för att bygga en global coreset som förbättrar över de tidigare metoderna genom att minska kommunikations komplexiteten, och som fungerar över allmänna kommunikationstopologier. Experimentella resultat på storskaliga datauppsättningar visar att detta tillvägagångssätt överträffar andra kärnuppsättningsbaserade distribuerade klusteralgoritmer.
Balcan m.fl. visade en coreset konstruktion för k-median och k-medel, vilket leder till en kluster algoritm med Õ (mkd) kommunikation, och också studerat mer allmänna graf topologier för distribuerad dator REF.
Distributed k-Means and k-Median Clustering on General Topologies
{'venue': 'NIPS 2013', 'journal': 'arXiv: Learning', 'mag_field_of_study': ['Computer Science', 'Mathematics']}