Cargando…

A Fast kNN Algorithm Using Multiple Space-Filling Curves

The paper considers a time-efficient implementation of the k nearest neighbours (kNN) algorithm. A well-known approach for accelerating the kNN algorithm is to utilise dimensionality reduction methods based on the use of space-filling curves. In this paper, we take this approach further and propose...

Descripción completa

Detalles Bibliográficos
Autores principales: Barkalov, Konstantin, Shtanyuk, Anton, Sysoyev, Alexander
Formato: Online Artículo Texto
Lenguaje:English
Publicado: MDPI 2022
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9223091/
https://www.ncbi.nlm.nih.gov/pubmed/35741488
http://dx.doi.org/10.3390/e24060767
_version_ 1784733037829816320
author Barkalov, Konstantin
Shtanyuk, Anton
Sysoyev, Alexander
author_facet Barkalov, Konstantin
Shtanyuk, Anton
Sysoyev, Alexander
author_sort Barkalov, Konstantin
collection PubMed
description The paper considers a time-efficient implementation of the k nearest neighbours (kNN) algorithm. A well-known approach for accelerating the kNN algorithm is to utilise dimensionality reduction methods based on the use of space-filling curves. In this paper, we take this approach further and propose an algorithm that employs multiple space-filling curves and is faster (with comparable quality) compared with the kNN algorithm, which uses kd-trees to determine the nearest neighbours. A specific method for constructing multiple Peano curves is outlined, and statements are given about the preservation of object proximity information in the course of dimensionality reduction. An experimental comparison with known kNN implementations using kd-trees was performed using test and real-life data.
format Online
Article
Text
id pubmed-9223091
institution National Center for Biotechnology Information
language English
publishDate 2022
publisher MDPI
record_format MEDLINE/PubMed
spelling pubmed-92230912022-06-24 A Fast kNN Algorithm Using Multiple Space-Filling Curves Barkalov, Konstantin Shtanyuk, Anton Sysoyev, Alexander Entropy (Basel) Article The paper considers a time-efficient implementation of the k nearest neighbours (kNN) algorithm. A well-known approach for accelerating the kNN algorithm is to utilise dimensionality reduction methods based on the use of space-filling curves. In this paper, we take this approach further and propose an algorithm that employs multiple space-filling curves and is faster (with comparable quality) compared with the kNN algorithm, which uses kd-trees to determine the nearest neighbours. A specific method for constructing multiple Peano curves is outlined, and statements are given about the preservation of object proximity information in the course of dimensionality reduction. An experimental comparison with known kNN implementations using kd-trees was performed using test and real-life data. MDPI 2022-05-30 /pmc/articles/PMC9223091/ /pubmed/35741488 http://dx.doi.org/10.3390/e24060767 Text en © 2022 by the authors. https://creativecommons.org/licenses/by/4.0/Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).
spellingShingle Article
Barkalov, Konstantin
Shtanyuk, Anton
Sysoyev, Alexander
A Fast kNN Algorithm Using Multiple Space-Filling Curves
title A Fast kNN Algorithm Using Multiple Space-Filling Curves
title_full A Fast kNN Algorithm Using Multiple Space-Filling Curves
title_fullStr A Fast kNN Algorithm Using Multiple Space-Filling Curves
title_full_unstemmed A Fast kNN Algorithm Using Multiple Space-Filling Curves
title_short A Fast kNN Algorithm Using Multiple Space-Filling Curves
title_sort fast knn algorithm using multiple space-filling curves
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9223091/
https://www.ncbi.nlm.nih.gov/pubmed/35741488
http://dx.doi.org/10.3390/e24060767
work_keys_str_mv AT barkalovkonstantin afastknnalgorithmusingmultiplespacefillingcurves
AT shtanyukanton afastknnalgorithmusingmultiplespacefillingcurves
AT sysoyevalexander afastknnalgorithmusingmultiplespacefillingcurves
AT barkalovkonstantin fastknnalgorithmusingmultiplespacefillingcurves
AT shtanyukanton fastknnalgorithmusingmultiplespacefillingcurves
AT sysoyevalexander fastknnalgorithmusingmultiplespacefillingcurves