A theoretical analysis of query selection for collaborative filtering.

S. Dasgupta, W. S. Lee and P. M. Long. A theoretical analysis of query selection for collaborative filtering. Machine Learning, 51: 283-298, 2003.

(Available in Postscript and PDF formats.)

Abstract
We consider the problem of determining which of a set of experts has tastes most similar to a given user by asking the user questions about his likes and dislikes. We describe a simple and fast algorithm for generating queries for a theoretical model of this problem. We establish approximation guarantees for this and related algorithms.