1. A similarity calculation system for increasing the efficiency of a computer when performing searching, comprising: at least one processor; and at least one memory device that stores a plurality of instructions, which when executed by the at least one processor, causes the at least one processor to operate to: acquire a query vector; acquire a plurality of target vectors; calculate a similarity between each of the plurality of target vectors belonging to any one of the plurality of clusters and the query vector, calculate, for each of the plurality of target vectors, a calculation amount to be estimated when calculating the similarity between the each of the plurality of target vectors and the query vector, cluster the plurality of target vectors based on the calculation amount to be estimated for each of the plurality of target vectors, wherein, in the calculation, the processor calculates a number of non-zero elements of each of the plurality of target vectors as the estimated calculation amount, wherein, in the clustering, the processor clusters the plurality of target vectors so that a difference in a total sum of the calculated calculation amounts for all of the plurality of target vectors belonging to each of the plurality of clusters among the plurality of clusters decreases, wherein, in the clustering, the processor clusters the plurality of target vectors by generating a graph comprising: a plurality of first nodes that correspond to each of the plurality of target vectors and that has the calculation amount estimated for a corresponding one of the plurality of target vectors as a weight, a plurality of second nodes corresponding to an element type of the plurality of target vectors, and a plurality of edges connecting each of the plurality of first nodes to any one of the plurality of second nodes, and by dividing the generated graph based on the weight of each of the plurality of first nodes.