Back to results
US 8,510,311 B2Granted
Pattern search apparatus and method thereof
AssigneeKabushiki Kaisha Toshiba
InventorsTomoyuki Shibata, Osamu Yamaguchi, Toshikazu Wada
Life of this patent
Estimating the term…
Abstract
A pattern search apparatus includes a storage unit, a distribution acquisition unit, a hash function unit, a training unit, and a search unit. A cumulative probability distribution of the training pattern on an arbitrary axis is obtained, and hash function each of which divides a probability value are defined based on the cumulative probability distribution.
Claims11
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.
4 more elements
A pattern search method comprising:
- executing, by a computer, computer-executable instructions that cause the computer to perform operations, comprising:
- storing a plurality of training patterns having d dimensions, where d is an integer;
- obtaining 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;
- obtaining 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 are uniform in each dimension of the d dimensions, to a hash value corresponding to each of the probability sections;
- obtaining hash values of respective training patterns of the plurality of training patterns by using the hash function and classifying the respective training patterns as one or more buckets corresponding to the hash values;
- and
- obtaining a hash value of an input pattern by using the hash function and searching 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.
4 more elements
A program stored in a non-transitory medium capable of being read by a computer and causing the computer to implement functions including:
- storing a plurality of d-dimensional training patterns, where d is an integer;
- obtaining a cumulative probability distribution representing a cumulative probability of existing probabilities of respective training patterns of the d-dimensional training patterns on an arbitrary dimensional axis of d dimensions;
- obtaining 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 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;
- obtaining hash values of the respective training patterns by using the hash function and classifying the respective training patterns into one or more buckets corresponding to the hash values;
- and
- obtaining a hash value of an input pattern by using the hash function and searching 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.
3 more elements
Dependencies are inferred from the claim text.