1: Initialize f = 1=(k(1 + log n)) and an empty set K
2: while some portion of the stream remains unread do
3: while jKj   = (k log n) and some portion of the stream is unread do
4: Read the next point x from the stream
5: Measure  = miny2K d(x; y)
2
6: if probability =f event occurs then
7: set K   K
S
fxg
8: else
9: assign x to its closest facility in K
10: if stream not exhausted then
11: while jKj >  do
12: Set f   f
13: Move each x 2 K to the center-of-mass of its points
14: Let wx be the number of points assigned to x 2 K
15: Initialize K^
containing the first facility from K
16: for each x 2 K do
17: Measure  = min
y2K^ d(x; y)
2
18: if probability wx=f event occurs then
19: set K^   K^
S
fxg
20: else
21: assign x to its closest facility in K^
22: Set K   K^
23: else
24: Run batch k-means algorithm on weighted points K
25: Perform ball k-means (as per [9]) on the resulting set of cluster