Artificial neural networks for the nearest neighbor search problem

The naturally parallel structure and the possibility of analog implementations of neural networks make them attractive for real-time applications involving vector quantization that require the nearest neighbor search process with high computational complexity. Three neural-net methods to identify the nearest codevector have been proposed in this paper. Method I is based on the property that a perceptron separates the Euclidean space linearly into two half-spaces. Thus, for a codebook with N codevectors, N(N-1)/2 perceptrons combined with N logical AND gates can completely identify the nearest codevector. An efficient algorithm to detect redundant perceptrons has also been developed. Method II uses this efficient algorithm to identify all redundant perceptrons that can be removed from the neural network in Method I. Method III uses a backpropagation neural network combined with a limited exhaustive full search process within a small size neighboring codevector set to finally identify the nearest codevector.<>