  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 an O(1)-approximate k-means
solution.
