Sketching techniques for collaborative filtering
Yoram Bachrach, Ely Porat, Jeffrey S. Rosenschein · 2009
Recommender systems attempt to highlight items that a target user is likely to find interesting. A common technique is to use collaborative filtering (CF), where multiple users share information so as to provide each with effective recommendations. A key aspect of CF systems is finding users whose tastes accurately reflect the tastes of some target user. Typically, the system looks for other agents who have had experience with many of the items the target user has examined, and whose classifi-cation of these items has a strong correlation with the classifications of the target user. Since the uni-verse of items may be enormous and huge data sets are involved, sophisticated methods must be used to quickly locate appropriate other agents. We present a method for quickly determining the proportional intersection between the items that each of two users has examined, by sending and maintaining extremely concise “sketches ” of the list of items. These sketches enable the approxima-tion of the proportional intersection within a dis-tance of , with a high probability of 1 − δ. Our sketching techniques are based on random min-wise independent hash functions, and use very little space and time, so they are well-suited for use in large-scale collaborative filtering systems. 1