Just to add to the previous answer that the streaming algorithm in the cited paper is also known as "Sequential K-means". It doesn't need any iteration over the whole dataset but the results can be substantially different from the well-known K-means.
Moreover, if you don't know (guess) the number of clusters K and are still interested in a streaming algorithm that derives from K-means and that doesn't need to loop over the whole dataset, let me suggest two publications:
J. Hensman, R. Pullin, M. Eaton, K. Worden, K. M. Holford and S. L. Evans, Detecting and identifying artificial acoustic emission signals in an industrial fatigue environment, http://dx.doi.org/10.1088/0957-0233/20/4/045101
E. Pomponi, A. Vinogradov, A real-time approach to acoustic emission clustering, Mech. Syst. Signal Process. (2013), http://dx.doi.org/10.1016/j.ymssp.2013.03.017
The former describes the online radius-based clustering algorithm (ORACAL) and the latter the Adaptive Sequential K-means (ASK) algorithm, two interesting variations of the standard Sequential K-means (i.e. MacQueen 1967)
Disclaimer: I'm the co-author of the second one