Guest lecture: Improving performance and usability of web search engines
by Aristides Gionis from Yahoo! Research Barcelona
on Monday 2nd June at 14.15 in room B222 in Kumpula.
Abstract: In this talk we will discuss problems arising in the context of web search engines. We will first discuss trade-offs in designing efficient caching systems. We explore the impact of different approaches, such as static vs. dynamic caching, and caching query results vs. caching posting lists. We then present a new algorithm for static caching of posting lists, which outperforms previous methods, and we explore its trade-offs using a query log spanning a whole year.
We will then turn to the problem of query recommendation. We introduce the problem of query decomposition, where we are given a query, and we want to produce a small set of queries whose union of resulting documents corresponds approximately to that of the original query. Ideally, these queries should represent coherent, conceptually well-separated topics. We first show how this problem can be instantiated as a specific variant of a set cover problem, for which we provide an efficient greedy algorithm. Next, we show how the same problem can be seen as a constrained clustering problem, for which we develop a two-phase algorithm based on hierarchical agglomerative clustering followed by dynamic programming. Our experiments, conducted on a set of actual queries in a Web scale search engine, confirm the effectiveness of the proposed solutions.
Welcome!