dm.cs.tu-dortmund.de/en/mlbits/cluster-kmeans-acceleration/
Accelerating k-means Clustering – Lecture Notes
pairwise distances of the \(k\) centers for avoiding computations.
Needs additional memory: \(n\cdot (k+1) + \binom {k}{2}\)
Hamerly [ Hame10 ] simplified this to a single lower bound \(l(i)\) for each point [...] \(u(i)=d(x_i,\mu _{a(i)})\) , and only if the condition still holds, also compute the distances to the \(k-1\) other centers, and update the cluster assignment \(a(i)\) , \(u(i)\) and \(l(i)\) .
Additional pruning …
