1. A method comprising: determining training data including queries; determining n-grams from own content of the queries; determining an n-gram space that represents the queries as one or more vectors in the n-gram space, each dimension of the n-gram space being independent and represented by a unique one of the n-grams; identifying similar query pairs and dissimilar query pairs of the queries based at least in part on user behavior data, wherein the user behavior data includes at least one of click-through data or session data; and learning a similarity function using the identified similar query pairs and the dissimilar query pairs in the training data, the similarity function based at least in part on a transform of the n-gram space, the transform resulting in a transformed n-gram space having one or more of the unique n-grams being dependent on one or more other of the unique n-grams.
2. A method as recited in claim 1 , wherein each query in the training data comprises a common query.