Efficient Distributed Algorithms for the -Nearest Neighbors Problem
The -nearest neighbors is a basic problem in machine learning with numerous applications. In this problem, given a (training) set of data points with labels and a query point , we want to assign a label to based on the labels of the -nearest points to the query. We study this problem in the {\em -machine model}, (Note that parameter stands for the number of machines in the -machine model and is independent of -nearest points.) a model for distributed large-scale data. In this model, we assume that the points are distributed (in a balanced fashion) among the machines and the goal is to quickly compute answer given a query point to a machine. Our main result is a simple randomized algorithm in the -machine model that runs in communication rounds with high probability success (regardless of the number of machines and the number of points ). The message complexity of the algorithm is small taking only messages. Our bounds are essentially the best possible for comparison-based algorithms (Algorithms that use only comparison operations () between elements to distinguish the ordering among them). This is due to the existence of a lower bound of communication rounds for finding the {\em median} of elements distributed evenly among two processors by Rodeh \cite{rodeh}. We also implemented our algorithm and show that it performs well compared to an algorithm (used in practice) that sends nearest points from each machine to a single machine which then computes the answer.