- By:
- Prokopenko, Andrey V; Lebrun-Grandie, Damien T; Arndt, Daniel
- Page Number:
- 503-512
- Book Title:
- Proceedings of the 52nd International Conference on Parallel Processing
- Publication Date:
- November 9, 2023
- Publisher Location:
- Association for Computing Machinery, 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:
- Various
- View DOI Listing:
- https://doi.org/10.1145/3605573.3605594
Abstract
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.
