Abstract
We present a brute-force approach for finding k-nearest neighbors on the GPU for many queries in parallel. Our program takes advantage of recent advances in fundamental GPU computing primitives. We modify a matrix multiplication subroutine in MAGMA library [6] to calculate the squared Euclidean distances between queries and references. The nearest neighbors selection is accomplished by a truncated merge sort built on top of sorting and merging functions in the Modern GPU library [3]. Compared to state-of-the-art approaches, our program is faster and it handles larger inputs. For instance, we can find 1000 nearest neighbors among 1 million 64-dimensional reference points at a rate of about 435 queries per second.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
cuknns: GPU accelerated k-nearest neighbor library (2012). http://autogpu.ee.auth.gr/doku.php?id=cuknns:gpu_accelerated_k-nearest_neighbor_library
kNN CUDA (2013). http://vincentfpgarcia.github.io/kNN-CUDA/
Modern GPU (2013). http://nvlabs.github.io/moderngpu/
cuBLAS in CUDA toolkit 6.5. (2014). https://developer.nvidia.com/cuBLAS
CUDA toolkit 6.5. (2014). https://developer.nvidia.com/cuda-toolkit-65
MAGMA 1.6.1. (2015). http://icl.cs.utk.edu/magma/
Thrust (2015). https://developer.nvidia.com/Thrust
Altman, N.S.: An introduction to kernel and nearest-neighbor nonparametric regression. The American Statistician 46(3), 175–185 (1992)
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)
Barrientos, R.J., Gómez, 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–392. Springer, Heidelberg (2011)
Beliakov, G., Johnstone, M., Nahavandi, S.: Computing of high breakdown regression estimators without sorting on graphics processing units. Computing 94(5), 433–447 (2012)
Beliakov, G., Li, G.: Improving the speed and stability of the k-nearest neighbors method. Pattern Recognition Letters 33(10), 1296–1301 (2012)
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–522 (2002)
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–235. Springer, Heidelberg (1998)
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–8. IEEE, June 2008
Cayton, L.: Accelerating nearest neighbor search on manycore systems. In: 2012 IEEE 26th International Parallel and Distributed Processing Symposium, pp. 402–413. IEEE, May 2012
Cover, T.M., Hart, P.E.: Nearest neighbor pattern classification. IEEE Transactions on Information Theory 13(1), 21–27 (1967)
Dashti, A., Komarov, I., D’Souza, R.M.: Efficient computation of k-nearest neighbour graphs for large high-dimensional data sets on GPU clusters. PLOS ONE 8(9), e74113 (2013)
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–262. ACM (2004)
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–95. Springer (2015)
Domeniconi, C., Peng, J., Gunopulos, D.: Locally adaptive metric nearest-neighbor classification. IEEE Transactions on Pattern Analysis and Machine Intelligence 24(9), 1281–1285 (2002)
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–28. Springer International Publishing (2014)
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–6. IEEE, June 2008
Garcia, V., Debreuve, É., 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–3760, September 2010
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–340. ACM (2012)
Härdle, W.: Applied nonparametric regression. Number 19 in Econometric Society Monographs. Cambridge University Press (1990)
Hastie, T., Tibshirani, R.: Discriminant adaptive nearest neighbor classification. IEEE Transactions on Pattern Analysis and Machine Intelligence 18(6), 607–616 (1996)
Jégou, H., Douze, M., Schmid, C.: Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence 33(1), 117–128 (2011)
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–773. IEEE Computer Society (2010)
Kato, K., Hosino, T.: Multi-GPU algorithm for \(k\)-nearest neighbor problem. Concurrency and Computation: Practice and Experience 24(1), 45–53 (2012)
Komarov, I., Dashti, A., D’Souza, R.M.: Fast \(k\)-NNG construction with GPU-based quick multi-select. PLOS ONE 9(5), e92409 (2014)
Kruliš, M., Skopal, T., Lokoč, J., Beecks, C.: Combining CPU and GPU architectures for fast similarity search. Distributed and Parallel Databases 30(3–4), 179–207 (2012)
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–155. Citeseer, December 2009
Kurzak, J., Tomov, S., Dongarra, J.: Autotuning GEMM kernels for the Fermi GPU. IEEE Transactions on Parallel and Distributed Systems 23(11), 2045–2057 (2012)
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–296. IEEE, October 2009
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–60. IEEE, August 2010
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–418. IEEE, September 2009
Lukač, N., Žalik, B.: Fast approximate k-nearest neighbours search using GPGPU. In: GPU Computing and Applications, chapter 14, pp. 221–234. Springer (2015)
Miranda, N., Chávez, 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–311. Springer, Heidelberg (2013)
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–515 (2010)
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–1618. IEEE, May 2012
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–2248. IEEE, October 2010
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–220. ACM, November 2011
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–389. IEEE, April 2012
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–6. IEEE, September 2012
Teodoro, G., Valle, E., Mariano, N., Torres, R., Meira Jr, W., Saltz, J.H.: Approximate similarity search for online multimedia services on distributed CPU–GPU platforms. The VLDB Journal 23(3), 427–448 (2014)
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–992. MIT Press (2002)
Weinberger, K.Q., Saul, L.K.: Distance metric learning for large margin nearest neighbor classification. Journal of Machine Learning Research 10, 207–244 (2009)
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–2136. IEEE (2006)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Li, S., Amenta, N. (2015). Brute-Force k-Nearest Neighbors Search on the GPU. In: Amato, G., Connor, R., Falchi, F., Gennaro, C. (eds) Similarity Search and Applications. SISAP 2015. Lecture Notes in Computer Science(), vol 9371. Springer, Cham. https://doi.org/10.1007/978-3-319-25087-8_25
Download citation
DOI: https://doi.org/10.1007/978-3-319-25087-8_25
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-25086-1
Online ISBN: 978-3-319-25087-8
eBook Packages: Computer ScienceComputer Science (R0)