Efficient Computation of the <italic>K</italic> Nearest Neighbors Query Using Incremental Radius on a <italic>k</italic>²-tree
Proximity searches within metric spaces are critical for numerous real world applications, including pattern recognition, multimedia information retrieval, and spatial data analysis, among others. With the exponential increase in data volume, the demand for memory efficient structures to store and p...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10975746/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849314527713165312 |
|---|---|
| author | Rodrigo Torres-Aviles Monica Caniupan |
| author_facet | Rodrigo Torres-Aviles Monica Caniupan |
| author_sort | Rodrigo Torres-Aviles |
| collection | DOAJ |
| description | Proximity searches within metric spaces are critical for numerous real world applications, including pattern recognition, multimedia information retrieval, and spatial data analysis, among others. With the exponential increase in data volume, the demand for memory efficient structures to store and process information has become increasingly important. In this paper, we present an alternative algorithm for efficient computation of the K-nearest neighbors (KNN) query using the <inline-formula> <tex-math notation="LaTeX">$k^{2}$ </tex-math></inline-formula>-tree compact data structure, using the incremental radius technique. This approach offers an alternative to the existing algorithm that utilizes a priority queue over <inline-formula> <tex-math notation="LaTeX">$k^{2}$ </tex-math></inline-formula>-trees. Through both theoretical and experimental analysis, we demonstrate that our proposed algorithm is up to 2 times faster compared to the priority queue based solution, while also providing substantial improvements in memory efficiency. |
| format | Article |
| id | doaj-art-062d4f6a85dd4e5997d6a777df2d4d53 |
| institution | Kabale University |
| issn | 2169-3536 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-062d4f6a85dd4e5997d6a777df2d4d532025-08-20T03:52:25ZengIEEEIEEE Access2169-35362025-01-0113727787278910.1109/ACCESS.2025.356418510975746Efficient Computation of the <italic>K</italic> Nearest Neighbors Query Using Incremental Radius on a <italic>k</italic>²-treeRodrigo Torres-Aviles0Monica Caniupan1https://orcid.org/0000-0003-1543-2378Departamento de Sistemas de Información, Universidad del Bío-Bío, Concepción, ChileDepartamento de Sistemas de Información, Universidad del Bío-Bío, Concepción, ChileProximity searches within metric spaces are critical for numerous real world applications, including pattern recognition, multimedia information retrieval, and spatial data analysis, among others. With the exponential increase in data volume, the demand for memory efficient structures to store and process information has become increasingly important. In this paper, we present an alternative algorithm for efficient computation of the K-nearest neighbors (KNN) query using the <inline-formula> <tex-math notation="LaTeX">$k^{2}$ </tex-math></inline-formula>-tree compact data structure, using the incremental radius technique. This approach offers an alternative to the existing algorithm that utilizes a priority queue over <inline-formula> <tex-math notation="LaTeX">$k^{2}$ </tex-math></inline-formula>-trees. Through both theoretical and experimental analysis, we demonstrate that our proposed algorithm is up to 2 times faster compared to the priority queue based solution, while also providing substantial improvements in memory efficiency.https://ieeexplore.ieee.org/document/10975746/Proximity searchesKNNk²-treecompact data structuresincremental radiusspatial databases |
| spellingShingle | Rodrigo Torres-Aviles Monica Caniupan Efficient Computation of the <italic>K</italic> Nearest Neighbors Query Using Incremental Radius on a <italic>k</italic>²-tree IEEE Access Proximity searches KNN k²-tree compact data structures incremental radius spatial databases |
| title | Efficient Computation of the <italic>K</italic> Nearest Neighbors Query Using Incremental Radius on a <italic>k</italic>²-tree |
| title_full | Efficient Computation of the <italic>K</italic> Nearest Neighbors Query Using Incremental Radius on a <italic>k</italic>²-tree |
| title_fullStr | Efficient Computation of the <italic>K</italic> Nearest Neighbors Query Using Incremental Radius on a <italic>k</italic>²-tree |
| title_full_unstemmed | Efficient Computation of the <italic>K</italic> Nearest Neighbors Query Using Incremental Radius on a <italic>k</italic>²-tree |
| title_short | Efficient Computation of the <italic>K</italic> Nearest Neighbors Query Using Incremental Radius on a <italic>k</italic>²-tree |
| title_sort | efficient computation of the italic k italic nearest neighbors query using incremental radius on a italic k italic x00b2 tree |
| topic | Proximity searches KNN k²-tree compact data structures incremental radius spatial databases |
| url | https://ieeexplore.ieee.org/document/10975746/ |
| work_keys_str_mv | AT rodrigotorresaviles efficientcomputationoftheitalickitalicnearestneighborsqueryusingincrementalradiusonaitalickitalicx00b2tree AT monicacaniupan efficientcomputationoftheitalickitalicnearestneighborsqueryusingincrementalradiusonaitalickitalicx00b2tree |