Research Of Nearest Neighbor Search Based On VQ

Near Neighbor querying on multidimensional data is one of the most commonformulations in digital media processing applications, which has been extensivelystudied for long. Most of the approaches published thus far are still beset by suchproblems as high dimension and large scale. As vector quantization has many goodfeatures, indexes based on vector quantization have become a new approach forsimilarity search which is both promising and practical.In the thesis, we first take a general view on the multidimensional similarity query,difficulties and general ideas, and the basic idea of several state-of-art indexing methods.Then we introduce the principles and techniques of vector quantization according to theneed of NNS. Then we analyze the power of product quantization and residualquantization, and talk about two ways for approximate search by residual quantization.For the exact near neighbor query (ENN), we summarize two traditional pruningmethods respectively based on cell approximation and hyper-plane, and then introduce anew method based on cell-distance which is simple and powerful, with enoughsupporting experimental results. Finally, this thesis summarizes the law of indexingmethods based on VQ, and proposes some possible improving ways.