Patent ID: 8510311

Claim:
A pattern search apparatus comprising: a computing system that executes computer-executable components stored in a non-transitory memory, the computer-executable components comprising: a storage unit configured to store a plurality of training patterns having d dimensions, where d is an integer; a distribution acquisition unit configured to obtain a cumulative probability distribution representing a cumulative probability of existing probabilities of the plurality of training patterns on an arbitrary dimensional axis of the d dimensions; a hash function unit configured to obtain a hash function to convert a value of an arbitrary point in a distribution section on the arbitrary dimensional axis corresponding to, in the cumulative probability distribution of the d dimensions, each of a plurality of probability sections which are obtained by dividing the cumulative probability distribution so that cumulative probability values of the plurality of probability sections become uniform in each dimension of the d dimensions, to a hash value corresponding to each of the plurality of probability sections; a training unit configured to obtain hash values of respective training patterns in the plurality of training patterns by using the hash function and to classify the respective training patterns into one or more buckets corresponding to the hash values; and a search unit configured to obtain a hash value of an input pattern by using the hash function and to perform a search of a training pattern most similar to the input pattern from a subset of the respective training patterns belonging to a bucket, of the one or more buckets, corresponding to the hash value of the input pattern.