{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,1]],"date-time":"2025-04-01T17:40:33Z","timestamp":1743529233714,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642311246"},{"type":"electronic","value":"9783642311253"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31125-3_6","type":"book-chapter","created":{"date-parts":[[2012,6,18]],"date-time":"2012-06-18T09:24:23Z","timestamp":1340011463000},"page":"71-86","source":"Crossref","is-referenced-by-count":9,"title":["kNN-Bor\u016fvka-GPU: A Fast and Scalable MST Construction from kNN Graphs on GPU"],"prefix":"10.1007","author":[{"given":"Ahmed Shamsul","family":"Arefin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carlos","family":"Riveros","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Regina","family":"Berretta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pablo","family":"Moscato","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_CR1","unstructured":"NVIDIA CUDA - Programming Guide (2007), http:\/\/developer.nvidia.com\/"},{"key":"6_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1007\/3-540-68530-8_28","volume-title":"Algorithms - ESA \u201998","author":"J. Abello","year":"1998","unstructured":"Abello, J., Buchsbaum, A.L., Westbrook, J.: A Functional Approach to External Graph Algorithms. In: Bilardi, G., Pietracaprina, A., Italiano, G.F., Pucci, G. (eds.) ESA 1998. LNCS, vol.\u00a01461, pp. 332\u2013343. Springer, Heidelberg (1998)"},{"key":"6_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/978-3-642-24669-2_36","volume-title":"Algorithms and Architectures for Parallel Processing","author":"A.S. Arefin","year":"2011","unstructured":"Arefin, A.S., Inostroza-Ponta, M., Mathieson, L., Berretta, R., Moscato, P.: Clustering Nodes in Large-Scale Biological Networks Using External Memory Algorithms. In: Xiang, Y., Cuzzocrea, A., Hobbs, M., Zhou, W. (eds.) ICA3PP 2011, Part II. LNCS, vol.\u00a07017, pp. 375\u2013386. Springer, Heidelberg (2011)"},{"key":"6_CR4","unstructured":"Arefin, A.S., Riveros, C., Berretta, R., Moscato, P.: Gpu-fs-knn: A fast and scalable knn computation technique using gpu. Faculty Postgrad Research Poster, The University of Newcastle, Australia (September 2011), http:\/\/www.newcastle.edu.au\/Resources\/Faculties\/Faculty%20of%20Engineering%20and%20Built%20Environment\/Research\/Arefin.pdf"},{"key":"6_CR5","first-page":"1366","volume":"66","author":"D.A. Bader","year":"2006","unstructured":"Bader, D.A., Cong, G.: Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs. J. P. Dist. Comp.\u00a066, 1366\u20131378 (2006)","journal-title":"J. P. Dist. Comp."},{"key":"6_CR6","unstructured":"Bader, D.A., Madduri, K.: GTgraph: A suite of synthetic graph generators (2006)"},{"issue":"1","key":"6_CR7","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0167-8191(89)90005-7","volume":"12","author":"R.S. Barr","year":"1989","unstructured":"Barr, R.S., Helgaon, R.V., Kennington, J.L.: Minimal spanning trees: an empirical investigation of parallel algorithms. Parallel Computing\u00a012(1), 45\u201352 (1989)","journal-title":"Parallel Computing"},{"key":"6_CR8","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1109\/TC.1978.1675043","volume":"27","author":"J.L. Bentley","year":"1978","unstructured":"Bentley, J.L., Friedman, J.H.: Fast algorithms for constructing minimal spanning trees in coordinate spaces. IEEE Trans. Comput.\u00a027, 97\u2013105 (1978)","journal-title":"IEEE Trans. Comput."},{"key":"6_CR9","unstructured":"Boruvka, O.: O Jist\u00e9m Probl\u00e9mu Minim\u00e1ln\u00edm (About a Certain Minimal Problem) (in Czech, German summary). Pr\u00e1ce Mor. Pr\u00edrodoved. Spol. v Brne III 3 (1926)"},{"key":"6_CR10","unstructured":"Chung, S., Condon, A.: Parallel implementation of borvka\u2019s minimum spanning tree algorithm. In: Proceedings of the 10th International Parallel Processing Symposium, IPPS 1996, pp. 302\u2013308 (1996)"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Dehne, F., G\u00f6tz, S.: Practical parallel algorithms for minimum spanning trees. In: Symposium on Reliable Distributed Systems, pp. 366\u2013371 (1998)","DOI":"10.1109\/RELDIS.1998.740525"},{"key":"6_CR12","unstructured":"Demetrescu, C., Goldberg, A., Johnson, D.: 9th DIMACS implementation challenge - shortest paths (2006), http:\/\/www.dis.uniroma1.it\/~challenge9\/"},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Dyen, I., Kruskal, J.B., Black, P.: An indoeuropean classification: A lexicostatistical experiment. Trans. of the American Phil. Soc.\u00a082(5), iii\u2013iv, 1\u2013132","DOI":"10.2307\/1006517"},{"key":"6_CR14","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1109\/MAHC.1985.10011","volume":"7","author":"R.L. Graham","year":"1985","unstructured":"Graham, R.L., Hell, P.: On the history of the minimum spanning tree problem. IEEE Ann. Hist. Comput.\u00a07, 43\u201357 (1985)","journal-title":"IEEE Ann. Hist. Comput."},{"key":"6_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/978-3-540-77220-0_21","volume-title":"High Performance Computing \u2013 HiPC 2007","author":"P. Harish","year":"2007","unstructured":"Harish, P., Narayanan, P.J.: Accelerating Large Graph Algorithms on the GPU Using CUDA. In: Aluru, S., Parashar, M., Badrinath, R., Prasanna, V.K. (eds.) HiPC 2007. LNCS, vol.\u00a04873, pp. 197\u2013208. Springer, Heidelberg (2007)"},{"key":"6_CR16","unstructured":"Harris, M.: Optimizing parallel reduction in cuda. NVIDIA Developer Tech. (2008)"},{"key":"6_CR17","unstructured":"Hoberock, J., Bell, N.: Thrust - a productivity-oriented library for cuda. Template library, Version 1.4 (2010), http:\/\/code.google.com\/p\/thrust\/"},{"key":"6_CR18","unstructured":"Inostroza-Ponta, M.: An Integrated and Scalable Approach Based on Combinatorial Optimization Techniques for the Analysis of Microarray Data. Ph.D. thesis, School of Electrical Engineering and Computer Science, The University of Newcastle, Australia (2008)"},{"key":"6_CR19","doi-asserted-by":"crossref","unstructured":"Johnson, D.B., Metaxas, P.: A parallel algorithm for computing minimum spanning trees. In: Proceedings of the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1992, pp. 363\u2013372 (1992)","DOI":"10.1145\/140901.141917"},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"Kang, S., Bader, D.A.: An efficient transactional memory algorithm for computing minimum spanning forest of sparse graphs. In: Proc. of the 14th ACM SIGPLAN Symp., Principles and Practice of Parallel Programming, PPoPP, pp. 15\u201324 (2009)","DOI":"10.1145\/1504176.1504182"},{"key":"6_CR21","doi-asserted-by":"crossref","unstructured":"Moret, B.M.E., Shapiro, H.D.: An empirical assessment of algorithms for constructing a minimum spanning tree. DIMACS Monographs (1994)","DOI":"10.1090\/dimacs\/015\/09"},{"issue":"4","key":"6_CR22","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1093\/comjnl\/26.4.354","volume":"26","author":"F. Murtagh","year":"1983","unstructured":"Murtagh, F.: A survey of recent advances in hierarchical clustering algorithms. Comput. J.\u00a026(4), 354\u2013359 (1983)","journal-title":"Comput. J."},{"issue":"1-3","key":"6_CR23","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0012-365X(00)00224-7","volume":"233","author":"J. Nesetril","year":"2001","unstructured":"Nesetril, J., Milkov, E., Nesetrilov, H.: Otakar boruvka on minimum spanning tree problem translation of both the 1926 papers, comments, history. Discrete Mathematics\u00a0233(1-3), 3\u201336 (2001)","journal-title":"Discrete Mathematics"},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"Nobari, S.H., Bressan, S., Rassi, C.: A data parallel minimum spanning tree algorithm for most graphics processing units. In: Proc. of the Int. Con. ADPC (2010)","DOI":"10.5176\/978-981-08-7656-2_A-29"},{"key":"6_CR25","unstructured":"Rostrup, S., Srivastava, S., Singhal, K.: Fast and memory-efficient minimum spanning tree on the gpu (2011)"},{"key":"6_CR26","unstructured":"Siek, J., Lee, L.Q., Lumsdaine, A.: Boost random number library (June 2000), http:\/\/www.boost.org\/libs\/graph\/"},{"key":"6_CR27","doi-asserted-by":"publisher","first-page":"1381","DOI":"10.1016\/j.jpdc.2008.05.012","volume":"68","author":"E. Sintorn","year":"2008","unstructured":"Sintorn, E., Assarsson, U.: Fast parallel gpu-sorting using a hybrid algorithm. J. Parallel Distrib. Comput.\u00a068, 1381\u20131388 (2008)","journal-title":"J. Parallel Distrib. Comput."},{"key":"6_CR28","unstructured":"Tepper, M., Mejail, M., Mus\u00e9, P., Almansa, A.: Boruvka Meets Nearest Neighbors (2011), http:\/\/hal.archives-ouvertes.fr\/docs\/00\/58\/31\/20\/PDF\/preprint.pdf"},{"issue":"25","key":"6_CR29","doi-asserted-by":"publisher","first-page":"1999","DOI":"10.1056\/NEJMoa021967","volume":"347","author":"M.J. Vijver van de","year":"2002","unstructured":"van de Vijver, M.J., He, Y.D., et al.: A gene-expression signature as a predictor of survival in breast cancer. The New England JM\u00a0347(25), 1999\u20132009 (2002)","journal-title":"The New England JM"},{"key":"6_CR30","doi-asserted-by":"crossref","unstructured":"Vineet, V., Harish, P., Patidar, S., Narayanan, P.J.: Fast minimum spanning tree for large graphs on the gpu. In: Proc. of Conf. on HPG, pp. 167\u2013171. ACM (2009)","DOI":"10.1145\/1572769.1572796"}],"container-title":["Lecture Notes in Computer Science","Computational Science and Its Applications \u2013 ICCSA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31125-3_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,1]],"date-time":"2025-04-01T17:02:28Z","timestamp":1743526948000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31125-3_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642311246","9783642311253"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31125-3_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}