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.

For text, see
[google-all-pairs-similarity-search](http://code.google.com/p/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](http://stats.stackexchange.com/questions/3713/choosing-clustering-method).