2
$\begingroup$

In R, currently to implement wards method for hierarchical clustering, I use the following code - results <- hclust(data, "ward.D2"). However as my data size has increased exponentially, I wanted to implement parallel execution.

Since I found no package, I tried to re-write the hclust method, however most of its code is written in fortan.

Does there exist any way to implement parallel execution here?

$\endgroup$
3
$\begingroup$

The complexity of that algorithm is O(n³), and it needs O(n²) memory.

So if your data grows "exponentially", you better settle for a sampling-based approach!

Seriously: benchmark the run time and memory requirements for 5k, 10k, 20k, 40k, 80k instances. You should be able to observe something between O(n²) (for computing the distance matrix) and O(n³) for the clustering. Then estimate how long this will take (and how much memory you'll need). Even if you are very optimistic, divide this by the number of threads M you can run. A more realistic value will be M/2 if you can run M threads.

When you are really convinced that you'll be okay with the resulting runtime, just implement the algorithm yourself. It is a very simple algorithm. No need to study the Fortran code. But most likely your code will be 2x slower (20x if using pure Python or R) than a well written old Fortran code...

$\endgroup$

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.