1
$\begingroup$

I implemented a hierarchical linkage algorithm for a set of 5,000 points. Each point is defined with a longitude and a latitude.

I read about this algorithm here.

These are the steps:

  1. Compute distance matrix between all points (great-circle distance, not Euclidean)
  2. Find the pair of points with the minimum distance between them
  3. If the minimum distance is larger than a threshold value
    • the algorithm finishes
  4. Otherwise
    • The two points are merged, and removed from the list of points.
    • The center point of this pair is added to the list of points
  5. Go back to 1

I do not consider single, complete, etc. types of linkage, since the points are substituted by a central point. Therefore, the distance is just the distance between all points (instead of point-cluster).

It runs okay for small amount of pairs, but it takes 1 second per iteration as soon as I run it for 5,000 points; potentially 83 minutes although it probably stops halfway due to the distance threshold.

Although I use Haversine formulation in the calculation of distances, it does not change much if I use a simple Euclidean approach; it then takes 1 second for 3 iterations.

Am I making a mistake in understanding and implementing this algorithm? If not, are there ways in which this could be sped up?

I am using MATLAB R2018b.

Thank you!

$\endgroup$
1
  • 1
    $\begingroup$ (In the article, I don't find 5. go to step 1: filling the distance matrix from scratch.) $\endgroup$
    – greybeard
    Feb 10, 2021 at 14:36

1 Answer 1

1
$\begingroup$

Yes. After you merge two points, you can update the distances of just the affected nodes, without having to recompute all pairs of distances again. That will be vastly faster.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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