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?

  • $\begingroup$ Why is the distance computation slow? Long vectors? $\endgroup$
    – le_andrew
    May 6, 2015 at 20:17
  • $\begingroup$ I'm not too familiar with the leader algorithm, but in what respect is it not robust? This may help identify better algorithms for you. Also how are these algorithms being implemented? Are you using pre-canned software or writing them yourself? Finally it would be useful to get a reasonable upper bound on the number of observations, and also the dimension of each observation. $\endgroup$ May 6, 2015 at 22:11

1 Answer 1


Have a look at DBSCAN, OPTICS etc.

They work well with index acceleration exactly because you can use an approximation to prune negative matches quickly.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.