Fast tree-based algorithms for DBSCAN for low-dimensional data on GPUs

DBSCAN is a well-known density-based clustering algorithm to discover\narbitrary shape clusters. While conceptually simple in serial, the algorithm is\nchallenging to efficiently parallelize on manycore GPU architectures. Common\npitfalls, such as asynchronous range query calls, result in high thread\nexecution divergence in many implementations. In this paper, we propose a new\nframework for GPU-accelerated DBSCAN, and describe two tree-based algorithms\nwithin that framework. Both algorithms fuse the search for neighbors with\nupdating cluster information, but differ in their treatment of dense regions of\nthe data. We show that the time taken to compute clusters is at most twice that\nof determination of the neighbors. We compare the proposed algorithms with\nexisting CPU and GPU implementations, and demonstrate their competitiveness and\nperformance using a fast traversal structure (bounding volume hierarchy) for\nlow dimensional data. We also show that the memory usage can be reduced by\nprocessing object neighbors dynamically without storing them.\n