A Fast Algorithm for k-Nearest Neighbor Problem on a Reconfigurable Mesh Computer

Given a set S of m points stored on a reconfigurable mesh computer of size n×n, one point per processing element (PE). In this paper we present a parallel method for solving the k-Nearest Neighbor problem (k-NN). This method permits each point of S to know its k-NN (0<k<m). The corresponding algorithm requires that each PE must have 2k registers where it stores the (x,y) coordinates of its k-NN in a given order. This algorithm has a complexity of O(logh+k ²) times, where h is a maximal number of points within a row of the mesh. This complexity is reduced to O(k ²) times, using an appropriate procedure which demonstrates the power of the reconfiguration operations carried out by the processors, and the polymorphic properties of the mesh.