1. An information processing apparatus characterized by comprising: holding means for holding a plurality of sets of media and at least two feature amounts of the media in correspondence with each other; read means for reading out the at least two feature amounts from said holding means; input means for inputting a medium as a query; feature amount acquisition means for acquiring at least two feature amounts of the medium as the query; calculation means for calculating similarities between corresponding feature amounts of the at least two feature amounts read out by said read means, and the at least two feature amounts acquired by said feature amount acquisition means; weight calculation means for calculating weight values respectively for the similarities for respective feature amounts calculated by said calculation means on the basis of statistical amounts of the at least two feature amounts acquired by said feature amount acquisition means; similarity calculation means for calculating similarities between media corresponding to the at least two feature amounts read out by said read means, and the medium as the query, on the basis of results obtained by weighting the similarities for respective feature amounts calculated by said calculation means by the weight values calculated by said weight calculation means; and output means for outputting similar candidates for the medium as the query of the media held by said holding means on the basis of the similarities calculated by said similarity calculation means.