I made a similar question asking about distance between documents (Wikipedia articles, news stories, etc.).  I made this a separate question because search queries are considerably smaller than documents and are considerably noisier.  I hence don't know (and doubt) if the same distance metrics would be used here.  Either vanilla lexical distance metrics or state-of-the-art semantic distance metrics are preferred, with stronger preference for the latter.
What are some standard ways of computing the distance between individual search queries?
machine learning;nlp;search
From my experience only some classes of queries can be classified on lexical features (due to ambiguity of natural language). Instead you can try to use boolean search results (sites or segments of sites, not documents, without ranking) as features for classification (instead on words). This approach works well in classes where there is a big lexical ambiguity in a query but exists a lot of good sites relevant to the query (e.g. movies, music, commercial queries and so on).Also, for offline classification you can do LSI on query-site matrix. See Introduction to Information Retrieval book for details.