Usage context obtained from search query logs is leveraged to facilitate in discovery and/or similarity determination of key search phrases. A key phrase extraction process extracts key phrases from raw search query logs and breaks individual queries into a vector of the key phrases. A Similarity Graph generation process then generates a Similarity Graph from the output of the key phrase extraction process. Information relating to the similarity levels between two key phrases can be employed to restrict a search space for tasks such as, for example, online keyword auctions and the like. Thus, instances can be employed to find frequent misspellings of a given keyword, keyword/acronym pairs, key phrases with similar intention, and/or keywords which are semantically related and the like.