Candidate Talk: New Algorithmic Ideas for Search, Ads, and Recommendations.

February 8, 2008
Yury Livshits | California Institute of Technology

Similarity search is the problem of preprocessing a database of N objects in such a way that given a query object, one can effectively determine its nearest neighbors in database. Similarity search underlies many algorithmic problems in the web. In particular it is used in

Behavioral targeting: Searching for the most relevant advertisement for displaying to a given user.
“Best match search”: Searching resumes, jobs, dating mathing, cars, apartments.
Personalized news aggregation: Searching for news articles that are most similar to the user’s profile of interests

The combinatorial approach to similarity search will be presented.
Namely, we show how the problem can be solved when similarity measure does not satisfy triangle inequality.
In the second part we outline a new direction:
the role of social networks in similarity search algorithms.

Speaker Details

Yury Lifshits (http://yury.name) obtained his PhD degree from Steklov Institute of Mathematics at St.Petersburg (2007). He is currently a postdoc at Caltech. He won two gold medals at International Mathematical Olympiads, received The Best Paper Award in Application Track of CSR’07 and The Yandex Teaching Award (2006) for his course “Algorithms for Internet”. Yury is a maintainer of “The Homepage of Nearest Neighbors”: http://simsearch.yury.name Recently he published an overview of similarity search as a Youtube video lecture: http://www.youtube.com/watch?v=MsRTrO_p6yE