research-article

A Partitioning GPU-based Algorithm for Processing the k Nearest-Neighbor Query

Authors:

Polychronis Velentzas,

Michael Vassilakopoulos,

Antonio CorralAuthors Info & Claims

MEDES '20: Proceedings of the 12th International Conference on Management of Digital EcoSystems

Pages 2 - 9

https://doi.org/10.1145/3415958.3433071

Published: 27 November 2020 Publication History

Abstract

The k Nearest-Neighbor (k-NN) query is a common spatial query that appears in several big data applications. Typically, GPU devices have much larger numbers of processing cores than CPUs and faster device memory than main memory accessed by CPUs, thus, providing higher computing power. We propose and implement a new GPU-based partitioning algorithm for the k-NN query, using the CUDA runtime API. Due to partitioning, this algorithm avoids calculating distances for the whole dataset. Using synthetic and real datasets, we present an extensive experimental performance comparison against six existing algorithms. These algorithms are based on calculating distances for the whole in-memory dataset. This comparison shows that the new algorithm excels in all the conducted experiments and outperforms these six algorithms.

References

[1]

Ahmed Shamsul Arefin, Carlos Riveros, Regina Berretta, and Pablo Moscato. 2012. GPU-FS-kNN: A software tool for fast and scalable kNN computation using GPUs. PloS ONE 7, 8 (2012), 1--13.

[2]

Gerassimos Barlas. 2014. Multicore and GPU Programming: An Integrated Approach (1 ed.). Morgan Kaufmann.

Digital Library

[3]

Ricardo J. Barrientos, José Ignacio Gómez, Christian Tenllado, Manuel Prieto-Matías, and Mauricio Marín. 2011. kNN Query Processing in Metric Spaces Using GPUs. In Euro-Par Conference. 380--392.

Digital Library

[4]

Ricardo J. Barrientos, Fabricio Millaguir, José L. Sánchez, and Enrique Arias. 2017. GPU-based exhaustive algorithms processing kNN queries. The Journal of Supercomputing 73, 10 (2017), 4611--4634.

Digital Library

[5]

Ahmed Eldawy and Mohamed F. Mokbel. 2015. SpatialHadoop: A MapReduce framework for spatial data. In ICDE Conference. 1352--1363.

[6]

Vincent Garcia, Eric Debreuve, Frank Nielsen, and Michel Barlaud. 2010. K-nearest neighbor search: Fast GPU-based implementations and application to high-dimensional feature matching. In ICIP Conference. 3757--3760.

[7]

Vincent Garcia, Éric Debreuve, and Michel Barlaud. 2018. Fast k nearest neighbor search using GPU. http://vincentfpgarcia.github.io/kNN-CUDA/

[8]

Pablo David Gutiérrez, Miguel Lastra, Jaume Bacardit, José Manuel Benítez, and Francisco Herrera. 2016. GPU-SME-kNN: Scalable and memory efficient kNN and lazy learning using GPUs. Inf. Sci. 373 (2016), 165--182.

Digital Library

[9]

S.B. Imandoust and Mohammad Bolandraftar. 2013. Application of K-nearest neighbor (KNN) approach for predicting economic events theoretical background. Int J Eng Res Appl 3 (01 2013), 605--610.

[10]

Kimikazu Kato and Tikara Hosino. 2012. Multi-GPU algorithm for k-nearest neighbor problem. Concurrency and Computation: Practice and Experience 24, 1 (2012), 45--53.

[11]

Ivan Komarov, Ali Dashti, and Roshan M. D'Souza. 2014. Fast k-NNG Construction with GPU-Based Quick Multi-Select. PloS ONE 9, 5 (2014), 1--9.

[12]

Quansheng Kuang and Lei Zhao. 2009. A Practical GPU Based KNN Algorithm. In SCSCT Conference. 151--155.

[13]

Shengren Li and Nina Amenta. 2015. Brute-Force k-Nearest Neighbors Search on the GPU. In SISAP Conference. 259--270.

Digital Library

[14]

Shenshen Liang, Cheng Wang, Ying Liu, and Liheng Jian. 2009. CUKNN: A parallel implementation of K-nearest neighbor on CUDA-enabled GPU. In YCICT Conference. 415--418.

[15]

Jan Masek, Radim Burget, Jan Karasek, Václav Uher, and Malay Kishore Dutta. 2015. Multi-GPU implementation of k-nearest neighbor algorithm. In TSP Conference. 764--767.

[16]

Gang Mei, Nengxiong Xu, and Liangliang Xu. 2016. Improving GPU-accelerated adaptive IDW interpolation algorithm using fast kNN search. SpringerPlus 5, 1 (2016), 1389.

[17]

NVIDIA. 2020. NVIDIA CUDA Runtime API. https://docs.nvidia.com/cuda/cuda-runtime- api/index.html

[18]

Jia Pan, Christian Lauterbach, and Dinesh Manocha. 2010. Efficient nearest-neighbor computation for GPU-based motion planning. In IROS Conference. 2243--2248.

[19]

Jia Pan and Dinesh Manocha. 2011. Fast GPU-based locality sensitive hashing for k-nearest neighbor computation. In ACM-GIS Conference. 211--220.

Digital Library

[20]

George Roumelis, Antonio Corral, Michael Vassilakopoulos, and Yannis Manolopoulos. 2016. New plane-sweep algorithms for distance-based join queries in spatial databases. GeoInformatica 20, 4 (2016), 571--628.

Digital Library

[21]

George Roumelis, Polychronis Velentzas, Michael Vassilakopoulos, Antonio Corral, Athanasios Fevgas, and Yannis Manolopoulos. 2019. Parallel processing of spatial batch-queries using xBR+-trees in solid-state drives. Cluster Computing (2019).

[22]

Amreek Singh, Kusum Deep, and Pallavi Grover. 2017. A novel approach to accelerate calibration process of a k-nearest neighbours classifier using GPU. J. Parallel Distrib. Comput. 104 (2017), 114--129.

Digital Library

[23]

Nikos Sismanis, Nikos Pitsianis, and Xiaobai Sun. 2012. Parallel search of k-nearest neighbors with synchronous operations. In HPEC Conference. 1--6.

[24]

Polychronis Velentzas, Michael Vassilakopoulos, and Antonio Corral. 2020. Inmemory k Nearest Neighbor GPU-based Query Processing. In GISTAM - Proc. of the 6st Int. Conf. on Geographical Information Systems Theory, Applications and Management, Prague, Czech Republic, 7-9 May, 2020, to appear. SciTePress.

[25]

Patrick Wieschollek, Oliver Wang, Alexander Sorkine-Hornung, and Hendrik P. A. Lensch. 2017. Efficient Large-scale Approximate Nearest Neighbor Search on the GPU. CoRR abs/1702.05911 (2017).

Cited By

Agathos AAzariadis P(2024)Multi-GPU 3D k-nearest neighbors computation with application to ICP, point cloud smoothing and normals computationParallel Computing10.1016/j.parco.2024.103093121:COnline publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1016/j.parco.2024.103093
Li YZhao XChen AYang GSong W(2023)GERWkNN: GPU-accelerated Exact Random Walk-based kNN Query in Large GraphsProceedings of the 2023 5th International Conference on Big Data Engineering10.1145/3640872.3640880(47-54)Online publication date: 17-Nov-2023
https://dl.acm.org/doi/10.1145/3640872.3640880
Velentzas PVassilakopoulos MCorral AAntonopoulos C(2023)GPU-Based Algorithms for Processing the k Nearest-Neighbor Query on Spatial Data Using Partitioning and Concurrent Kernel ExecutionInternational Journal of Parallel Programming10.1007/s10766-023-00755-8Online publication date: 21-Jul-2023
https://doi.org/10.1007/s10766-023-00755-8
Show More Cited By

Index Terms

A Partitioning GPU-based Algorithm for Processing the k Nearest-Neighbor Query
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel algorithms
      1. Massively parallel algorithms
      2. Shared memory algorithms
2. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database query processing

Recommendations

An Improved GPU-based Algorithmfor Processing the k Nearest Neighbor Query
PCI '20: Proceedings of the 24th Pan-Hellenic Conference on Informatics

The k Nearest Neighbor (k-NN) query is a common spatial query that appears in several big data applications. We propose and implement a new GPU-based algorithm for the k-NN query, which improves our previous Symmetric Progression Partitioning method (...
GPU-Based Algorithms for Processing the k Nearest-Neighbor Query on Disk-Resident Data
Model and Data Engineering
Abstract
Algorithms for answering the k Nearest-Neighbor (k-NN) query are widely used for queries in spatial databases and for distance classification of a group of query points against a reference dataset to derive the dominating feature class. GPU ...
GPU-Based Algorithms for Processing the k Nearest-Neighbor Query on Spatial Data Using Partitioning and Concurrent Kernel Execution
Abstract
Algorithms for answering the k nearest-neighbor (k-NN) query are widely used for queries in spatial databases and for distance classification of a group of query points against a reference dataset to derive the dominating feature class. GPU ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

MEDES '20: Proceedings of the 12th International Conference on Management of Digital EcoSystems

November 2020

170 pages

ISBN:9781450381154

DOI:10.1145/3415958

General Chairs:
Richard Chbeir
University Pau & Pays de l'Adour, France
,
Yannis Manolopoulos
Open University of Cyprus, Cyprus
,
Ernesto Damiani
Khalifa University of Science and Technology, UAE
,
Djamal Benslimane
Lyon 1 University, France
,
Program Chairs:
Ladjel Bellatreche
LIAS/ISAE-ENSMA, France
,
Tadeusz Morzy
Poznan University of Technology, Poland

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 November 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

Ministerio de Economía y Competitividad (MINECO)

Conference

MEDES '20

MEDES '20: 12th International Conference on Management of Digital EcoSystems

November 2 - 4, 2020

Virtual Event, United Arab Emirates

Acceptance Rates

MEDES '20 Paper Acceptance Rate 19 of 27 submissions, 70%;

Overall Acceptance Rate 267 of 682 submissions, 39%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
167
Total Downloads

Downloads (Last 12 months)25
Downloads (Last 6 weeks)2

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Agathos AAzariadis P(2024)Multi-GPU 3D k-nearest neighbors computation with application to ICP, point cloud smoothing and normals computationParallel Computing10.1016/j.parco.2024.103093121:COnline publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1016/j.parco.2024.103093
Li YZhao XChen AYang GSong W(2023)GERWkNN: GPU-accelerated Exact Random Walk-based kNN Query in Large GraphsProceedings of the 2023 5th International Conference on Big Data Engineering10.1145/3640872.3640880(47-54)Online publication date: 17-Nov-2023
https://dl.acm.org/doi/10.1145/3640872.3640880
Velentzas PVassilakopoulos MCorral AAntonopoulos C(2023)GPU-Based Algorithms for Processing the k Nearest-Neighbor Query on Spatial Data Using Partitioning and Concurrent Kernel ExecutionInternational Journal of Parallel Programming10.1007/s10766-023-00755-8Online publication date: 21-Jul-2023
https://doi.org/10.1007/s10766-023-00755-8
Biswas PDandapat SSairam A(2022)RippleInformation Systems10.1016/j.is.2021.101933105:COnline publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1016/j.is.2021.101933
Velentzas PVassilakopoulos MCorral A(2021)GPU-Based Algorithms for Processing the k Nearest-Neighbor Query on Disk-Resident DataModel and Data Engineering10.1007/978-3-030-78428-7_21(264-278)Online publication date: 14-Jun-2021
https://doi.org/10.1007/978-3-030-78428-7_21

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents