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.