Theoretically-Efficient and Practical Parallel DBSCAN
© 2020 Association for Computing Machinery. The DBSCAN method for spatial clustering has received significant attention due to its applicability in a variety of data analysis tasks. There are fast sequential algorithms for DBSCAN in Euclidean space that take O(nłog n) work for two dimensions, sub-qu...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
ACM
2021
|
| Online Access: | https://hdl.handle.net/1721.1/136631 |
| _version_ | 1811077464136351744 |
|---|---|
| author | Wang, Yiqiu Gu, Yan Shun, Julian |
| author_facet | Wang, Yiqiu Gu, Yan Shun, Julian |
| author_sort | Wang, Yiqiu |
| collection | MIT |
| description | © 2020 Association for Computing Machinery. The DBSCAN method for spatial clustering has received significant attention due to its applicability in a variety of data analysis tasks. There are fast sequential algorithms for DBSCAN in Euclidean space that take O(nłog n) work for two dimensions, sub-quadratic work for three or more dimensions, and can be computed approximately in linear work for any constant number of dimensions. However, existing parallel DBSCAN algorithms require quadratic work in the worst case. This paper bridges the gap between theory and practice of parallel DBSCAN by presenting new parallel algorithms for Euclidean exact DBSCAN and approximate DBSCAN that match the work bounds of their sequential counterparts, and are highly parallel (polylogarithmic depth). We present implementations of our algorithms along with optimizations that improve their practical performance. We perform a comprehensive experimental evaluation of our algorithms on a variety of datasets and parameter settings. Our experiments on a 36-core machine with two-way hyper-threading show that our implementations outperform existing parallel implementations by up to several orders of magnitude, and achieve speedups of up to 33x over the best sequential algorithms. |
| first_indexed | 2024-09-23T10:43:26Z |
| format | Article |
| id | mit-1721.1/136631 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:43:26Z |
| publishDate | 2021 |
| publisher | ACM |
| record_format | dspace |
| spelling | mit-1721.1/1366312022-09-30T22:33:05Z Theoretically-Efficient and Practical Parallel DBSCAN Wang, Yiqiu Gu, Yan Shun, Julian © 2020 Association for Computing Machinery. The DBSCAN method for spatial clustering has received significant attention due to its applicability in a variety of data analysis tasks. There are fast sequential algorithms for DBSCAN in Euclidean space that take O(nłog n) work for two dimensions, sub-quadratic work for three or more dimensions, and can be computed approximately in linear work for any constant number of dimensions. However, existing parallel DBSCAN algorithms require quadratic work in the worst case. This paper bridges the gap between theory and practice of parallel DBSCAN by presenting new parallel algorithms for Euclidean exact DBSCAN and approximate DBSCAN that match the work bounds of their sequential counterparts, and are highly parallel (polylogarithmic depth). We present implementations of our algorithms along with optimizations that improve their practical performance. We perform a comprehensive experimental evaluation of our algorithms on a variety of datasets and parameter settings. Our experiments on a 36-core machine with two-way hyper-threading show that our implementations outperform existing parallel implementations by up to several orders of magnitude, and achieve speedups of up to 33x over the best sequential algorithms. 2021-10-27T20:36:21Z 2021-10-27T20:36:21Z 2020 2021-04-02T13:53:05Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/136631 en 10.1145/3318464.3380582 Proceedings of the ACM SIGMOD International Conference on Management of Data Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf ACM arXiv |
| spellingShingle | Wang, Yiqiu Gu, Yan Shun, Julian Theoretically-Efficient and Practical Parallel DBSCAN |
| title | Theoretically-Efficient and Practical Parallel DBSCAN |
| title_full | Theoretically-Efficient and Practical Parallel DBSCAN |
| title_fullStr | Theoretically-Efficient and Practical Parallel DBSCAN |
| title_full_unstemmed | Theoretically-Efficient and Practical Parallel DBSCAN |
| title_short | Theoretically-Efficient and Practical Parallel DBSCAN |
| title_sort | theoretically efficient and practical parallel dbscan |
| url | https://hdl.handle.net/1721.1/136631 |
| work_keys_str_mv | AT wangyiqiu theoreticallyefficientandpracticalparalleldbscan AT guyan theoreticallyefficientandpracticalparalleldbscan AT shunjulian theoreticallyefficientandpracticalparalleldbscan |