RECORD
Fast tree-based algorithms for DBSCAN for low-dimensional data on GPUs
Distributed, Parallel, and Cluster Computing · Submitted 9 Mar 2021
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | DBSCAN is a well-known density-based clustering algorithm to discover arbitrary shape clusters. | background 1.00 | 0.03 | 0.02 | asserted 1.00 |
| s1 | While conceptually simple in serial, the algorithm is challenging to efficiently parallelize on manycore GPU architectures. | background 0.80 | 0.07 | 0.02 | asserted 1.00 |
| s2 | Common pitfalls, such as asynchronous range query calls, result in high thread execution divergence in many implementations. | background 0.90 | 0.08 | 0.02 | asserted 0.99 |
| s3 | In this paper, we propose a new framework for GPU-accelerated DBSCAN, and describe two tree-based algorithms within that framework. | contribution 1.00 | 0.91 | 0.12 | asserted 0.99 |
| s4 | Both algorithms fuse the search for neighbors with updating cluster information, but differ in their treatment of dense regions of the data. | method 0.77 | 0.77 | 0.10 | asserted 0.99 |
| s5 | We show that the time taken to compute clusters is at most twice that of determination of the neighbors. | result 1.00 | 0.95 | 0.20 | asserted 1.00 |
| s6 | 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. | result 0.54 | 0.94 | 0.36 | asserted 1.00 |
| s7 | We also show that the memory usage can be reduced by processing object neighbors dynamically without storing them. | result 0.50 | 0.94 | 0.10 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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.
Human review
How the literature uses it
1 arXiv paper cite this in 8 sentences
Papers citing it · 5 sentences without a confident label
Uses its method or tool 1 paper
-
We base our RT-DBSCAN algorithm on the parallel Union-Find FDBSCAN algorithm proposed by Prokopenko [ref] .
RT-DBSCAN: Accelerating DBSCAN using Ray Tracing Hardware · RT-DBSCAN · 0.91
Compares with it 1 paper
-
FDBSCAN FDBSCAN uses a parallel DisjointSet algorithm to compute clusters [ref] .
RT-DBSCAN: Accelerating DBSCAN using Ray Tracing Hardware · Performance Evaluation · 0.85
Cites it as support 1 paper
-
In fact, Prokopenko show that performance does not suffer even without hardware acceleration [ref] .
RT-DBSCAN: Accelerating DBSCAN using Ray Tracing Hardware · RT-DBSCAN · 0.96
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.