A Fast kNN Algorithm Using Multiple Space-Filling Curves.

Area of Science:

• Computer Science
• Data Mining
• Machine Learning

Background:

• The k-nearest neighbours (kNN) algorithm is a fundamental tool in machine learning.
• Traditional kNN implementations can be computationally intensive, especially with large datasets.
• Dimensionality reduction techniques, such as space-filling curves, are known methods for accelerating kNN.

Purpose of the Study:

• To propose and evaluate a novel, time-efficient implementation of the k-nearest neighbours (kNN) algorithm.
• To enhance the performance of kNN by utilizing multiple space-filling curves for dimensionality reduction.
• To compare the proposed algorithm's speed and quality against existing kNN methods that use kd-trees.

Main Methods:

• Development of an algorithm employing multiple space-filling curves for kNN acceleration.
• A specific method for constructing multiple Peano curves is detailed.
• Analysis of proximity information preservation during dimensionality reduction.

Main Results:

• The proposed multi-space-filling curve algorithm demonstrates faster execution times compared to kNN implementations using kd-trees.
• The algorithm achieves comparable quality to kd-tree based kNN methods.
• Experimental validation was conducted using both synthetic and real-world datasets.

Conclusions:

• The novel kNN algorithm utilizing multiple space-filling curves offers a significant speed improvement over kd-tree based approaches.
• This method provides a viable and efficient alternative for nearest neighbour searches.
• The approach effectively preserves proximity information, ensuring reliable results.