Rotated Partial Distance Search for Faster Vector
Quantization Encoding, James McNames · 2000
Partial Distance Search (PDS) is a method of reducing the amount of computation required for vector quantization encoding. The method is simple and general enough to be incorporated into many fast encoding algo- rithms. This paper describes a simple improvement to PDS, based on principal components analysis,that rotates the codebook without altering the interpoint distances. Like PDS,this new method can be used to improve many fast encoding algorithms. The algorithm decreases the decoding time of PDS by as much as 44% and decreases the decod- ing time of k-d trees by as much as 66% on common vector quantization benchmarks.