AN EFFICIENT APPROXIMATION-ELIMINATION ALGORITHM FOR FAST NEAREST-NEIGHBOR SEARCH BASED ON A SPHERICAL DISTANCE COORDINATE FORMULATION

An efficient approximation-elimination search algorithm for fast nearest-neighbour search is proposed based on a spherical distance coordinate formulation, where a vector in K-dimensional space is represented uniquely by its distances from K + 1 fixed points. The proposed algorithm uses triangle-inequality based elimination rules which is applicable for search using metric distances measures. It is a more efficient fixed point equivalent of the Approximation Elimination Search Algorithm (AESA) proposed earlier by Vidal [2]. In comparison to AESA which has a very high O(N2) storage complexity, the proposed algorithm uses only O(N) storage with very low approximation-elimination computational overheads while achieving complexity reductions closely comparable to AESA. The algorithm is used for fast vector quantization of speech waveforms and is observed to have O(K + 1) average complexity.