Skip to main content

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

by Andrey V Prokopenko, Damien T Lebrun-grandie, Daniel Arndt
Publication Type
Conference Paper
Book Title
Proceedings of the 52nd International Conference on Parallel Processing
Publication Date
Page Numbers
503 to 512
Publisher Location
New York, New York, United States of America
Conference Name
52nd International Conference on Parallel Processing (ICPP 2023)
Conference Location
Salt Lake City, Utah, United States of America
Conference Sponsor
Conference Date

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