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