The first source of approximation comes from compressed vectors. The most popular vector compression methods includes binary codes [1]}, [2]}, and vector quantization methods [3]}, [4]}. These methods have the desirable property that searching neighbors does not require reconstructing the vectors. For example, in a vector quantization method, a vector is first reduced by
principal component analysis dimension reduction and then is subsequently quantized. Although the process introduces similarity approximation error, it often results in orders of magnitude of compression, significantly improving efficiency in vector storage and similarity calculation.
<FIGURE>