  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.
