k-means clustering with efficient point lookup? 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$.
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.