What's an algorithm for $k$-means clustering, in particular an online algorithm (you can stream new points to it), such that once the size of the set of clusters $k$ becomes large, we can still efficiently lookup a point $p$ and classify it into a cluster ID (an integer)?

Obviously standard $k$-means alone is not sufficient. Would putting the centroids of each cluster into a BSP or $k'$D-tree do the trick? I used $k'$ there because that $k'$ has nothing to do with $k$.


1 Answer 1


Instead of the classical $k$-means algorithm where you

  • classify all points and then
  • update the center of each cluster to be the average of all points of that cluster,

you could use the sequential variant of $k$-means:

centers = random(k)
while True:
    p = next_point(points)
    c = find_center(centers, p)
    c = c + a * (p - c)

next_point iterates all the points and maybe prefers new points (online) for example by using deque and putting new points front.

find_center classifies a point. This takes $O(k)$ naive and $O(\log k)$ using a spacial datastructure like a k-d tree.

$a \in [0,1]$ says how much a center moves in the direction of the given point. Usually this is time dependent and gets lower with time, i.e. $a(t) = \lambda_1 e^{-\lambda_2 t}$. Maybe one could boost the weight of new points though.

  • 1
    $\begingroup$ What is c = c + a * (p - c) doing? What is a? Also, why do you think that find_center can be done in $O(\log k)$ time? I don't think that's true -- the running time depends on the dimension, and if the number of dimensions is large, it might be slow. $\endgroup$
    – D.W.
    Jan 20, 2018 at 0:02
  • $\begingroup$ Explained a in answer, thanks. Runtime: k-d trees and similar datastructures can find the nearest neighbor independently of the dimension because they build a search tree where each node halfes the search space along any dimension. But you are right, I did not think too hard about updating the position of a center in the tree. Wikipedia says it's O(log k) where k is the number of points in the tree, not the dimension. But you may have to rebuild the tree from time to time to balance it. $\endgroup$
    – Hannes
    Jan 20, 2018 at 9:15
  • $\begingroup$ I know Wikipedia says it is $O(\log k)$, but Wikipedia leaves out something very important: the dependence on the dimension. In fact, the dependence on the dimension appears to be exponential in the number of dimensions, so the running time is more akin to $O((\log k)^d)$ where $d$ is the number of dimensions. Empirically, my experience is that once $d$ starts getting large, k-d trees aren't much faster than naive linear search through all the points. $\endgroup$
    – D.W.
    Jan 20, 2018 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.