{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T14:32:39Z","timestamp":1787236359116,"version":"build-2736575974"},"reference-count":33,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2019,3,7]],"date-time":"2019-03-07T00:00:00Z","timestamp":1551916800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["EXC 310\/2"],"award-info":[{"award-number":["EXC 310\/2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Clustering is an important task in data mining that has become more challenging due to the ever-increasing size of available datasets. To cope with these big data scenarios, a high-performance clustering approach is required. Sparse grid clustering is a density-based clustering method that uses a sparse grid density estimation as its central building block. The underlying density estimation approach enables the detection of clusters with non-convex shapes and without a predetermined number of clusters. In this work, we introduce a new distributed and performance-portable variant of the sparse grid clustering algorithm that is suited for big data settings. Our computed kernels were implemented in OpenCL to enable portability across a wide range of architectures. For distributed environments, we added a manager\u2013worker scheme that was implemented using MPI. In experiments on two supercomputers, Piz Daint and Hazel Hen, with up to 100 million data points in a ten-dimensional dataset, we show the performance and scalability of our approach. The dataset with 100 million data points was clustered in 1198   s    using 128 nodes of Piz Daint. This translates to an overall performance of 352    TFLOPS   . On the node-level, we provide results for two GPUs, Nvidia\u2019s Tesla P100 and the AMD FirePro W8100, and one processor-based platform that uses Intel Xeon E5-2680v3 processors. In these experiments, we achieved between 43% and 66% of the peak performance across all computed kernels and devices, demonstrating the performance portability of our approach.<\/jats:p>","DOI":"10.3390\/a12030060","type":"journal-article","created":{"date-parts":[[2019,3,8]],"date-time":"2019-03-08T04:58:35Z","timestamp":1552021115000},"page":"60","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Heterogeneous Distributed Big Data Clustering on Sparse Grids"],"prefix":"10.3390","volume":"12","author":[{"given":"David","family":"Pfander","sequence":"first","affiliation":[{"name":"Department of Simulation Software Engineering, University of Stuttgart, 70569 Stuttgart, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gregor","family":"Dai\u00df","sequence":"additional","affiliation":[{"name":"Department of Simulation Software Engineering, University of Stuttgart, 70569 Stuttgart, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dirk","family":"Pfl\u00fcger","sequence":"additional","affiliation":[{"name":"Department of Simulation Software Engineering, University of Stuttgart, 70569 Stuttgart, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2019,3,7]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning, Springer. [2nd ed.].","DOI":"10.1007\/978-0-387-84858-7"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"881","DOI":"10.1109\/TPAMI.2002.1017616","article-title":"An Efficient k-Means Clustering Algorithm: Analysis and Implementation","volume":"24","author":"Kanungo","year":"2002","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_3","unstructured":"Arthur, D., and Vassilvitskii, S. (2007, January 7\u20139). K-means++: The Advantages of Careful Seeding. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, USA."},{"key":"ref_4","unstructured":"Ester, M., Kriegel, H.P., Sander, J., and Xu, X. (1996, January 2\u20134). A Density-based Algorithm for Discovering Clusters a Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, Portland, OR, USA."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Song, H., and Lee, J.G. (2018, January 10\u201315). RP-DBSCAN: A Superfast Parallel DBSCAN Algorithm Based on Random Partitioning. Proceedings of the 2018 International Conference on Management of Data, Houston, TX, USA.","DOI":"10.1145\/3183713.3196887"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Gan, J., and Tao, Y. (June, January 31). DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation. Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Australia.","DOI":"10.1145\/2723372.2737792"},{"key":"ref_7","unstructured":"Hinneburg, A., and Gabriel, H.H. (2007, January 6\u20138). DENCLUE 2.0: Fast Clustering Based on Kernel Density Estimation. Proceedings of the 7th International Conference on Intelligent Data Analysis, Ljubljana, Slovenia."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","article-title":"A tutorial on spectral clustering","volume":"17","year":"2007","journal-title":"Stat. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0003-2670(94)00085-9","article-title":"Classification of multicomponent analytical data of olive oils using different neural networks","volume":"292","author":"Zupan","year":"1994","journal-title":"Anal. Chim. Acta"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1145\/568574.568575","article-title":"Why So Many Clustering Algorithms: A Position Paper","volume":"4","year":"2002","journal-title":"SIGKDD Explor. Newsl."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/s11227-006-8294-1","article-title":"Hierarchical parallel processing of large scale data clustering on a PC cluster with GPU co-processing","volume":"36","author":"Takizawa","year":"2006","journal-title":"J. Supercomput."},{"key":"ref_12","unstructured":"Fang, W., Lau, K.K., Lu, M., Xiao, X., Lam, C.K., Yang, P.Y., He, B., Luo, Q., Sander, P.V., and Yang, K. (2008). Parallel Data Mining on Graphics Processors, Hong Kong University of Science and Technology. Technical Report HKUST-CS08-07."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"942","DOI":"10.1007\/s11227-011-0672-7","article-title":"Parallel data mining techniques on Graphics Processing Unit with Compute Unified Device Architecture (CUDA)","volume":"64","author":"Jian","year":"2013","journal-title":"J. Supercomput."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Bhimani, J., Leeser, M., and Mi, N. (2015, January 15\u201317). Accelerating K-Means Clustering with Parallel Implementations and GPU Computing. Proceedings of the 2015 IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA.","DOI":"10.1109\/HPEC.2015.7322467"},{"key":"ref_15","unstructured":"Farivar, R., Rebolledo, D., Chan, E., and Campbell, R.H. (2008, January 14\u201317). A Parallel Implementation of K-Means Clustering on GPUs. Proceedings of the 2008 International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA 2008, Las Vegas, NV, USA."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"B\u00f6hm, C., Noll, R., Plant, C., and Wackersreuther, B. (2009, January 2\u20136). Density-based Clustering Using Graphics Processors. Proceedings of the 18th ACM Conference on Information and Knowledge Management, Hong Kong, China.","DOI":"10.1145\/1645953.1646038"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1016\/j.procs.2013.05.200","article-title":"G-DBSCAN: A GPU Accelerated Algorithm for Density-based Clustering","volume":"18","author":"Andrade","year":"2013","journal-title":"Procedia Comput. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"622","DOI":"10.14778\/2180912.2180915","article-title":"Scalable K-Means++","volume":"5","author":"Bahmani","year":"2012","journal-title":"Proc. VLDB Endow."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/s11704-013-3158-3","article-title":"MR-DBSCAN: A scalable MapReduce-based DBSCAN algorithm for heavily skewed data","volume":"8","author":"He","year":"2014","journal-title":"Front. Comput. Sci."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Bellman, R. (1961). Adaptive Control Processes: A Guided Tour, Princeton University Press. Rand Corporation. Research Studies.","DOI":"10.1515\/9781400874668"},{"key":"ref_21","first-page":"131","article-title":"Clustering Based on Density Estimation with Sparse Grids","volume":"Volume 7526","author":"Glimm","year":"2012","journal-title":"KI 2012: Advances in Artificial Intelligence"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Pfl\u00fcger, D. (2010). Spatially Adaptive Sparse Grids for High-Dimensional Problems, Verlag Dr.Hut.","DOI":"10.1016\/j.jco.2010.04.001"},{"key":"ref_23","unstructured":"Garcke, J. (2004). Maschinelles Lernen Durch Funktionsrekonstruktion Mit Verallgemeinerten D\u00fcnnen Gittern. [Ph.D. Thesis, Universit\u00e4t Bonn, Institut f\u00fcr Numerische Simulation]."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/s10766-012-0202-0","article-title":"Emerging Architectures Enable to Boost Massively Parallel Data Mining Using Adaptive Sparse Grids","volume":"41","author":"Heinecke","year":"2012","journal-title":"Int. J. Parallel Program."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"2145","DOI":"10.1002\/cpe.3514","article-title":"Data Mining on Vast Datasets as a Cluster System Benchmark","volume":"28","author":"Heinecke","year":"2015","journal-title":"Concurr. Comput. Pract. Exp."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Garcke, J., and Pfl\u00fcger, D. (2016). A new Subspace-Based Algorithm for Efficient Spatially Adaptive Sparse Grid Regression, Classification and Multi-evaluation. Sparse Grids and Applications\u2014Stuttgart 2014, Springer.","DOI":"10.1007\/978-3-319-28262-6"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1017\/S0962492904000182","article-title":"Sparse Grids","volume":"13","author":"Bungartz","year":"2004","journal-title":"Acta Numer."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"712","DOI":"10.21914\/anziamj.v42i0.2232","article-title":"Finite Element Thin Plate Splines In Density Estimation","volume":"42","author":"Hegland","year":"2000","journal-title":"ANZIAM J."},{"key":"ref_29","unstructured":"Fog, A. (2018). Instruction Tables, Technical University of Denmark. Technical Report."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Peherstorfer, B., Pfl\u00fcger, D., and Bungartz, H.J. (2014, January 24\u201326). Density Estimation with Adaptive Sparse Grids for Large Data Sets. Proceedings of the 2014 SIAM International Conference on Data Mining, Philadelphia, PA, USA.","DOI":"10.1137\/1.9781611973440.51"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Franzelin, F., and Pfl\u00fcger, D. (2016). From Data to Uncertainty: An Efficient Integrated Data-Driven Sparse Grid Approach to Propagate Uncertainty, Springer.","DOI":"10.1007\/978-3-319-28262-6_2"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Datar, M., Immorlica, N., Indyk, P., and Mirrokni, V.S. (2004, January 9\u201311). Locality-Sensitive Hashing Scheme Based on P-stable Distributions. Proceedings of the Twentieth Annual Symposium on Computational Geometry, Brooklyn, NY, USA.","DOI":"10.1145\/997817.997857"},{"key":"ref_33","unstructured":"(2019, January 14). SG++: General Sparse Grid Toolbox. Available online: https:\/\/github.com\/SGpp\/SGpp."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/3\/60\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:36:55Z","timestamp":1760186215000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/3\/60"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,7]]},"references-count":33,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2019,3]]}},"alternative-id":["a12030060"],"URL":"https:\/\/doi.org\/10.3390\/a12030060","relation":{"has-preprint":[{"id-type":"doi","id":"10.20944\/preprints201902.0019.v1","asserted-by":"object"}]},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,7]]}}}