Telescope indexing for k-nearest neighbor search algorithms over high dimensional data & large data sets
Abstract When k-Nearest-Neighbors ( $$k$$ -NN) was conceived more than 70 years ago, computation, as we use it now, would be hardly recognizable. Since then, technology has improved by orders of magnitude, including unprecedented connectivity. However, $$k$$ -NN has remained virtually unchanged, exp...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Nature Portfolio
2025-07-01
|
| Series: | Scientific Reports |
| Subjects: | |
| Online Access: | https://doi.org/10.1038/s41598-025-09856-5 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Abstract When k-Nearest-Neighbors ( $$k$$ -NN) was conceived more than 70 years ago, computation, as we use it now, would be hardly recognizable. Since then, technology has improved by orders of magnitude, including unprecedented connectivity. However, $$k$$ -NN has remained virtually unchanged, exposing its shortcomings for today’s needs: becoming overwhelmed when presented with large, high-dimensional data. Although space partitioning data structures, especially k-d trees and ball-trees, have improved performance in larger data, they remain inadequate when data is also high-dimensional. Experiments confirm that space partitioning becomes ineffective in high-dimensional data because most of the search space is explored needlessly. Our strategy is to partition the data into small groups of points similarly distanced from a reference point in a B+ tree data structure and use this data structure to limit the search space of a $$k$$ -NN query. Further, we establish that the limited search space chosen by the B+ tree structure can be effectively explored by any indexing techniques applicable to the entire data. We then present our algorithm $$k$$ -NN with partitioning (ti $$k$$ -NN), including computational analysis and experiments. Our detailed evaluation demonstrates significant speedup achieved by ti $$k$$ -NN over the naive, $$k$$ -d tree, $$ball$$ -tree based $$k$$ -NN and other state-of-the-art approximate $$k$$ -NN search approaches in high dimensional data. |
|---|---|
| ISSN: | 2045-2322 |