Uncovering Semantic Similarities between Query Terms


September 8, 2004


Nicole Immorlica


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.


Nicole Immorlica

Nicole Immorlica is an assistant professor in the theoretical computer science group at Northwestern University. She joined Northwestern in September 2008 after postdoctoral positions at Microsoft Research in Redmond, WA, and Centruum voor Wiskunde en Informatica (CWI) in Amsterdam, Netherlands. She received her Ph.D. from MIT 2005. Her work focuses on applying economic and computer science techniques to problems at the forefront of computer science research, including models of diffusion on social networks, the design and analysis of ad auction markets, and the development of general auction mechanisms.