Higher-dimensional Nearest Neighbor Search by Distributed Coding

In this paper we propose a fast approximate nearest neighbor search algorithm in a high dimensional spherical space using an idea called distributed coding which is to represent a vector by a set of many vectors and encode them efficiently. We implemented the algorithm and tested it with synthetic data. The results show that the proposed method exceeds a popular approximate nearest neighbor library, ANN in search time and accuracy in the case of higher-dimension and a large number of prototypes. Keyword Approximate Nearest Neighbor, Distributed Coding, k-d tree, Locality Sensitive Hashing 1. はじめに