A method and system for projecting queries and images into a similarity space where queries are close to their relevant images is provided. A similarity space projection (“SSP”) system learns a query projection function and an image projection function based on training data. The query projection function projects the relevance of the most relevant words of a query into a similarity space and the image projection function projects the relevance to an image of the most relevant words of a query into the same similarity space so that queries and their relevant images are close in the similarity space. The SSP system can then identify images that are relevant to a target query and queries that are relevant to a target image using the projection functions.