Clustering massive data sets in practice If you have a very large data set of $n$ vectors and you want to cluster them according to some metric measure, what is the current state of the art when you can not afford to do more than $\Theta(n)$ work?  I am interested in methods that work well in practice as well as having nice theoretical properties.

A web search brings up "A sublinear time approximation scheme for clustering in metric spaces" by P. Indyk as the most cited paper in the area.
At the risk of sounding immodest, I wrote a short survey on stream clustering a few years ago. It's a little out of date, but not overly so, and doing forward citations will get you to the recent work in the area.