Techniques are described for determining queries that are similar to rare queries. An n-gram space is defined to represent queries and a similarity function is defined to measure the similarities between queries. The similarity function is learned by leveraging training data derived from user behavior data and formalized as an optimization problem using a metric learning approach. Furthermore, the similarity function can be defined in the n-gram space, which is equivalent to a cosine similarity in a transformed n-gram space. Locality sensitive hashing can be exploited for efficient retrieval of similar queries from a large query repository. This technique can be used to enhance the accuracy of query similarity calculation for rare queries, facilitate the retrieval of similar queries and significantly improve search relevance.