Parallel implementation

[AdrianEddy]

Hi,

I've parallelized most of the loops used in the algorithm using rayon here: AdrianEddy@cda5e3e

Ideally this could be merged, but in my opinion it should be an optional feature, and this complicates things a bit to make the code clean for both the single-threaded path and the multi-threaded one, especially with the generic and the Send + Sync bounds

Unfortunately I don't have a capacity right now to work on a proper PR with the feature flag handled, and I also didn't ran extensive tests to verify everything, so I'm just leaving this here to let people know that a faster version is possible

Please feel free to take that code and implement in this repo in whatever form you seem fit.

Thanks for the great implementation!

[tom-whitehead]

Hey @AdrianEddy,

Thanks for raising this PR. I've looked at doing this in the past, but in the end gave up as a) the majority of the computation time is in running the condense_tree method, which cannot be easily done in parallel and b) as you mention, having this behind a feature is complex to implement.

That said, on larger datasets there could definitely be some benefit to having some parallel computations. If I can make time I will try to work on separating multi-threaded and single-threaded paths, maybe starting with core distances.

Thanks again!

[AdrianEddy]

To give you a perspective, on a dataset of 42548 512-element vectors, the single-threaded version runs in 1442 s but the parallelized in 172 s
So yeah, definitely an improvement worth the effort :)

[tom-whitehead]

Ah right, in my benchmarking I used much lower dimension vectors. On an aside, that is a lot of dimensions for HDBSCAN to deal with and probably won't yield the best results anyway due to the curse of dimensionality - the vector space will be sparsely populated, which is a challenge for a density based algorithm. Reducing dimensionality first with UMAP/PCA will give much better results.

Still, I'm sure there are people who want to cluster in higher dimensions, so as mentioned will try to carve out some time for this!

[tom-whitehead]

Hey @AdrianEddy , I've raised a first PR fora parallel implementation behind a feature flag. I've decided to have a separate method cluster_par (in line with rust's principle that features should be additive).

Currently, this only parallel-ises core distance calculations (and with some code duplication!), but I will work my way through the remaining in the future.

Unit tests are passing fine, but I will do some more local testing before merging.