h2oai / h2oai/h2o4gpu

Implement GPU based DBSCAN clustering algo

Open
#239 21 comments 1 reaction 1 assignee Claimed by @teju85 View on GitHub
CUDA new algo
Dominant language
C++
Stars
468
Forks
96
PR merge metrics
No merged PRs in 30d

Description

Original serial algo: https://www.aaai.org/Papers/KDD/1996/KDD96-037.pdf
GPU based implementations:
1. CUDA-DClust: http://www.dbs.ifi.lmu.de/Publikationen/Boehm/CIKM_09.pdf. It uses a collision matrix approach to name clusters. also has an index data structure on GPU that helps reduce computational complexity of eps-neighborhood detection.
2. G-DBSCAN: https://pdfs.semanticscholar.org/31df/abb8d1085ac468b60a83d32af2a558407c95.pdf. Simpler implementation. Generates a proximity graph out of the eps-neighborhood info and then performs BFS traversal to name the clusters. Thus exposing more parallelism than the previous approach.
IMHO, I think we should start with an implementation based on G-DBSCAN and the refine the implementation as per performance profile.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.