A fast codebook search algorithm for nearest-neighbor pattern matching

A critical issue in the use of Vector Quantization is to circumvent the complexity bottleneck that prevents the full power of this data compression technique from being exploited. The demanding exhaustive codebook search can be avoided by more efficient algorithms for locating the nearest codevector in a codebook to a given input vector. This paper introduces a fast nearest neighbor search algorithm, the Binary Hyperplane Testing (BHT) algorithm, for fast codebook searching when least Euclidean distance is the appropriate distortion or dissimilarity measure. Let denote the size of a codebook, and denote the dimension of a vector. The search complexity of the BHT algorithm increases linearly with the resolution for fixed dimension . The search complexity of the BHT algorithm is sufficiently low that it has been used to implement a real-time speech waveform vector quantizer with sampling rate 8 KHz, dimension , and codebook size using a single programmable signal processor, the TMS32010.