A new scalable parallel DBSCAN algorithm using the disjoint-set data structure. Patwary, M. M. A., Palsetia, D., Agrawal, A., Liao, W., Manne, F., & Choudhary, A. In SC '12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, pages 1–11, November, 2012. ISSN: 2167-4337doi abstract bibtex DBSCAN is a well-known density based clustering algorithm capable of discovering arbitrary shaped clusters and eliminating noise data. However, parallelization of DBSCAN is challenging as it exhibits an inherent sequential data access order. Moreover, existing parallel implementations adopt a master-slave strategy which can easily cause an unbalanced workload and hence result in low parallel efficiency. We present a new parallel DBSCAN algorithm (PDSDBSCAN) using graph algorithmic concepts. More specifically, we employ the disjoint-set data structure to break the access sequentiality of DBSCAN. In addition, we use a tree-based bottom-up approach to construct the clusters. This yields a better-balanced workload distribution. We implement the algorithm both for shared and for distributed memory. Using data sets containing up to several hundred million high-dimensional points, we show that PDSDBSCAN significantly outperforms the master-slave approach, achieving speedups up to 25.97 using 40 cores on shared memory architecture, and speedups up to 5,765 using 8,192 cores on distributed memory architecture.
@inproceedings{patwary_new_2012,
title = {A new scalable parallel {DBSCAN} algorithm using the disjoint-set data structure},
doi = {10.1109/SC.2012.9},
abstract = {DBSCAN is a well-known density based clustering algorithm capable of discovering arbitrary shaped clusters and eliminating noise data. However, parallelization of DBSCAN is challenging as it exhibits an inherent sequential data access order. Moreover, existing parallel implementations adopt a master-slave strategy which can easily cause an unbalanced workload and hence result in low parallel efficiency. We present a new parallel DBSCAN algorithm (PDSDBSCAN) using graph algorithmic concepts. More specifically, we employ the disjoint-set data structure to break the access sequentiality of DBSCAN. In addition, we use a tree-based bottom-up approach to construct the clusters. This yields a better-balanced workload distribution. We implement the algorithm both for shared and for distributed memory. Using data sets containing up to several hundred million high-dimensional points, we show that PDSDBSCAN significantly outperforms the master-slave approach, achieving speedups up to 25.97 using 40 cores on shared memory architecture, and speedups up to 5,765 using 8,192 cores on distributed memory architecture.},
booktitle = {{SC} '12: {Proceedings} of the {International} {Conference} on {High} {Performance} {Computing}, {Networking}, {Storage} and {Analysis}},
author = {Patwary, Md. Mostofa Ali and Palsetia, Diana and Agrawal, Ankit and Liao, Wei-keng and Manne, Fredrik and Choudhary, Alok},
month = nov,
year = {2012},
note = {ISSN: 2167-4337},
keywords = {Clustering algorithms, Data structures, Density based clustering, Disjoint-set data structure, Instruction sets, Merging, Noise, Partitioning algorithms, Union-Find algorithm, Vegetation},
pages = {1--11},
}
Downloads: 0
{"_id":"c6QM4FxRsRbFgkSDT","bibbaseid":"patwary-palsetia-agrawal-liao-manne-choudhary-anewscalableparalleldbscanalgorithmusingthedisjointsetdatastructure-2012","author_short":["Patwary, M. M. A.","Palsetia, D.","Agrawal, A.","Liao, W.","Manne, F.","Choudhary, A."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"A new scalable parallel DBSCAN algorithm using the disjoint-set data structure","doi":"10.1109/SC.2012.9","abstract":"DBSCAN is a well-known density based clustering algorithm capable of discovering arbitrary shaped clusters and eliminating noise data. However, parallelization of DBSCAN is challenging as it exhibits an inherent sequential data access order. Moreover, existing parallel implementations adopt a master-slave strategy which can easily cause an unbalanced workload and hence result in low parallel efficiency. We present a new parallel DBSCAN algorithm (PDSDBSCAN) using graph algorithmic concepts. More specifically, we employ the disjoint-set data structure to break the access sequentiality of DBSCAN. In addition, we use a tree-based bottom-up approach to construct the clusters. This yields a better-balanced workload distribution. We implement the algorithm both for shared and for distributed memory. Using data sets containing up to several hundred million high-dimensional points, we show that PDSDBSCAN significantly outperforms the master-slave approach, achieving speedups up to 25.97 using 40 cores on shared memory architecture, and speedups up to 5,765 using 8,192 cores on distributed memory architecture.","booktitle":"SC '12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis","author":[{"propositions":[],"lastnames":["Patwary"],"firstnames":["Md.","Mostofa","Ali"],"suffixes":[]},{"propositions":[],"lastnames":["Palsetia"],"firstnames":["Diana"],"suffixes":[]},{"propositions":[],"lastnames":["Agrawal"],"firstnames":["Ankit"],"suffixes":[]},{"propositions":[],"lastnames":["Liao"],"firstnames":["Wei-keng"],"suffixes":[]},{"propositions":[],"lastnames":["Manne"],"firstnames":["Fredrik"],"suffixes":[]},{"propositions":[],"lastnames":["Choudhary"],"firstnames":["Alok"],"suffixes":[]}],"month":"November","year":"2012","note":"ISSN: 2167-4337","keywords":"Clustering algorithms, Data structures, Density based clustering, Disjoint-set data structure, Instruction sets, Merging, Noise, Partitioning algorithms, Union-Find algorithm, Vegetation","pages":"1–11","bibtex":"@inproceedings{patwary_new_2012,\n\ttitle = {A new scalable parallel {DBSCAN} algorithm using the disjoint-set data structure},\n\tdoi = {10.1109/SC.2012.9},\n\tabstract = {DBSCAN is a well-known density based clustering algorithm capable of discovering arbitrary shaped clusters and eliminating noise data. However, parallelization of DBSCAN is challenging as it exhibits an inherent sequential data access order. Moreover, existing parallel implementations adopt a master-slave strategy which can easily cause an unbalanced workload and hence result in low parallel efficiency. We present a new parallel DBSCAN algorithm (PDSDBSCAN) using graph algorithmic concepts. More specifically, we employ the disjoint-set data structure to break the access sequentiality of DBSCAN. In addition, we use a tree-based bottom-up approach to construct the clusters. This yields a better-balanced workload distribution. We implement the algorithm both for shared and for distributed memory. Using data sets containing up to several hundred million high-dimensional points, we show that PDSDBSCAN significantly outperforms the master-slave approach, achieving speedups up to 25.97 using 40 cores on shared memory architecture, and speedups up to 5,765 using 8,192 cores on distributed memory architecture.},\n\tbooktitle = {{SC} '12: {Proceedings} of the {International} {Conference} on {High} {Performance} {Computing}, {Networking}, {Storage} and {Analysis}},\n\tauthor = {Patwary, Md. Mostofa Ali and Palsetia, Diana and Agrawal, Ankit and Liao, Wei-keng and Manne, Fredrik and Choudhary, Alok},\n\tmonth = nov,\n\tyear = {2012},\n\tnote = {ISSN: 2167-4337},\n\tkeywords = {Clustering algorithms, Data structures, Density based clustering, Disjoint-set data structure, Instruction sets, Merging, Noise, Partitioning algorithms, Union-Find algorithm, Vegetation},\n\tpages = {1--11},\n}\n\n\n\n","author_short":["Patwary, M. M. A.","Palsetia, D.","Agrawal, A.","Liao, W.","Manne, F.","Choudhary, A."],"key":"patwary_new_2012","id":"patwary_new_2012","bibbaseid":"patwary-palsetia-agrawal-liao-manne-choudhary-anewscalableparalleldbscanalgorithmusingthedisjointsetdatastructure-2012","role":"author","urls":{},"keyword":["Clustering algorithms","Data structures","Density based clustering","Disjoint-set data structure","Instruction sets","Merging","Noise","Partitioning algorithms","Union-Find algorithm","Vegetation"],"metadata":{"authorlinks":{}},"html":""},"bibtype":"inproceedings","biburl":"https://bibbase.org/zotero/mh_lenguyen","dataSources":["iwKepCrWBps7ojhDx"],"keywords":["clustering algorithms","data structures","density based clustering","disjoint-set data structure","instruction sets","merging","noise","partitioning algorithms","union-find algorithm","vegetation"],"search_terms":["new","scalable","parallel","dbscan","algorithm","using","disjoint","set","data","structure","patwary","palsetia","agrawal","liao","manne","choudhary"],"title":"A new scalable parallel DBSCAN algorithm using the disjoint-set data structure","year":2012}