Contact: Dan-Cristian Tomozei
Recently, many large companies (Amazon, Netflix, Google, etc.) have manifested a vivid interest in producing personalized recommendations for their users. Such companies maintain powerful servers running centralized algorithms, that use large databases of ratings (in the order of hundreds of millions) issued by users for items on offer in order to generate recommendations. Due to the very large instances of the problem, an acceptable trade-off between the computational complexity of the algorithms and their performance needs to be reached. Moreover, privacy concerns arise, since sensitive user data are stored on the companies’ servers.
An alternative approach is to generate recommendations in a distributed fashion. In this approach, each user maintains a so-called profile (i.e., a vector of coordinates in a certain profile space), that she computes via message exchanges with her friends (trusted users). The profiles are computed such that the proximity of two users in the profile space implies that their tastes are similar. A simple scheme for generating cooperative recommendations can then be envisioned where neighbors issue votes for items weighted according to their pre-computed profiles.
The aim of this project is to evaluate distributed methods for computing such user profiles for various classes of friendship graphs (typically small world, such as Kleinberg’s model, Watts-Strogatz, etc.).
Refs:
Satish Babu Korada, Andrea Montanari, Sewoong Oh. Gossip PCA. arXiv. To appear in ACM Sigmetrics’11
J. Kleinberg. Navigation in a Small World. Nature 406(2000), 845.