Are there algorithms for clustering objects with pairwise distances, without computing all pairwise distances? I'm looking for a clustering algorithm that clusters objects, by using their pairwise distances, without needing to calculate all pairwise distances.

Normally pairwise clustering is done like this: (see here)


Compute full distance matrix between all pairwise combination of objects
Assuming that the distances there are non-euclidean, one might use Spectral Clustering or Affinity propagation on the distance matrix and retrieve the clustering results.


Here comes the however: 

Computing the full distance matrix for all pairwise combination of objects is computationally very expensive. So my though was, whether there are some clustering algorithms that only do lookups on a subset of the pairwise distances, so it is not necessary to compute the full matrix?

I know Spectral Clustering works also on sparse matrices, but since it is theoretically possible to compute all pairwise distances, which ones should be left out?

Exited to hear your ideas, thanks!
Well, one may argue that DBSCAN is based on all pairwise distances, but it uses data indexing to avoid computing all of them using geometric bounds.

And there are other examples if you browse through literature.

For example, the classic CLARA method is an approximation to PAM that avoids computing all pairwise distances.

And there are many more such techniques.