2026-07-21T14:16:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14166 2024-03-12T11:59:59Z ddc:004 open_access

Relational Algorithms for k-Means Clustering Moseley, Benjamin Pruhs, Kirk Samadian, Alireza Wang, Yuyan k-means clustering approximation big-data databases This paper gives a k-means approximation algorithm that is efficient in the relational algorithms model. This is an algorithm that operates directly on a relational database without performing a join to convert it to a matrix whose rows represent the data points. The running time is potentially exponentially smaller than N, the number of data points to be clustered that the relational database represents. Few relational algorithms are known and this paper offers techniques for designing relational algorithms as well as characterizing their limitations. We show that given two data points as cluster centers, if we cluster points according to their closest centers, it is NP-Hard to approximate the number of points in the clusters on a general relational input. This is trivial for conventional data inputs and this result exemplifies that standard algorithmic techniques may not be directly applied when designing an efficient relational algorithm. This paper then introduces a new method that leverages rejection sampling and the k-means++ algorithm to construct a O(1)-approximate k-means solution. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Moseley and Kirk Pruhs and Alireza Samadian and Yuyan Wang 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.97 urn:nbn:de:0030-drops-141668 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.97 eng https://creativecommons.org/licenses/by/4.0/legalcode