In this talk, we propose a new measure for the semantic similarity of query terms based on the statistical correlation of their frequency functions. We develop an efficient way to approximate this measure using standard dimensionality reduction techniques. This approximation can be computed online to build a data structure with significantly less space and query complexity than a brute-force approach. We use our techniques to analyze data from the MSN query logs, automatically uncovering several interesting similarities. This work has applications in ad auction keyword suggestion tools.