15. A method of learning a similarity function for rare queries, the method comprising: determining training data based in part on user behavior data, the training data including similar and dissimilar query pairs; determining n-grams from own content of queries in the training data; mapping the n-grams in the training data into vectors represented in an n-gram space, each unique one of the n-grams being represented as an orthogonal dimension of the n-gram space; learning a similarity function using at least a subset of the training data, wherein the learning includes optimizing an objective function, the similarity function based at least in part on a similarity measurement in a transformed n-gram space having one or more of the unique n-grams being non-orthogonal with respect to one or more other of the unique n-grams, the objective function based at least in part on the transformed n-gram space; determining a family of hash functions in the n-gram space that are based on the transformed n-gram space; indexing queries from a collection of queries into sets of similar queries utilizing the family of hash functions; receiving a rare query; calculating an index for the rare query utilizing the family of hash functions; and identifying an associated one of the sets of similar queries based on the index.
16. A method as recited in claim 15 , the method further comprising: applying a ranking function to rank the associated set of similar queries in an order based on relevance to the rare query, the ranking function being based in part on the similarity function; and providing the associated set of similar queries in the order.