TY - GEN

T1 - Tell me who i am

T2 - SPAA 2006: 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures

AU - Alon, Noga

AU - Awerbuch, Baruch

AU - Azar, Yossi

AU - Patt-Shamir, Boaz

PY - 2006/10/16

Y1 - 2006/10/16

N2 - We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes or dislikes each object. However, the players do not know their preferences. To find his preference of an object, a player may probe it, but each probe incurs unit cost. The goal of the players is to learn their complete preference vector (approximately) while incurring minimal cost. This is possible if many players have similar preference vectors: such a set of players with similar "taste" may split the cost of probing all objects among them, and share the results of their probes by posting them on a public billboard. The problem is that players do not know a priori whose taste is close to theirs. In this paper we present a distributed randomized peer-to-peer algorithm in which each player outputs a vector which is close to the best possible ap proximation of the player's real preference vector after a polylogarithmic number of rounds. The algorithm works under adversarial preferences. Previous algorithms either made severely limiting assumptions on the structure of the preference vectors, or had polynomial overhead.

AB - We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes or dislikes each object. However, the players do not know their preferences. To find his preference of an object, a player may probe it, but each probe incurs unit cost. The goal of the players is to learn their complete preference vector (approximately) while incurring minimal cost. This is possible if many players have similar preference vectors: such a set of players with similar "taste" may split the cost of probing all objects among them, and share the results of their probes by posting them on a public billboard. The problem is that players do not know a priori whose taste is close to theirs. In this paper we present a distributed randomized peer-to-peer algorithm in which each player outputs a vector which is close to the best possible ap proximation of the player's real preference vector after a polylogarithmic number of rounds. The algorithm works under adversarial preferences. Previous algorithms either made severely limiting assumptions on the structure of the preference vectors, or had polynomial overhead.

KW - Billboard

KW - Collaborative filtering

KW - Electronic commerce

KW - Probes

KW - Randomized algorithms

KW - Recommendation systems

UR - http://www.scopus.com/inward/record.url?scp=33749539431&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33749539431&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:33749539431

SN - 1595934529

SN - 9781595934529

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 1

EP - 10

BT - SPAA 2006

Y2 - 30 July 2006 through 2 August 2006

ER -