Search system, search method and program recording medium

A search method for a search for one or more “K” registered vectors which comprise a registered vector being most similar to an input vector and a registered vector being “K”-th most similar to the input vector, from among one or more registered vectors, the search method comprising performing:

• similarity calculation which is a calculation of a degree of a similarity between an input vector and a registered vector with respect to a plurality of registered vectors,
• determination of a threshold which is a height of the “K”-th highest degree of similarity among similarities calculated by the similarity calculation,
• with respect to a registered vector, of the plurality of registered vectors, to which the similarity is not yet calculated:
• calculation of a degree of partial similarity which is a degree of similarity between a portion of the input vector and a portion of the registered vector;
• limit calculation which is a calculation, based on the degree of partial similarity, of an upper limit of possible values of an expected degree of similarity;
• comparison between the upper limit of the registered vector and a threshold;
• determination, based on the comparison, whether to exclude the registered vector from a plurality of candidates for a result of the search,
• calculation, when the registered vector is not excluded, of a degree of similarity;
• and
• update, when the degree of similarity exceeds the height of the degree of similarity of any of the similarities calculated by the similarity calculation, of the threshold to a higher threshold;
• determination, with respect to another registered vector, of the plurality of registered vectors, to which the similarity is not yet calculated, of whether to exclude the another registered vector, using the higher threshold;
• wherein the processor is further configured to perform:
• repeat from a process of the degree of partial similarity calculation to a process of the determination of whether to exclude the registered vector based on the comparison between the upper limit of the registered vector and the threshold, while gradually increasing a variable number of “d”, the variable value of “d” representing a dimension number of the portion of the input vector and the portion the registered vector, until the value reaches “d=D”;
• wherein “D” is the dimension of the input vector and the registered vector.

A non-transitory computer-readable storage medium storing a program that causes a computer to perform a search method for a search for one or more “K” registered vectors which comprise a registered vector being most similar to an input vector and a registered vector being “K”-th most similar to the input vector, from among one or more registered vectors, the search method comprising performing:

• similarity calculation which is a calculation of a degree of a similarity between an input vector and a registered vector with respect to a plurality of registered vectors,
• determination of a threshold which is a height of the “K”-th highest degree of similarity among similarities calculated by the similarity calculation,
• with respect to a registered vector, of the plurality of registered vectors, to which the similarity is not yet calculated:
• calculation of a degree of partial similarity which is a degree of similarity between a portion of the input vector and a portion of the registered vector;
• limit calculation which is a calculation, based on the degree of partial similarity, of an upper limit of possible values of an expected degree of similarity;
• comparison between the upper limit of the registered vector and a threshold;
• determination, based on the comparison, whether to exclude the registered vector from a plurality of candidates for a result of the search,
• calculation, when the registered vector is not excluded, of a degree of similarity;
• and
• update, when the degree of similarity exceeds the height of the degree of similarity of any of the similarities calculates by the similarity calculation, of the threshold to a higher threshold;
• determination, with respect to another registered vector, of the plurality of registered vectors, to which the similarity is not yet calculated, of whether or not to exclude the another registered vector, using the higher threshold;
• wherein the processor is further configured to perform:
• repeating from a process of the degree of partial similarity calculation to a process of the determination of whether to exclude the registered vector based on the comparison between the upper limit of the registered vector and the threshold, while gradually increasing a variable number of “d”, the variable value of “d” representing a dimension number of the portion of the input vector and the portion of the registered vector, until the value reaches “d=D”;
• wherein “D” is the dimension of the input vector and the registered vector.