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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</tex> denote the size of a codebook, and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</tex> denote the dimension of a vector. The search complexity of the BHT algorithm increases linearly with the resolution <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">r = (log₂N)/k</tex> for fixed dimension <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</tex> . 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k = 4</tex> , and codebook size <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N = 128</tex> using a single programmable signal processor, the TMS32010.