I have a set of $N$ objects for which I can calculate the distance between each pair, so I can compute the distance matrix. However, establishing a distance between a pair of objects is not computationally fast. Furthermore, $N$ can be a large number (1000 or more). Because of this, an $O(n^2)$ algorithm is not useful, it is too computationally expensive. I can calculate an approximate threshold that establishes when two objects belong to the same cluster or not.
I implemented the leader algorithm (proposed by Hargitan) and it is fast and provides more or less good results.
Are there some partitional clustering algorithms that run fast but are a bit more robust than the leader one?