Before revision:  We first show that the  k-means+ + algorithm can be efficiently implemented on relational data . In contrast, we show that the adaptive k-means algorithm likely can not be efficiently implemented on relational data, as this would imply P = \#P. However, we show that a slight variation of this adaptive k-means algorithm can be efficiently implemented on relational data, and that this alternative algorithmhas the same performance guarantee as the original algorithm , that is that it outputs an O(1)-approximate sketch .
After revision:  We first show that the k-means+ + algorithm to construct an O(1)-approximate sketch .