APPROXIMATE NEAREST NEIGHBOR SEARCH METHOD, NEAREST NEIGHBOR SEARCH PROGRAM, AND NEAREST NEIGHBOR SEARCH DEVICE

摘要

PROBLEM TO BE SOLVED: To provide an approximate nearest neighbor search method which efficiently searches for the nearest neighbor data point by using a binary tree based on principal component analysis.;SOLUTION: When a nearest neighbor search device is provided with query vector data and an approximate nearest neighbor search database in which vector data is classified in hierarchical structure of a binary tree having first and second slave clusters corresponding to a principal component score, the device uses an initial value of a search target cluster for a cluster of a root node of the binary tree, corrects the query vector data by subtracting an average vector of the target cluster from the query vector, and represents an inner product of the corrected query vector and a first principal component vector acquired by performing principal component analysis on the target cluster, as a query principal component score for the target cluster. The device defines the first slave cluster as a search cluster when the query principal component score is equal to or less than zero, defines the second slave cluster as the search cluster when the query principal component score is positive, and continues searching until reaching the terminal hierarchy. The device determines vector data which belongs to the search cluster of the terminal hierarchy and has the shortest distance from the query vector, as the nearest data.;COPYRIGHT: (C)2013,JPO&INPIT