approximate nearest neighbor searching apparatus, approximate nearest neighbor search method and program

摘要

By narrow down properly the number of nearest neighbor candidates, high search precision and speed We realize the approximate nearest neighbor search that combines. When a plurality of points represented by the vector data is inputted, the multi-dimensional space to calculate the index of the hash by applying a hash function to each point, which is divided into a plurality of regions by a bin of the multi-dimensional hash table and a database storage unit made by storing the multi-dimensional hash table each point by projecting each point within, when the query is entered, by applying the hash function to the query of the query in the space position is determined, determines an estimate of the distance between the regions in the query space, the search range determining unit for determining a region to be searched on the basis of the estimated value, and each point of the search area It calculates the distance to the query, recently to calculate the closest point to the query as a nearest neighbor of the query and a neighboring point determiner, the search range determining section is a representative point of the region by referring to the index for each area In seeking to determine the query and determines the estimated value based on a distance between the representative points, by applying the branch and bound method to be the search by excluding an area that can not become a region to be the search area approximate recently I apply a neighbor search device that.