Distributed Computation of the knn Graph for Large High-Dimensional Point Sets

Area of Science:

• Computational science
• Data science
• Robotics

Background:

• High-dimensional data analysis is crucial in fields like robotics, biology, and data mining.
• Computing k-nearest neighbor (knn) graphs is essential for these analyses but computationally intensive.
• Existing methods struggle with large datasets and arbitrary distance metrics on single machines.

Purpose of the Study:

• To develop an efficient, distributed framework for computing knn graphs.
• To enable the computation of knn graphs for large, high-dimensional datasets exceeding single-machine capacity.
• To extend the framework for other proximity queries like approximate knn and range queries.

Main Methods:

• A distributed computation framework using message passing for clusters of processors.
• Implementation of algorithms for efficient knn graph construction.
• Experimental validation on high-dimensional datasets.

Main Results:

• The distributed framework achieves nearly linear speedup with over 100 processors.
• The method demonstrates scalability for computations involving hundreds of processors.
• The framework successfully computes knn graphs for large, high-dimensional data.

Conclusions:

• The proposed distributed approach efficiently tackles the computational demands of knn graph construction.
• The framework offers a scalable solution for complex proximity queries in high-dimensional spaces.
• This work significantly advances the feasibility of analyzing large datasets in various scientific domains.