\label{pg:singlepass}K-Means currently runs in $O(kN)$ time. A procedure called Single Pass K-Means, developed by Farnstrom et al.\cite{singlePassKMeans}, is designed to lessen the runtime. Single Pass K-Means begins as regular K-Means by initializing the clusters to random locations. Next, each instance in the training dataset is processed. Each instance is added to the existing cluster that is closest to it. Once $1\%$ of the data bas been processed, any cluster that has no new instances is removed, and a new cluster is initialized to the furthest data point. The process continues until there is no data left.

Single Pass K-Means has almost the same quality of clusters as regular K-Means, but runs in half the time. Besides the runtime, another main benefit of Single Pass K-Means over regular K-Means is that the data is only observed once, allowing it to run on datasets with a forward only cursor\footnote{A forward only cursor means that an instance can only be observed once, and each instance must be observed in sequence.}.
