Sketching Techniques for Collaborative Filtering

1 Introduction

Recommender systems attempt to provide a user with recommendations regarding information items that she is likely to find interesting. Recommender systems have been applied to many domains, such as books, music, videos, images, web pages, and news. Such systems maintain a profile of each user, and compare it to certain reference characteristics. Sometimes these characteristics are obtained from the information item itself, in an approach called the content based approach, and sometimes from information kept regarding the tastes of other users, in the collaborative filtering approach.

Collaborative filtering (CF) makes predictions about the tastes of a user (filtering) through collaboration among multiple agents, each tied to a specific user (because each user has Jeffrey S. Rosenschein The Hebrew University Jerusalem, Israel jeff@cs.huji.ac.il an agent, we will sometimes use the terms interchangeably). These CF systems predict whether a certain item is likely to interest the target user under the assumption that users whose past tastes are similar to the target user are likely to give a good prediction regarding the future tastes of the target user. Typically, CF systems operate in two steps. First, they seek users who share similar rating patterns with the target user. Second, they use the ratings from those like-minded users found in the first step to generate a prediction for the target user. Real-world CF systems need to handle huge volumes of information, as the universe of items is enormous, and there are many users.

Given a target user, we want to find another user who has rated many of the items the target user has rated. Also, it is likely that the prediction would be better if items rated by both users are a significant proportion of the items rated by either user. For example, it may be the case that two users have 100 songs that both have rated, but each of them has rated 10,000 songs. In this case, these 100 songs constitute only 1% of the songs each user has rated, so it harder to use the ratings of the first to understand the tastes of the second.

We propose methods for approximating the proportional intersection (PI) between the items that each of two users has rated. Our methods are very accurate, returning an approximately correct answer with very high probability, but require little information to be stored or sent. These methods thus provide a useful building block for CF systems. Our algorithms use sketching techniques, which construct an extremely concise representation of the items a user has rated, called a sketch. Rather than storing, transmitting, and processing the entire list of rated items, our algorithms operate on these extremely concise sketches, which are designed to enable a good approximation of the PI. Our algorithms use sketches based on random min-wise independent hash functions. We analyze the proposed methods via sampling techniques and Hoeffding's inequality to calculate the required sketch size given the desired accuracy and confidence for the PI's size. This analysis shows that very small sketch sizes are indeed sufficient to achieve high levels of accuracy and success probabilities.

2 Problem Statement

We now formally define the problem of computing the proportional intersection (PI) between two sets. We attempt to model a simple collaborative filtering domain. In this case, each user of the CF system has a set of items she has rated. A certain user, Alice, asks the CF system to give a prediction for a certain item she has not examined. In order to provide Alice with a good prediction, we must first find users who have rated many items that Alice has also rated. It is also desirable to find users such that the number of items rated by both Alice and any of these users are a significant proportion of the items rated by either of them. We call the proportion of items rated by two users out of all items rated by each of them the proportional intersection (PI). After finding users with a high PI to Alice's items, the CF system could use the ratings of these users to build a prediction for Alice. A naive way to do this is to keep the entire list of rated items for each user on a central server. However, this is undesirable, as the universe of items is very large, and there are a huge number of users, each of whom has ratings for a significant number of items.

One solution for handling the size of the data sets is compressing the lists of rated items using some known compression method. We are interested in achieving a much shorter description of the items list than compression techniques could enable. Such a concise description is called a sketch. We aim to design a sketch that would allow us to discover the PI with target users, and that would be as small as possible. Thus, we are willing to accept some inaccuracy when finding users with a high PI, and we are willing to accept some probability of error. Given target accuracy ϵ > 0 and a target confidence δ, our method must return an approximation ˆx to the actual PI x, such that with probability of at least 1 -δ the approximation is accurate enough, so |ˆx-x| ≤ ϵ. Obviously, the size of the sketch would depend on both ϵ and δ, and we wish it to be as small as possible.

We now consider two users, Alice and Bob, and formally define proportional intersection and the sketching technique. We denote by C1 the set of items Alice has rated, and by C2 the set of items Bob has rated. These items are taken from a large universe U of items (U is several orders of magnitude larger then C1 and C2). For now, we will assume that |C1| = |C2| = n (for example, the n items each user has rated most recently). We denote C1 ∩ C2 = T .

Under our sketching model, we only maintain the sketches of the rated item lists. Thus, all we have available are the sketches S1 of C1, and S2 of C2. A sketching framework is designed to allow for the approximation of the PI between any two users with a target confidence and accuracy. Let C1,C2, . . . ,Cm be the rated item lists of the users, and S1, S2, . . . , Sm be their sketches. We currently assume that for any i, j we have |Ci| = |Cj|. Consider any two users, i and j, and denote the PI pi,j = |Ci∩Cj | |Ci| = |Ci∩Cj | |Cj| .

Definition 2. A PI sketching framework with confidence δ and accuracy ϵ maintains only S1, S2, . . . , Sm, and for any two users, ai and aj, allows for the computation of pi,j with accuracy of at least ϵ and with confidence of at least δ. That is, the framework returns an approximation ˆ pi,j to pi,j such that with probability of at least 1 -δ we have |pi,j - ˆ pi,j | ≤ ϵ.

The following sections suggest a technique that enables the building of a PI sketching framework.

3 Sketches for Approximating Proportional Intersection

Consider again Alice and Bob, with the set C1 of items that Alice has rated, and the set C2 of items that Bob has rated (from the universe U of items). Again, we denote |C1| = |C2| = n and C1 ∩ C2 = T, and denote |T| = t. A straightforward method of generating a sketch for the items of each user is simply sampling some r random items. This generates a sketch Sr 1 for C1 and Sr 1 for C2; each such sketch is just a set of r items. We can estimate p1,2 = |C1∩C2| |C1| by computing ˆ p1,2 = |Sr 1 ∩Sr 2 | r . However, for the sketch to be small, we must use small values of r. The probability for each item fromC1 to appear in Sr 1 is r n-r+1 . To note that a certain item is in both C1 and C2, it must appear in both Sr 1 and Sr 2 , and since r is small, this happens with very low probability.

When r = 1, for example, S1 1 is simply a random item from C1, and S1 2 is a random item from C2. In order to have an item in S1 1 ∩S1 2 , the item chosen from C1 to be in S1 1 must be in T (out of the n items in C1 there are only t such items), and the same item must be chosen from C2 to be in S1 2 . Thus, the probability of having an item in S1 1 ∩ S1 2 is 1t · 1n , which is very small. Consider, however, the case where the sketch S1 is the minimal item from C1, and S2 is the minimal item from C2. If the minimal item in C1 ∪C2 is in T , we are guaranteed to have an item in S1 ∩ S2. Of course, always using the minimal item would always generate the same S1 and S2, regardless of the PI that we are estimating. We overcome this by using min-wise independent functions.

Let H be a family of functions over the same source X and target Y , so each h ∈ H is a function h : X → Y , where Y is a completely ordered set. We say that H is min-wise independent if, when randomly choosing a function h ∈ H, for any subset C ⊆ X, any x ∈ C has an equal probability of being the minimal after applying h. 1

Definition 3. H is a min-wise independent family, if for all C ⊆ X, for any x ∈ C,

[Indyk, 2001] shows that it is possible to construct minwise independent families of hash functions such as the ones we require here, so from this point on we use these results. 2

We now use integers to define the identity of items in U (where |U| = u), so any subset C ⊆ U is simply a list of |C| integers in [u] (we use [u] to denote {1, 2, . . . , u}). Thus,

1 We must choose h from H under a certain distribution. We will assume that h is chosen uniformly from H, although any distribution for choosing a member of h that would make H min-wise independent would do.

2 Although we use Indyk's results, and assume it is possible to construct such families of min-wise independent hash functions, we do note that in fact for most practical applications it is possible to use any approximately uniform hash function, or even pairwise independent hash functions, and still obtain very good results.

Alice's rated items are C1 ⊆ [u], and Bob's rated items are C2 ⊆ [u]. We continue to denote |C1| = |C2| = n and C1 ∩ C2 = T, and |T| = t.

Let H be a family of min-wise independent functions from [u] to [n2 ] (so each h ∈ H is a function h : [u] → [n2 ]). Note that the domain of each hash function in the family is an integer in the very large range of [u], but the hashed values are in the much smaller range of [n2 ]. The reason we use a range of n2 integers rather than just n integers is to mitigate the effect of collisions in the hashed values. 3 The complete construction of min-wise independent families is fully explained in [Indyk, 2001], but for the purpose of understanding the current work it is only required to know that for any u and n << u it is possible to construct a min-wise independent family of functions mapping from [u] to [n2 ].

Let h ∈ H be a randomly chosen function from H. We can apply h on all the integers in C1 and examine the minimal integer we get, mh1 = minx∈C1 h(x). We can do the same to C2 and examine mh2 = minx∈C2 h(x). We now compute the probability that m1 = m2: Prh∈H[mh1 = mh2 ] = P rh∈H [minx∈C1 h(x) = minx∈C2 h(x)].

Proof. For brevity, we denote p = p1,2. We use the size of the PI between Alice and Bob, p = p1,2, to compute that probability. C1 contains n items, p · n are items that are also present in C2, and (1-p) ·n that are not. C2 contains n items, p·n are items that are present in C1, and (1-p) ·n that are not. In total C1∪C2 contains p·n+2·(1-p)·n = pn+(2-2p)n = n(2 - p) items. When an item in T is minimal under h, i.e., for some a ∈ T we have h(a) = minx∈C1∪C2 h(x), we get that minx∈C1 h(x) = minx∈C2 h(x). Since H is min-wise independent, we get that Prh∈H[mh1 = mh2 ] = pn n(2-p) = p 2-p .

Building a PI sketching framework requires us to generate sketches that would allow us to get good estimates for the PI between any two users, p = pi,j. We note that given α = Prh∈H[mh1 = mh2 ] for Alice and Bob, we can easily obtain the PI between them, p1,2. Since α = p1,2 2-p1,2 , we get that (2 -p)α = p, so p = 2α-αp, and thus p = 2α 1+α . Therefore, the problem of estimating the PI is reduced to estimating α.

Our suggested approximation algorithm relies on generating sketches based on a random sample of several such functions from the min-wise independent family H. The sketches are then used to approximate α, and thus approximate the PI.

3 [Indyk, 2001] shows how to construct an approximately minwise independent family of hash functions where the source and target are the same space, i.e., each h ∈ H is a function h : [m] → [m]. To construct a min-wise independent family of functions from [u] to [n2 ], we first apply an approximately uniform hash function h′ : [u] → [n2 ], and then apply the functions from the min-wise independent family from [n2 ] to [n2 ] which can be constructed using the methods in [Indyk, 2001]. Since |Ci| = n but h′ has a range of n2 , due to the Birthday Paradox principle, the probability of a collision (i.e., having x ̸= y ∈ Ci such that h′ (x) = h′ (y)) is very small, let alone a collision that occurs with the specific element we examine. For further details, see [Indyk, 2001].

We first define the sketches we use. Let vk = 〈h1, h2, . . . , hk〉 be a tuple of k randomly chosen functions from the min-wise independent family H. Let Ci be the set of items ranked by agent ai. We now define the sketch for Ci given vk. We first denote the minimal item in Ci under hj as mhj i =minx∈Ci hj(x).

Definition 4. The Hk sketch of Ci, S(Ci), is the list of minimal items in Ci under the k randomly chosen functions from h: Sk (Ci) = (mh1 i ,mh2 i , . . . ,mhk i ).

When k, the number of randomly chosen functions from H, is known, we simply write S(Ci) rather than Sk (Ci). We now show how to use the sketches of C1 and C2 to estimate the PI between them.

3.1 Estimating the Proportional Intersection, Given Sketches

We first note that due to Theorem 1, randomly choosing a function h ∈ H and testing whether mh1 = mh2 is in fact a Bernoulli trial, with a success probability of α = p1,2 2-p1,2 . We define the random variable of this Bernoulli trial as:

Given the sketches Sk (C1) = (mh1 1 ,mh2 1 , . . . ,mhk 1 ) and Sk (C2) = (mh1 2 ,mh2 2 , . . . ,mhk 2 ) we can easily test (for each i ∈ {1, . . . , k}) whether mhi 1 = mhi 2 , and obtain the results of k such Bernoulli trials.

Lemma 1. Let h1, . . . , hk be a set of k randomly-sampled functions from the min-wise independent family H, and X1 = Xh1 , . . . ,Xk = Xhk be the series of k Bernoulli trials, as defined above. Let X be the number of successes in this series of Bernoulli trials, X = ∑kj=1 Xj. Then the maximum likelihood estimator for α = p1,2 2-p1,2 is: ˆα = Xk . This estimator is unbiased.

Proof. Each suchXj is a single Bernoulli trial, andPr(Xj = 1) = α and Pr(Xj = 0) = 1 - α. X1, . . . ,Xk is a series of k such Bernoulli trials. X is the number of successes in this series of Bernoulli trials, X = ∑kj=1 Xj, and thus has the binomial distribution X ∼ B(k, α). Since the Xj's are independent (as H is min-wise independent) but identical Bernoulli trials, the maximum likelihood estimator for α is ˆα = Xk . This estimator is known to be unbiased for the binomial distribution.

The estimator ˆα by itself does not provide a bound on the probability that this value is approximately correct. Moreover, we are interested in approximating p1,2, and not α. We begin by obtaining an estimate for α which is probably approximately correct (PAC) using the sample X1, . . . ,Xk of these k Bernoulli trials, and later handle deriving a probably approximately correct estimate for p1,2. As mentioned in Definition 2, if for some ϵ > 0, we consider values that are within a distance of ϵ from the correct value, p1,2, accurate enough, and are willing to accept a certain low probability δ of having our estimator miss it by more than ϵ, we can derive the appropriate number of functions k to use in the sketch. Obviously, larger values of k would increase our accuracy and confidence, but will of course increase the sketch size, which we want to minimize. The next section analyzes the sketch size, i.e., the required k, given the target confidence and accuracy.

4 Sketch Size Analysis

We now attempt to derive the necessary sketch size, k, that is required in order to build a PI sketching framework. We can formulate this problem as building a confidence interval for the PI, pi,j, with an accuracy of ϵ and with confidence level of 1 - δ. The interval we build is: [ ˆ pi,j - ϵ, ˆ pi,j + ϵ].

The interval is centered in ˆ pi,j, has a width of 2 · ϵ > 0, and contains the true pi,j with a probability of at least 1 - δ. To achieve the desired accuracy and confidence, the sketch size k must be long enough. To find the appropriate k, we must obtain an equation to tie together the required k, the confidence level δ, and the accuracy ϵ. Our analysis is based on Hoeffding's inequality [Hoeffding, 1963].

Theorem2 (Hoeffding's inequality). Let X1, . . . ,Xn be independent random variables, where all Xi are bounded so that Xi ∈ [ai, bi], and let X = ∑ni=1 Xi. Then the following inequality holds.

We now use Hoeffding's inequality to derive the required sketch size for a desired confidence and accuracy regarding α = p 2-p , and then show how to find the sketch size for a confidence and accuracy regarding p. Let h1, . . . , hk be a set of k randomly-sampled functions from the min-wise independent family H, and X1 = Xh1 , . . . ,Xk = Xhk be the series k of Bernoulli trials, as defined above. Again, let X = ∑kj=1 Xj, and take ˆα = Xk as an estimator for α. All Xi are either 0 or 1 (and are thus bounded between these values), and E[X] = k · α. Thus, the following holds: Pr(|X-kα| ≥ kϵ) ≤ 2e-2 k ϵ2 . Therefore the following also holds: Pr(|ˆα - α| ≥ ϵ) ≤ 2e-2k ϵ2 . We now compute the number of required samples in order to make sure that this probability is below some required confidence level δ. 4

Theorem 3 (Sketch Size for Approximating α). For any required accuracy ϵ > 0 and required confidence level 1 - δ, we can construct a confidence interval for α with width 2ϵ of the form: [ˆα- ϵ, ˆα+ ϵ].

This interval holds the correct α with probability of at least 1-δ. The required sketch length (or equivalently, the required number of samples) to perform this is k = ln 2 δ 2 ϵ2 . Equivalently, given k samples and a required confidence of 1 - δ, the following is a confidence interval for α, with the required confidence level of 1 - δ: [ ˆα- √ 1 2k ln 2δ , ˆα+ √ 1 2k ln 2δ ].

4 Such computations are widely used for the analysis of randomized algorithms in various areas. For example, PAC learning algorithms are usually based on similar techniques.

Proof. We use Hoeffding's inequality to make sure the error does not exceed our target confidence level δ, and get: Pr(|ˆα - α| ≥ ϵ) ≤ 2e-2k ϵ2 ≤ δ. We extract ϵ and k: -2k ϵ2 ≤ ln δ2 . Equivalently: ϵ2 ≥ - ln δ2 2k . Finally we get the following equations: ϵ ≥ √ 1 2k ln 2δ and k ≥ ln 2 δ 2 ϵ2 .

The above sketch size analysis was for obtaining an approximation for α, and not for pi,j. However, due to Theorem 1 we have pi,j = 2α 1+α . We are interested in building a PI sketching framework, with confidence 1 - δ and accuracy ϵ for pi,j. We now show that by taking a sketch size that allows building a confidence interval for α with width of ϵ′ = ϵ3 and confidence δ, we obtained the required accuracy of ϵ and confidence of δ for pi,j.

Theorem 4 (Sketch Size for Approximating pi,j). A PI sketching framework with accuracy ϵ and confidence δ can be obtained by using a sketch size of: k = ln 2 δ 2 ϵ2 9 .

Proof. For brevity we denote p = pi,j. Due to Theorem 1, we have p = 2α 1+α . Denote by k the sketch size required for obtaining an estimate ˆα for α, with accuracy of ϵ′ and confidence 1 - δ, as can be derived from Theorem 3. By using sketches of size k, we obtain an estimate ˆα such that with probability 1-δ we have ˆα-ϵ′ < α < ˆα+ϵ′ . We use the following as an estimator for p: ˆ p = 2 ˆα 1+ˆα . We now analyze how good this estimator for p is. Since ˆα - ϵ′ ≤ α ≤ ˆα + ϵ′ , we obtain the following equations: 2ˆα2ϵ′ ≤ 2α ≤ 2ˆα+2ϵ′ and ˆα - ϵ′ + 1 ≤ α + 1 ≤ ˆα + ϵ′ + 1.

Thus we have: p ≥ 2ˆα-2ϵ′ ˆα+ϵ′+1 ≥ 2ˆα ˆα+ϵ′+1 - 2ϵ′ ≥ ˆ p - 3ϵ′ . Similarly, we can show that: p < ˆ p + 3ϵ.

Note that we need only handle the case where ϵ′ < ˆα. Our suggested method uses a sketch size and computes an estimation for the PI, ˆα, using the sketches. The sketch size used is determined by the required approximation accuracy, as defined by ϵ (or ϵ′ ). If the computed ˆα (our estimation of the PI) is so small that ˆα < ϵ′ , we can simply output ˆ p = ϵ as our estimation (which for the required accuracy of ϵ would be accurate enough).

We also note that: 5

Earlier we have shown that: p ≤ 2ˆα+2ϵ′ ˆα-ϵ′+1 = 2 ˆα ˆα-ϵ′+1 + 2ϵ′ ˆα-ϵ′+1 . Thus we obtain: p ≤ 2ˆα ˆα-ϵ′+1 + 2ϵ′ ˆα-ϵ′+1 ≤ ˆ p + 3ϵ′ . We have now shown that: ˆ p - 3ϵ′ ≤ p ≤ ˆ p + 3ϵ′ . Thus, by using ϵ′ = ϵ3 in the formula of Theorem 3, we obtain the desired accuracy of ϵ for p, rather than for α.

We now note that a similar approach, using similar transitions, can be used even if the set sizes of user items are similar but not identical. However, if these sets are vastly different in sizes, a different method must be used.

5 Applications in Collaborative Filtering Systems

We now examine the applicability of the above results to collaborative filtering systems. Our sketches require k log n bits per agent. Although k does not depend on the number of items each agent has ranked, n, it does depend on the desired confidence and accuracy.

Consider a recommender system for items in a large Internet music store, that holds over |U| = 100,000,000 music video clips. Each integer in that range requires 27 bits to represent. In such a system we may obtain direct rankings for clips by users, or infer them using the number of times a user has watched a clip, or the amount of time spent watching it. We assume each user has watched 10,000 clips. 6 The range of our hash functions is n2 , so we require 2 log 10,000 = 27 bits to represent each integer in this range. We use values of ϵ = 0.2, and δ = 0.1, which allow obtaining a moderately good estimation of the PI, with a pretty high probability. Using Theorem 4, we obtain the required sketch size of k = 337. Thus, a list of a user's clips requires 27·10,000 = 270,000 bits, whereas a sketch only requires 337 · 27 = 9099 bits. Since there are millions of users, this is a significant improvement. Another example is personalized web search. 7 Consider a recommender system for web pages, which suggests to users websites that were frequently visited by similar users. In this case, we deal with a much larger universe of

5 In the second-to-last transition we again use the fact that ϵ′ < α.

6 This is a large number, which might be appropriate for heavy users after several years of using the system, but it is still several orders of magnitude smaller than the total number of clips.

7 We thank an anonymous reviewer for pointing out this interesting application.

30,000,000,000 items, 8 so each item requires 35 bits to represent. Assuming that we have a list of 10,000 pages ranked per user (similarly to the previous example), a list representation would require 350,000 bits per user. Since the sketch size only depends on ϵ, δ and the number of items with which each user has interacted, the sketch size remains 9099 for this case as well, yielding an even more significant improvement.

6 RelatedWork

There are many examples of CF systems. An early example is Tapestry [Goldberg et al., 1992], which relied on information manually inserted by users. Early systems with automated predictions were GroupLens [Resnick et al., 1994] and Ringo [Shardan and Maes, 1995]. CF algorithms use correlations between human preferences to predict future preferences. [Resnick et al., 1994] used the Pearson correlation coefficient, while [Shardan and Maes, 1995] examined several other measures.

This paper tackles the problem of handling the massive data sets in CF systems. A difficult step in generating a prediction for a target user is finding other users who share ranked items with the target user. We formulated this problem as computing the PI between the users' ranked items. Rather than maintaining the full lists of ranked items, we only maintain much shorter "sketches" that allow approximating the PI. Several papers deal with sketching. Massive data streams are fundamental to data processing applications; the increasing size of data sets has triggered the need for improved algorithms for processing huge inputs. Typically, papers that propose sketching techniques operate on large strings, and sketches are used to approximate various relations between strings. Much of that research considers the streaming model, where an algorithm can only make one pass over the data and, due to memory constraints, can only maintain a small sketch for further processing and queries. [Feigenbaum et al., 2002] presents a sketch for approximating the L1 -difference between two streams, and [Cormode et al., 2003] examines estimating the Hamming norm for massive data streams.

To the best of our knowledge, the current paper describes the first research that uses such sketching techniques to allow CF systems to handle massive data sets. Our methods are based on using a min-wise independent family of hash functions. Such functions have been used in the data stream model; families of this type have been studied in [Broder et al., 2000; Mulmuley, 1996; Indyk, 2001]. Another application of such functions is estimating rarity of items and similarity over data stream windows [Datar and Muthukrishnan, 2002]. Our methods are similar to several other articles regarding Locally Sensitive Hashing (LSH) [Gionis et al., 1999; Andoni and Indyk, 2008]. Our technique is an adaptation of the LSH framework for the specific case of CF systems. We focused on estimating PI, and provided bounds using current theoretical methods, based on assumptions regarding the CF scenario. There exist several other techniques of a similar nature. Random Projection methods, such as

8 Measuring the exact number of webpages on the Internet is a very difficult task, however we believe 30 billion is in the right order of magnitude.

[Achlioptas, 2003] embed n points in a high-dimensional space into a k-dimensional space, where k logarithmically depends on n, while preserving pairwise distances up to a small factor. However, our technique is more tailored towards CF and computing the PI. Semantic Hashing [Salakhutdinov and Hinton, 2008] chooses codes for datapoints such that the Hamming distance between the codes correlates with the degree of semantic similarity between them. A similar approach, Spectral Hashing, is examined in [Weiss et al., 2008], where it is shown that finding the optimal Semantic Hash code is NP-Hard. Although Spectral Hashing is computationally feasible, it still involves non-trivial computations of matrix thresholded eigenvectors of the graph Laplacian, whereas our approach is much simpler, and computationally efficient.

7 Conclusion

A major challenge in CF systems is the huge amount of information to be handled. A key building block of CF systems is finding users who share many ranked items. We formulated this problem as computing the PI, and suggested a sketching technique that allows doing so in an enormous universe of items, and with huge volumes of information regarding such rankings. Our method is based on concise sketches. To achieve a small sketch size, we sacrifice the exact computation of the PI, and only approximate it with a given accuracy and success probability. The sketch size is logarithmic in the desired confidence, and polynomial in the desired accuracy, remaining small even when the confidence and accuracy are high. Our method thus allows building scalable CF systems.

Much work remains open for future research. First, our methods only allow finding users with a high PI of ranked items with those of the target users. A CF system must also check for correlations between the users' rankings, and offer good recommendations based on this information. For a full solution, one must show how to tractably perform these steps for massive data sets. Second, we only analyzed the required sketch size theoretically. We believe empirical tests of our methods, using real data sets or using simulations, would allow us to improve the sketch size used, which could be of importance in real-world applications. Finally, we have focused on uses of our methods for CF systems, but we believe these methods are general. Future research could reveal other applications for these methods, for example in trust and reputation systems.

Acknowledgment

This research was partially supported by Israel Science Foundation grant #898/05.