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.

• THere's also lots of work on sampling and streaming-based methods. These tend to work best when the metric is the Euclidean distance (or relatives). I'm not sure what your situation is. – Suresh Venkat Mar 7 '13 at 12:49
• @SureshVenkat Weighted Euclidean distance works for me. I can find lists of papers, what I am not clear on is which are considered the current state of the art from an algorithms/practice point of view. – Majid Mar 7 '13 at 13:04