A fast nearest-neighbor search algorithm

A fast nearest-neighbor search algorithm is developed which incorporates prior information about input vectors. The prior information comes in the form of a vector from the codebook which is known to be near the input vector, though it may not be the nearest codebook vector. A number of applications are described for which such prior information is available. The algorithm has a very simple structure and can be designed to have very low memory requirements. The new algorithm requires much less computation for constructing precomputed tables than previously proposed algorithms with comparable performance. Simulations show dramatic saving over conventional full search methods