Telescope indexing for k-nearest neighbor search algorithms over high dimensional data & large data sets.

Area of Science:

• Computer Science
• Machine Learning
• Data Structures

Background:

• k-Nearest-Neighbors (kNN) algorithms struggle with large, high-dimensional datasets.
• Existing methods like k-d trees and ball-trees are insufficient for high-dimensional data due to ineffective space partitioning.

Purpose of the Study:

• To develop an efficient kNN search algorithm for high-dimensional data.
• To overcome the limitations of traditional space partitioning techniques in high dimensions.

Main Methods:

• A novel approach using a B+ tree to partition data based on distances from a reference point.
• Limiting the search space for kNN queries using the B+ tree structure.
• Developing and evaluating the ti-kNN algorithm.

Main Results:

• The ti-kNN algorithm demonstrates significant speedups compared to naive kNN, k-d trees, and ball-trees.
• Experiments confirm the effectiveness of the B+ tree partitioning for reducing search space in high-dimensional data.
• The proposed method outperforms other state-of-the-art approximate kNN search approaches.

Conclusions:

• The B+ tree-based partitioning strategy effectively enhances kNN search performance in high-dimensional spaces.
• ti-kNN offers a scalable and efficient solution for kNN queries on large, complex datasets.
• This approach provides a substantial improvement over existing methods for high-dimensional data analysis.