Good question. A straw man method for say 3 nearest neighbors is to sample Nsample neighbors of each data point, keeping the nearest 3. While trivial, running this for a few values of Nsample will give you some idea of signal / noise ratio, near / background noise, easily plotted for your data. An additional trick is to then check neighbors of neighbors, to see if any of those ar nearer than direct neighbors. Also, if the input data is already well-shuffled, sample in blocks, otherwise cache will thrash.
(Added): see fastcluster
in R and I believe in SciPy v0.11.
For text, see
google-all-pairs-similarity-search.
Repeat, "An appropriate dissimilarity measure is far more important in obtaining success with clustering than choice of clustering algorithm" — choosing-clustering-method.
