  k-means is one of the most influential and utilized machine learning
algorithms. Its computation limits the performance and scalability of many
statistical analysis and machine learning tasks. We rethink and optimize
k-means in terms of modern NUMA architectures to develop a novel
parallelization scheme that delays and minimizes synchronization barriers. The
\textit{k-means NUMA Optimized Routine} (\textsf{knor}) library has (i)
in-memory (\textsf{knori}), (ii) distributed memory (\textsf{knord}), and (iii)
semi-external memory (\textsf{knors}) modules that radically improve the
performance of k-means for varying memory and hardware budgets. \textsf{knori}
boosts performance for single machine datasets by an order of magnitude or
more. \textsf{knors} improves the scalability of k-means on a memory budget
using SSDs. \textsf{knors} scales to billions of points on a single machine,
using a fraction of the resources that distributed in-memory systems require.
\textsf{knord} retains \textsf{knori}'s performance characteristics, while
scaling in-memory through distributed computation in the cloud. \textsf{knor}
modifies Elkan's triangle inequality pruning algorithm such that we utilize it
on billion-point datasets without the significant memory overhead of the
original algorithm. We demonstrate \textsf{knor} outperforms distributed
commercial products like H$_2$O, Turi (formerly Dato, GraphLab) and Spark's
MLlib by more than an order of magnitude for datasets of $10^7$ to $10^9$
points.
