Towards Yinyang K-means on GPU

#1

Post by tanoku » Wed, Jul 27, 2016, 4:07 PM UTC

Towards Yinyang K-means on GPU
blog.sourced.tech

Re: Towards Yinyang K-means on GPU

#2

Post by nl » Thu, Jul 28, 2016, 9:38 AM UTC

This is pretty interesting. Is the author here? I have something to point them at. @nlothian on Twitter, or email in my profile.

Re: Towards Yinyang K-means on GPU

#3

Post by vmarkovtsev » Thu, Jul 28, 2016, 9:44 AM UTC

nl wrote: post #2

This is pretty interesting. Is the author here? I have something to point them at. @nlothian on Twitter, or email in my profile.

Here. Please don't bite :)

Re: Towards Yinyang K-means on GPU

#4

Post by nl » Thu, Jul 28, 2016, 9:56 AM UTC

vmarkovtsev wrote: post #3

nl wrote: post #2

This is pretty interesting. Is the author here? I have something to point them at. @nlothian on Twitter, or email in my profile.

Here. Please don't bite :)

I'm pretty impressed!

Do you know about IBM's Spark+GPU Hackathon?[1] There are some pretty substantial prizes (I thought they were offering cash, but I'm not seeing it now).

[1] http://openpower.devpost.com/details/spark_rally

Re: Towards Yinyang K-means on GPU

#5

Post by vmarkovtsev » Thu, Jul 28, 2016, 10:06 AM UTC

nl wrote: post #4

vmarkovtsev wrote: post #3

Earlier quoted context omitted.

Here. Please don't bite :)

I'm pretty impressed! Do you know about IBM's Spark+GPU Hackathon?[1] There are some pretty substantial prizes (I thought they were offering cash, but I'm not seeing it now). [1] http://openpower.devpost.com/details/spark_rally

This is an exciting opportunity, thanks, we will study it.

Re: Towards Yinyang K-means on GPU

#6

Post by fnord123 » Thu, Jul 28, 2016, 2:48 PM UTC

vmarkovtsev wrote: post #3

nl wrote: post #2

This is pretty interesting. Is the author here? I have something to point them at. @nlothian on Twitter, or email in my profile.

Here. Please don't bite :)

Do you have any interest in implementing other clustering algorithms on GPU? e.g. HDBSCAN? Or is it not as parallelizable?

Re: Towards Yinyang K-means on GPU

#7

Post by cs702 » Thu, Jul 28, 2016, 2:55 PM UTC

fnord123 wrote: post #6

vmarkovtsev wrote: post #3

Earlier quoted context omitted.

Here. Please don't bite :)

Do you have any interest in implementing other clustering algorithms on GPU? e.g. HDBSCAN? Or is it not as parallelizable?

Agree on HDBSCAN/DBSCAN, which is able to find the number of clusters in a large class of problems (unlike K-means, which requires that the number of clusters/centroids be provided as a hyperparameter, or found via some kind of search).

Otherwise, I just want to say to vmarkovtsev: thank you for this -- I will add it to my arsenal of tools, and may others will surely do so as well.

Re: Towards Yinyang K-means on GPU

#8

Post by vmarkovtsev » Thu, Jul 28, 2016, 4:08 PM UTC

cs702 wrote: post #7

fnord123 wrote: post #6

Earlier quoted context omitted.

Do you have any interest in implementing other clustering algorithms on GPU? e.g. HDBSCAN? Or is it not as parallelizable?

Agree on HDBSCAN/DBSCAN, which is able to find the number of clusters in a large class of problems (unlike K-means, which requires that the number of clusters/centroids be provided as a hyperparameter, or found via some kind of search). Otherwise, I just want to say to vmarkovtsev: thank you for this -- I will add it to my arsenal of tools, and may others will surely do so as well.

Thanks. Actually, I like DBSCAN a lot and use it often, though I am not much familiar with it's internals. It looks like it is iterative and thus does not fit very well to a GPU. The only way I see is to pick several seed points at start...

Re: Towards Yinyang K-means on GPU

#9

Post by cs702 » Thu, Jul 28, 2016, 6:28 PM UTC

vmarkovtsev wrote: post #8

cs702 wrote: post #7

Earlier quoted context omitted.

Agree on HDBSCAN/DBSCAN, which is able to find the number of clusters in a large class of problems (unlike K-means, which requires that the number of clusters/centroids be provided as a hyperparameter, or found via some kind of search). Otherwise, I just want to say to vmarkovtsev: thank you for this -- I will add it to my arsenal of tools, and may others will surely do so as well.

Thanks. Actually, I like DBSCAN a lot and use it often, though I am not much familiar with it's internals. It looks like it is iterative and thus does not fit very well to a GPU. The only way I see is to pick several seed points at start...

A Google search reveals this paper: https://arxiv.org/abs/1506.02226

This paper claims a "97x improvement" over traditional (non-parallelized) DBSCAN algorithms, but that's not a very helpful claim, because it does not indicate what the computational costs are as a function of, say, the number of data points or dimensions.

Re: Towards Yinyang K-means on GPU

#10

Post by vmarkovtsev » Thu, Jul 28, 2016, 6:51 PM UTC

cs702 wrote: post #9

vmarkovtsev wrote: post #8

Earlier quoted context omitted.

Thanks. Actually, I like DBSCAN a lot and use it often, though I am not much familiar with it's internals. It looks like it is iterative and thus does not fit very well to a GPU. The only way I see is to pick several seed points at start...

A Google search reveals this paper: https://arxiv.org/abs/1506.02226 This paper claims a "97x improvement" over traditional (non-parallelized) DBSCAN algorithms, but that's not a very helpful claim, because it does not indicate what the computational costs are as a function of, say, the number of data points or dimensions.

97x improvement is actually very suspicious. Thanks for the article!