Abstract Recommender systems attempt to highlight items that a target user is likely to fifind interesting. A common technique is to use collaborative fifiltering (CF), where multiple users share information so as to provide each with effective recommendations. A key aspect of CF systems is fifinding users whose tastes accurately reflflect 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 classififi- cation of these items has a strong correlation with the classififications of the target user. Since the universe 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 approximation of the proportional intersection within a distance of , with a high probability of 1 − δ. Our sketching techniques are based on random minwise independent hash functions, and use very little space and time, so they are well-suited for use in large-scale collaborative fifiltering systems