{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T18:24:49Z","timestamp":1767983089304,"version":"3.49.0"},"publisher-location":"Cham","reference-count":49,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319250861","type":"print"},{"value":"9783319250878","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-25087-8_25","type":"book-chapter","created":{"date-parts":[[2015,10,6]],"date-time":"2015-10-06T18:11:35Z","timestamp":1444155095000},"page":"259-270","source":"Crossref","is-referenced-by-count":28,"title":["Brute-Force k-Nearest Neighbors Search on the GPU"],"prefix":"10.1007","author":[{"given":"Shengren","family":"Li","sequence":"first","affiliation":[]},{"given":"Nina","family":"Amenta","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,10,17]]},"reference":[{"key":"25_CR1","unstructured":"cuknns: GPU accelerated k-nearest neighbor library (2012). http:\/\/autogpu.ee.auth.gr\/doku.php?id=cuknns:gpu_accelerated_k-nearest_neighbor_library"},{"key":"25_CR2","unstructured":"kNN CUDA (2013). http:\/\/vincentfpgarcia.github.io\/kNN-CUDA\/"},{"key":"25_CR3","unstructured":"Modern GPU (2013). http:\/\/nvlabs.github.io\/moderngpu\/"},{"key":"25_CR4","unstructured":"cuBLAS in CUDA toolkit 6.5. (2014). https:\/\/developer.nvidia.com\/cuBLAS"},{"key":"25_CR5","unstructured":"CUDA toolkit 6.5. (2014). https:\/\/developer.nvidia.com\/cuda-toolkit-65"},{"key":"25_CR6","unstructured":"MAGMA 1.6.1. (2015). http:\/\/icl.cs.utk.edu\/magma\/"},{"key":"25_CR7","unstructured":"Thrust (2015). https:\/\/developer.nvidia.com\/Thrust"},{"issue":"3","key":"25_CR8","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1080\/00031305.1992.10475879","volume":"46","author":"NS Altman","year":"1992","unstructured":"Altman, N.S.: An introduction to kernel and nearest-neighbor nonparametric regression. The American Statistician 46(3), 175\u2013185 (1992)","journal-title":"The American Statistician"},{"issue":"8","key":"25_CR9","doi-asserted-by":"publisher","first-page":"e44000","DOI":"10.1371\/journal.pone.0044000","volume":"7","author":"AS Arefin","year":"2012","unstructured":"Arefin, A.S., Riveros, C., Berretta, R., Moscato, P.: GPU-FS- $$k$$ NN: A software tool for fast and scalable $$k$$ NN computation using GPUs. PLOS ONE 7(8), e44000 (2012)","journal-title":"PLOS ONE"},{"key":"25_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1007\/978-3-642-23400-2_35","volume-title":"Euro-Par 2011 Parallel Processing","author":"RJ Barrientos","year":"2011","unstructured":"Barrientos, R.J., G\u00f3mez, J.I., Tenllado, C., Matias, M.P., Marin, M.: kNN query processing in metric spaces using GPUs. In: Jeannot, E., Namyst, R., Roman, J. (eds.) Euro-Par 2011, Part I. LNCS, vol. 6852, pp. 380\u2013392. Springer, Heidelberg (2011)"},{"issue":"5","key":"25_CR11","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/s00607-011-0183-7","volume":"94","author":"G Beliakov","year":"2012","unstructured":"Beliakov, G., Johnstone, M., Nahavandi, S.: Computing of high breakdown regression estimators without sorting on graphics processing units. Computing 94(5), 433\u2013447 (2012)","journal-title":"Computing"},{"issue":"10","key":"25_CR12","doi-asserted-by":"publisher","first-page":"1296","DOI":"10.1016\/j.patrec.2012.02.016","volume":"33","author":"G Beliakov","year":"2012","unstructured":"Beliakov, G., Li, G.: Improving the speed and stability of the k-nearest neighbors method. Pattern Recognition Letters 33(10), 1296\u20131301 (2012)","journal-title":"Pattern Recognition Letters"},{"issue":"4","key":"25_CR13","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1109\/34.993558","volume":"24","author":"S Belongie","year":"2002","unstructured":"Belongie, S., Malik, J., Puzicha, J.: Shape matching and object recognition using shape contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence 24(4), 509\u2013522 (2002)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"25_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/3-540-49257-7_15","volume-title":"Database Theory - ICDT 1999","author":"K Beyer","year":"1998","unstructured":"Beyer, K., Goldstein, J., Ramakrishnan, R., Shaft, U.: When is nearest neighbor meaningful? In: Beeri, C., Bruneman, P. (eds.) ICDT 1999. LNCS, vol. 1540, pp. 217\u2013235. Springer, Heidelberg (1998)"},{"key":"25_CR15","doi-asserted-by":"crossref","unstructured":"Boiman, O., Shechtman, E., Irani, M.: In defense of nearest-neighbor based image classification. In: IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2008, pp. 1\u20138. IEEE, June 2008","DOI":"10.1109\/CVPR.2008.4587598"},{"key":"25_CR16","doi-asserted-by":"crossref","unstructured":"Cayton, L.: Accelerating nearest neighbor search on manycore systems. In: 2012 IEEE 26th International Parallel and Distributed Processing Symposium, pp. 402\u2013413. IEEE, May 2012","DOI":"10.1109\/IPDPS.2012.45"},{"issue":"1","key":"25_CR17","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1109\/TIT.1967.1053964","volume":"13","author":"TM Cover","year":"1967","unstructured":"Cover, T.M., Hart, P.E.: Nearest neighbor pattern classification. IEEE Transactions on Information Theory 13(1), 21\u201327 (1967)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"9","key":"25_CR18","doi-asserted-by":"publisher","first-page":"e74113","DOI":"10.1371\/journal.pone.0074113","volume":"8","author":"A Dashti","year":"2013","unstructured":"Dashti, A., Komarov, I., D\u2019Souza, R.M.: Efficient computation of k-nearest neighbour graphs for large high-dimensional data sets on GPU clusters. PLOS ONE 8(9), e74113 (2013)","journal-title":"PLOS ONE"},{"key":"25_CR19","doi-asserted-by":"crossref","unstructured":"Datar, M., Immorlica, N., Indyk, P., Mirrokni, V.S.: Locality-sensitive hashing scheme based on p-stable distributions. In: Proceedings of the Twentieth Annual Symposium on Computational Geometry, SCG 2004, pp. 253\u2013262. ACM (2004)","DOI":"10.1145\/997817.997857"},{"key":"25_CR20","doi-asserted-by":"crossref","unstructured":"Diehl, P., Schweitzer, M.A.: Efficient neighbor search for particle methods on GPUs. In: Meshfree Methods for Partial Differential Equations VII, Lecture Notes in Computational Science and Engineering, vol. 100, pp. 81\u201395. Springer (2015)","DOI":"10.1007\/978-3-319-06898-5_5"},{"issue":"9","key":"25_CR21","doi-asserted-by":"publisher","first-page":"1281","DOI":"10.1109\/TPAMI.2002.1033219","volume":"24","author":"C Domeniconi","year":"2002","unstructured":"Domeniconi, C., Peng, J., Gunopulos, D.: Locally adaptive metric nearest-neighbor classification. IEEE Transactions on Pattern Analysis and Machine Intelligence 24(9), 1281\u20131285 (2002)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"25_CR22","doi-asserted-by":"crossref","unstructured":"Dongarra, J., Gates, M., Haidar, A., Kurzak, J., Luszczek, P., Tomov, S., Yamazaki, I.: Accelerating numerical dense linear algebra calculations with GPUs. In: Numerical Computations with GPUs, chapter 1, pp. 3\u201328. Springer International Publishing (2014)","DOI":"10.1007\/978-3-319-06548-9_1"},{"key":"25_CR23","doi-asserted-by":"crossref","unstructured":"Garcia, V., Debreuve, E., Barlaud, M.: Fast k nearest neighbor search using GPU. In: IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, CVPRW 2008, pp. 1\u20136. IEEE, June 2008","DOI":"10.1109\/CVPRW.2008.4563100"},{"key":"25_CR24","doi-asserted-by":"crossref","unstructured":"Garcia, V., Debreuve, \u00c9., Nielsen, F., Barlaud, M.: K-nearest neighbor search: fast GPU-based implementations and application to high-dimensional feature matching. In: Proceedings of 2010 IEEE 17th International Conference on Image Processing, pp. 3757\u20133760, September 2010","DOI":"10.1109\/ICIP.2010.5654017"},{"key":"25_CR25","doi-asserted-by":"crossref","unstructured":"Green, O., McColl, R., Bader, D.A.: GPU merge path - a GPU merging algorithm. In: Proceedings of the 26th ACM International Conference on Supercomputing, ICS 2012, pp. 331\u2013340. ACM (2012)","DOI":"10.1145\/2304576.2304621"},{"key":"25_CR26","doi-asserted-by":"crossref","unstructured":"H\u00e4rdle, W.: Applied nonparametric regression. Number 19 in Econometric Society Monographs. Cambridge University Press (1990)","DOI":"10.1017\/CCOL0521382483"},{"issue":"6","key":"25_CR27","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1109\/34.506411","volume":"18","author":"T Hastie","year":"1996","unstructured":"Hastie, T., Tibshirani, R.: Discriminant adaptive nearest neighbor classification. IEEE Transactions on Pattern Analysis and Machine Intelligence 18(6), 607\u2013616 (1996)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"1","key":"25_CR28","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1109\/TPAMI.2010.57","volume":"33","author":"H J\u00e9gou","year":"2011","unstructured":"J\u00e9gou, H., Douze, M., Schmid, C.: Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence 33(1), 117\u2013128 (2011)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"25_CR29","doi-asserted-by":"crossref","unstructured":"Kato, K., Hosino, T.: Solving $$k$$ -nearest neighbor problem on multiple graphics processors. In: Proceedings of the 2010 10th IEEE\/ACM International Conference on Cluster, Cloud and Grid Computing, CCGRID 2010, pp. 769\u2013773. IEEE Computer Society (2010)","DOI":"10.1109\/CCGRID.2010.47"},{"issue":"1","key":"25_CR30","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1002\/cpe.1718","volume":"24","author":"K Kato","year":"2012","unstructured":"Kato, K., Hosino, T.: Multi-GPU algorithm for $$k$$ -nearest neighbor problem. Concurrency and Computation: Practice and Experience 24(1), 45\u201353 (2012)","journal-title":"Concurrency and Computation: Practice and Experience"},{"issue":"5","key":"25_CR31","doi-asserted-by":"publisher","first-page":"e92409","DOI":"10.1371\/journal.pone.0092409","volume":"9","author":"I Komarov","year":"2014","unstructured":"Komarov, I., Dashti, A., D\u2019Souza, R.M.: Fast $$k$$ -NNG construction with GPU-based quick multi-select. PLOS ONE 9(5), e92409 (2014)","journal-title":"PLOS ONE"},{"issue":"3\u20134","key":"25_CR32","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s10619-012-7092-4","volume":"30","author":"M Kruli\u0161","year":"2012","unstructured":"Kruli\u0161, M., Skopal, T., Loko\u010d, J., Beecks, C.: Combining CPU and GPU architectures for fast similarity search. Distributed and Parallel Databases 30(3\u20134), 179\u2013207 (2012)","journal-title":"Distributed and Parallel Databases"},{"key":"25_CR33","unstructured":"Kuang, Q, Zhao, L.: A practical GPU based KNN algorithm. In: Proceedings of the Second Symposium International Computer Science and Computational Technology (ISCSCT 2009), pp. 151\u2013155. Citeseer, December 2009"},{"issue":"11","key":"25_CR34","doi-asserted-by":"publisher","first-page":"2045","DOI":"10.1109\/TPDS.2011.311","volume":"23","author":"J Kurzak","year":"2012","unstructured":"Kurzak, J., Tomov, S., Dongarra, J.: Autotuning GEMM kernels for the Fermi GPU. IEEE Transactions on Parallel and Distributed Systems 23(11), 2045\u20132057 (2012)","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"25_CR35","doi-asserted-by":"crossref","unstructured":"Liang, S., Liu, Y., Wang, C., Jian, L.: A CUDA-based parallel implementation of k-nearest neighbor algorithm. In: International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, CyberC 2009, pp. 291\u2013296. IEEE, October 2009","DOI":"10.1109\/CYBERC.2009.5399145"},{"key":"25_CR36","doi-asserted-by":"crossref","unstructured":"Liang, S., Liu, Y., Wang, C., Jian, L.: Design and evaluation of a parallel k-nearest neighbor algorithm on CUDA-enabled GPU. In: 2010 IEEE 2nd Symposium on Web Society (SWS), pp. 53\u201360. IEEE, August 2010","DOI":"10.1109\/SWS.2010.5607480"},{"key":"25_CR37","doi-asserted-by":"crossref","unstructured":"Liang, S., Wang, C., Liu, Y., Jian, L.: CUKNN: a parallel implementation of k-nearest neighbor onCUDA-enabled GPU. In: IEEE Youth Conference on Information, Computing and Telecommunication, YC-ICT 2009, pp. 415\u2013418. IEEE, September 2009","DOI":"10.1109\/YCICT.2009.5382329"},{"key":"25_CR38","doi-asserted-by":"crossref","unstructured":"Luka\u010d, N., \u017dalik, B.: Fast approximate k-nearest neighbours search using GPGPU. In: GPU Computing and Applications, chapter 14, pp. 221\u2013234. Springer (2015)","DOI":"10.1007\/978-981-287-134-3_14"},{"key":"25_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1007\/978-3-642-41062-8_30","volume-title":"Similarity Search and Applications","author":"N Miranda","year":"2013","unstructured":"Miranda, N., Ch\u00e1vez, E., Piccoli, M.F., Reyes, N.: (Very) Fast (All) k-nearest neighbors in metric and non metric spaces without indexing. In: Brisaboa, N., Pedreira, O., Zezula, P. (eds.) SISAP 2013. LNCS, vol. 8199, pp. 300\u2013311. Springer, Heidelberg (2013)"},{"issue":"4","key":"25_CR40","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1177\/1094342010385729","volume":"24","author":"R Nath","year":"2010","unstructured":"Nath, R., Tomov, S., Dongarra, J.: An improved magma gemm for Fermi graphics processing units. International Journal of High Performance Computing Applications 24(4), 511\u2013515 (2010)","journal-title":"International Journal of High Performance Computing Applications"},{"key":"25_CR41","doi-asserted-by":"crossref","unstructured":"Odeh, S., Green, O., Mwassi, Z., Shmueli, O., Birk, Y.: Merge path - parallel merging made simple. In: 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & Ph.D. Forum (IPDPSW), pp. 1611\u20131618. IEEE, May 2012","DOI":"10.1109\/IPDPSW.2012.202"},{"key":"25_CR42","doi-asserted-by":"crossref","unstructured":"Pan, J., Lauterbach, C., Manocha, D.: Efficient nearest-neighbor computation for GPU-based motion planning. In: The 2010 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 2243\u20132248. IEEE, October 2010","DOI":"10.1109\/IROS.2010.5651449"},{"key":"25_CR43","doi-asserted-by":"crossref","unstructured":"Pan, J., Manocha, D.: Fast GPU-based locality sensitive hashing for k-nearest neighbor computation. In: Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS 2011, pp. 211\u2013220. ACM, November 2011","DOI":"10.1145\/2093973.2094002"},{"key":"25_CR44","doi-asserted-by":"crossref","unstructured":"Pan, J., Manocha, D.: Bi-level locality sensitive hashing for k-nearest neighbor computation. In: 2012 IEEE 28th International Conference on Data Engineering (ICDE), pp. 378\u2013389. IEEE, April 2012","DOI":"10.1109\/ICDE.2012.40"},{"key":"25_CR45","doi-asserted-by":"crossref","unstructured":"Sismanis, N., Pitsianis, N., Sun, X.: Parallel search of $$k$$ -nearest neighbors with synchronous operations. In: 2012 IEEE Conference on High Performance Extreme Computing (HPEC), pp. 1\u20136. IEEE, September 2012","DOI":"10.1109\/HPEC.2012.6408667"},{"issue":"3","key":"25_CR46","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/s00778-013-0329-7","volume":"23","author":"G Teodoro","year":"2014","unstructured":"Teodoro, G., Valle, E., Mariano, N., Torres, R., Meira Jr, W., Saltz, J.H.: Approximate similarity search for online multimedia services on distributed CPU\u2013GPU platforms. The VLDB Journal 23(3), 427\u2013448 (2014)","journal-title":"The VLDB Journal"},{"key":"25_CR47","unstructured":"Vincent, P., Bengio, Y.: K-local hyperplane and convex distance nearest neighbor algorithms. In: Advances in Neural Information Processing Systems 14 (NIPS 2001), pp. 985\u2013992. MIT Press (2002)"},{"key":"25_CR48","first-page":"207","volume":"10","author":"KQ Weinberger","year":"2009","unstructured":"Weinberger, K.Q., Saul, L.K.: Distance metric learning for large margin nearest neighbor classification. Journal of Machine Learning Research 10, 207\u2013244 (2009)","journal-title":"Journal of Machine Learning Research"},{"key":"25_CR49","doi-asserted-by":"crossref","unstructured":"Zhang, H., Berg, A.C., Maire, M., Malik, J.: SVM-KNN: Discriminative nearest neighbor classification for visual category recognition. In: 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 2, pp. 2126\u20132136. IEEE (2006)","DOI":"10.1109\/CVPR.2006.301"}],"container-title":["Lecture Notes in Computer Science","Similarity Search and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-25087-8_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T22:50:51Z","timestamp":1748645451000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-25087-8_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319250861","9783319250878"],"references-count":49,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-25087-8_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}