# \[ANN\] ParallelKMeans v1.0.0 - KMeans In Super Sonic Mode

**URL:** <https://discourse.julialang.org/t/ann-parallelkmeans-v1-0-0-kmeans-in-super-sonic-mode/61786>\
**Category:** Package Announcements\
**Created:** [May 25, 2021, 2:37pm UTC](https://discourse.julialang.org/t/ann-parallelkmeans-v1-0-0-kmeans-in-super-sonic-mode/61786 "2021-05-25T14:37:57Z")\
**Posts on this page:** 17\
**Page:** 1

<div class="post-metadata">

**Author:** ![PyDataBlog](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pydatablog/32/12327_2.png) [@PyDataBlog](https://discourse.julialang.org/u/PyDataBlog)\
**Post date:** [May 25, 2021, 2:37pm UTC](https://discourse.julialang.org/t/ann-parallelkmeans-v1-0-0-kmeans-in-super-sonic-mode/61786/1 "2021-05-25T14:37:57Z")

</div>

Hello everyone.

We are finally ready to announce [ParallelKMeans](https://github.com/PyDataBlog/ParallelKMeans.jl) is finally and stable enough for daily use. Before I go into the details of this package, I would like to apologize to @Skoffer for the little commotion my [initial outburst about this idea](https://discourse.julialang.org/t/i-asked-for-help-optimizing-my-julia-code-now-its-someones-package/34679) caused 1 year ago. In hindsight, I could (and should have) handled it better.

Like the big bang, this package has not only evolved as the fastest KMeans implementation around but also gained me an amazing friendship. Enough about how amazing @Skoffer is!

The main features of this package are:

- Lightening fast implementation of K-Means clustering algorithm even on a single thread in native Julia.
- Support for multi-theading implementation of K-Means clustering algorithm.
- Implementation of classic & contemporary variants of the K-Means algorithm.
- Support for all distance metrics available at [Distances.jl](https://github.com/JuliaStats/Distances.jl)
- Supported interface as an [MLJ](https://github.com/alan-turing-institute/MLJ.jl#available-models) model.

Current benchmark look really promising as this package is lightning fast (_over **76x faster** than Python’s implementation via scikit-learn_) compared to other implementations in other languages.

 ![benchmark_image (1)](https://global.discourse-cdn.com/julialang/original/3X/f/b/fbad8b1aa6f79a8efc5462aefb309e2444a6cd79.png)

There are still many features planned for future releases so feel free to contribute in any form or shape. This community created and pushed this idea beyond my wildest imagination.

**Update** : A minor bug has now been fixed in the plot for YingYang 100k sample

---

<div class="post-metadata">

**Author:** ![Satvik](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/satvik/32/20486_2.png) [@Satvik](https://discourse.julialang.org/u/Satvik)\
**Post date:** [May 25, 2021, 3:13pm UTC](https://discourse.julialang.org/t/ann-parallelkmeans-v1-0-0-kmeans-in-super-sonic-mode/61786/2 "2021-05-25T15:13:15Z")

</div>

This is great timing! I’m just about to do some clustering for a project, so I’ll try this out.

---

<div class="post-metadata">

**Author:** ![PyDataBlog](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pydatablog/32/12327_2.png) [@PyDataBlog](https://discourse.julialang.org/u/PyDataBlog)\
**Post date:** [May 25, 2021, 9:15pm UTC](https://discourse.julialang.org/t/ann-parallelkmeans-v1-0-0-kmeans-in-super-sonic-mode/61786/3 "2021-05-25T21:15:25Z")

</div>

That’s great to hear. Feedback will be greatly appreciated!

---

<div class="post-metadata">

**Author:** ![MirekKratochvil](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mirekkratochvil/32/21851_2.png) [@MirekKratochvil](https://discourse.julialang.org/u/MirekKratochvil)\
**Post date:** [May 25, 2021, 9:53pm UTC](https://discourse.julialang.org/t/ann-parallelkmeans-v1-0-0-kmeans-in-super-sonic-mode/61786/4 "2021-05-25T21:53:06Z")

</div>

Hello! This looks super cool, also the YY implementation is great to have in Julia for sure. Is the code for the benchmark available somewhere? Last year we’ve implemented batch SOMs for huge datasets (which is basically the same as kMeans, sans one small (model) matrix multiplication per iteration), and I’d like to see how we would stand in this comparison. (The package is here: [GitHub - LCSB-BioCore/GigaSOM.jl: Huge-scale, high-performance flow cytometry clustering in Julia](https://github.com/LCSB-BioCore/GigaSOM.jl) )

---

<div class="post-metadata">

**Author:** ![PyDataBlog](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pydatablog/32/12327_2.png) [@PyDataBlog](https://discourse.julialang.org/u/PyDataBlog)\
**Post date:** [May 25, 2021, 10:02pm UTC](https://discourse.julialang.org/t/ann-parallelkmeans-v1-0-0-kmeans-in-super-sonic-mode/61786/5 "2021-05-25T22:02:41Z")

</div>

> [@MirekKratochvil](#):
>
> Is the code for the benchmark available somewhere?

Yes, the benchmarks can be found [here](https://github.com/PyDataBlog/ParallelKMeans.jl/blob/master/extras/ClusteringJL%2C%20Mlpack%2C%20%26%20ParallelKMeans%20Benchmarks%20Final.ipynb)

---

<div class="post-metadata">

**Author:** ![Skoffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/skoffer/32/378_2.png) [@Skoffer](https://discourse.julialang.org/u/Skoffer)\
**Post date:** [May 26, 2021, 6:02am UTC](https://discourse.julialang.org/t/ann-parallelkmeans-v1-0-0-kmeans-in-super-sonic-mode/61786/6 "2021-05-26T06:02:37Z")

</div>

It would be also interesting to compare with the `Coreset` approach (maybe with the internal YingYang algorithm). In my experiments, `Coreset` gave high-quality clusters in a fraction of full Lloyd-like algorithms time.

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [May 26, 2021, 6:22am UTC](https://discourse.julialang.org/t/ann-parallelkmeans-v1-0-0-kmeans-in-super-sonic-mode/61786/7 "2021-05-26T06:22:23Z")

</div>

noticed that R was not in the list of benchmarks.

wonder how it will perform.

---

<div class="post-metadata">

**Author:** ![Skoffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/skoffer/32/378_2.png) [@Skoffer](https://discourse.julialang.org/u/Skoffer)\
**Post date:** [May 26, 2021, 6:29am UTC](https://discourse.julialang.org/t/ann-parallelkmeans-v1-0-0-kmeans-in-super-sonic-mode/61786/8 "2021-05-26T06:29:01Z")

</div>

We used R implementation of [knor](https://cran.r-project.org/web/packages/knor/) which is as far as I know faster than other R implementations of means.

---

<div class="post-metadata">

**Author:** ![PyDataBlog](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pydatablog/32/12327_2.png) [@PyDataBlog](https://discourse.julialang.org/u/PyDataBlog)\
**Post date:** [May 26, 2021, 7:42am UTC](https://discourse.julialang.org/t/ann-parallelkmeans-v1-0-0-kmeans-in-super-sonic-mode/61786/9 "2021-05-26T07:42:17Z")

</div>

> [@xiaodai](#):
>
> noticed that R was not in the list of benchmarks.

Here’s a [table](https://pydatablog.github.io/ParallelKMeans.jl/dev/#Benchmark-Results) of all the benchmark results including the languages.

---

<div class="post-metadata">

**Author:** ![PyDataBlog](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pydatablog/32/12327_2.png) [@PyDataBlog](https://discourse.julialang.org/u/PyDataBlog)\
**Post date:** [May 26, 2021, 8:01am UTC](https://discourse.julialang.org/t/ann-parallelkmeans-v1-0-0-kmeans-in-super-sonic-mode/61786/10 "2021-05-26T08:01:21Z")

</div>

The next set of expanded benchmarks will definitely have this benchmark.

---

<div class="post-metadata">

**Author:** ![MirekKratochvil](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mirekkratochvil/32/21851_2.png) [@MirekKratochvil](https://discourse.julialang.org/u/MirekKratochvil)\
**Post date:** [May 26, 2021, 8:07am UTC](https://discourse.julialang.org/t/ann-parallelkmeans-v1-0-0-kmeans-in-super-sonic-mode/61786/11 "2021-05-26T08:07:29Z")

</div>

Thanks for the link! What is the used dimensionality and the (final) number of clusters? I didn’t find that even from the notebook, and well, the performance varies wildly with that.

(We did something similar for GPUs here [cuda-kmeans/results at master · krulis-martin/cuda-kmeans · GitHub](https://github.com/krulis-martin/cuda-kmeans/tree/master/results) – you can see the performance is basically n_d_k, so not reporting d\*k makes the benchmark much less useful than it could be.)

---

<div class="post-metadata">

**Author:** ![PyDataBlog](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pydatablog/32/12327_2.png) [@PyDataBlog](https://discourse.julialang.org/u/PyDataBlog)\
**Post date:** [May 26, 2021, 8:18am UTC](https://discourse.julialang.org/t/ann-parallelkmeans-v1-0-0-kmeans-in-super-sonic-mode/61786/12 "2021-05-26T08:18:52Z")

</div>

> [@MirekKratochvil](#):
>
> hanks for the link! What is the used dimensionality and the (final) number of clusters?

The data used for this benchmark can be found [here](https://github.com/PyDataBlog/ParallelKMeans.jl/blob/master/extras/Sklearn%20Benchmark-Final.ipynb)

The next iteration of benchmarks will give various dimension levels.

The elbow method was used as practical benchmarking criteria for the ‘_selection of the final number of clusters_’ as this is a common utility that practitioners use for such decisions.

---

<div class="post-metadata">

**Author:** ![cjdoris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cjdoris/32/213133_2.png) [@cjdoris](https://discourse.julialang.org/u/cjdoris)\
**Post date:** [May 26, 2021, 8:41am UTC](https://discourse.julialang.org/t/ann-parallelkmeans-v1-0-0-kmeans-in-super-sonic-mode/61786/13 "2021-05-26T08:41:16Z")

</div>

Very cool!

In your benchmarks, all the algorithms get about 10x slower for a 10x increase in data, which makes sense, except that they each have a point where they get 1000x slower (except Knor which is at the slower level throughout). Do you know why this is? Is it a cache thing?

It looks like your implementations avoid this barrier for longer somehow, can you say why? Though even ignoring the jumps you appear to be about 8x faster anyway.

---

<div class="post-metadata">

**Author:** ![PyDataBlog](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pydatablog/32/12327_2.png) [@PyDataBlog](https://discourse.julialang.org/u/PyDataBlog)\
**Post date:** [May 26, 2021, 9:47am UTC](https://discourse.julialang.org/t/ann-parallelkmeans-v1-0-0-kmeans-in-super-sonic-mode/61786/14 "2021-05-26T09:47:47Z")

</div>

Can you please re-evaluate your observations given the update in the plot now?

---

<div class="post-metadata">

**Author:** ![cjdoris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cjdoris/32/213133_2.png) [@cjdoris](https://discourse.julialang.org/u/cjdoris)\
**Post date:** [May 26, 2021, 1:18pm UTC](https://discourse.julialang.org/t/ann-parallelkmeans-v1-0-0-kmeans-in-super-sonic-mode/61786/15 "2021-05-26T13:18:47Z")

</div>

I don’t understand, my observations are about the plot currently in the readme.

---

<div class="post-metadata">

**Author:** ![PyDataBlog](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pydatablog/32/12327_2.png) [@PyDataBlog](https://discourse.julialang.org/u/PyDataBlog)\
**Post date:** [May 26, 2021, 1:22pm UTC](https://discourse.julialang.org/t/ann-parallelkmeans-v1-0-0-kmeans-in-super-sonic-mode/61786/16 "2021-05-26T13:22:55Z")

</div>

The plot has been updated hence the request for any potential re-evaluation.

---

<div class="post-metadata">

**Author:** ![cjdoris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cjdoris/32/213133_2.png) [@cjdoris](https://discourse.julialang.org/u/cjdoris)\
**Post date:** [May 26, 2021, 7:16pm UTC](https://discourse.julialang.org/t/ann-parallelkmeans-v1-0-0-kmeans-in-super-sonic-mode/61786/17 "2021-05-26T19:16:54Z")

</div>

I don’t see anything different, my observations/questions pertain to this plot: [ParallelKMeans.jl/benchmark\_image.png at e14c139d68e530571b97931105da5bfcecc612b5 · PyDataBlog/ParallelKMeans.jl · GitHub](https://github.com/PyDataBlog/ParallelKMeans.jl/blob/e14c139d68e530571b97931105da5bfcecc612b5/docs/src/benchmark_image.png)