A fast codebook search algorithm for nearest-neighbor pattern matching
De-Yuan Cheng, A. Gersho · 2005
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. LetNdenote the size of a codebook, andkdenote the dimension of a vector. The search complexity of the BHT algorithm increases linearly with the resolutionr = (\log_{2}N)/kfor fixed dimensionk. 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, dimensionk = 4, and codebook sizeN = 128using a single programmable signal processor, the TMS32010.