Fast tree-based algorithms for DBSCAN on GPUs

DBSCAN is a well-known density-based clustering algorithm to discover clusters of arbitrary shape. The efforts to parallelize the algorithm on GPUs often suffer from high thread execution divergence (for example, due to asynchronous calls to range queries). In this paper, we propose a new general framework for DBSCAN on GPUs, and propose two tree-based algorithms within that framework. Both algorithms fuse neighbor search with updating clustering information, and differ in their treatment of dense regions of the data. We show that the cost of computing clusters is at most twice the cost of neighbor determination in parallel. We compare the proposed algorithms with existing GPU implementations, and demonstrate their competitiveness and excellent performance in the presence of a fast traversal structure (bounding volume hierarchy). In addition, we show that the memory usage can be reduced by processing the neighbors of an object on the fly without storing them.