# how to implement a hierarchical clustering technique using parallel execution in R

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?

## 1 Answer

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...