Fast Nearest-Neighbor Search Based on Voronoi Projections and Its Application to Vector Quantization Encoding

摘要

In this work, we consider two fast nearest-neighbor search methods based on the projections of Voronoi regions, namely, the box-search method and the cell-partition search method. We provide their comprehensive study in the contest of vector quantization encoding. We show that the use of principal component transformation reduces the complexity of Voronoi-projection based search significantly for data with high degree of correlation across their components.