Online advertising is the primary economic force behind numerous

Internet services ranging from major Web search engines to obscure forums. A new discipline - Computational Advertising - has recently emerged, which studies the process of advertising on the Internet from a variety of angles. A successful advertising campaign should be integral to the user experience and relevant to the users'information needs, as well as economically worthwhile to the advertiser and the publisher. This talk will survey the evolution of online advertising systems, and discuss the unique challenges posed by searching the ad corpus. At first approximation, finding user-relevant ads can be reduced to conventional information retrieval. However, the complex structure of ad campaigns along with the cornucopia of pertinent non-textual information makes ad retrieval substantially (and interestingly) different. We juxtapose ad retrieval with Web search and show how to adapt standard IR methods, in particular by augmenting the ad selection process with external knowledge. We demonstrate how to enrich query representation using Web search results, and thus use the Web as a repository of relevant query-specific knowledge. We will discuss how computational advertising benefits from research in many AI areas such as machine learning, machine translation, and text summarization, and also survey some of the new problems it poses.