Towards Yinyang K-means on GPU
blog.sourced.tech
blog.sourced.tech
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).
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.
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.
http://www.sciencedirect.com/science/article/pii/S1877050913...
https://www.researchgate.net/publication/221614133_Density-b...
My questions to you would be:
1. The main problem with k-means is it's scalability [1]. Could you comment on what k and n g you'd expect your implementation to compute?
2. (kd-, ...) Trees with blacklisting (Pelleg-Moore) are a more efficient algorithmic approach to k-means clustering than k-means++ and consorts (which you are showing in the benchmarks on your blog). Do you know how yinyang fares against a correct Pelleg-Moore implementation of k-means (as the yinyang algorithm's authors did not... :-( )?
[1] http://www.eecs.tufts.edu/~dsculley/papers/fastkmeans.pdf
2. No, unfortunately I don't. Implementing a tree on GPU is a real pain and the performance will still be bad, so I didn't even consider them.
The common problem with advanced approaches is the memory overhead. Hi-end GPU has only 12 GB and you have to fit. E.g. Yinyang becomes unapplicable on 500000 samples, 10000 clusters and 480 dimensions (though only the product of samples and clusters matters much).