Consistent Weighted Sampling Made Fast, Small, and Easy

Introduction

Web experiments have repeatedly shown that most breadth-first collections of pages contain many unique pages, but also contain large clusters of near-duplicate pages. Typical studies have found that duplicate and near-duplicate pages account for between a third and a half of a corpus.

Min-wise sampling has been widely used in Web and image search since the mid-nineties to produce consistent compact sketches which provide good estimates of pairwise similarity of corpus items, computing the sketch with reference only to a single item. Min-wise hashing computes a sketch for estimating the Jaccard (scaled L1) similarity effectively; SimHash , and related techniques compute sketches for estimating the angular separation (in L2) of arbitrary vectors. Both of these have been widely used in deployed commercial search engines to allow the search result pages to suppress reporting the near-duplicate pages which would otherwise often dominate the search results.

SimHash, by its nature, allows vector coordinates to be arbitrary real numbers, and weights the random projections accordingly. While min-wise sampling is designed for unweighted sets it can also be used for non-negative integer weights. For this one simply replaces any element $e$ of weight $w$ by $w$ elements $e_{1},\ldots,e_{w}$ of unit weight. This reduction however leads to the running time of computing one consistent sample to be proportional to the sum of all weights. More recent papers removed the integer weight restriction, and showed how to produce samples using a constant number of hash evaluations for any element, independent of its weight.

All these sampling techniques as described typically result in a Boolean random variable whose expectation is related to the similarity. One typically applies the same procedure repeatedly with independent randomness to produce a sketch consisting of hundreds to samples, to get independent Boolean estimates that can be averaged. In this work, we will be concerned with designing a faster estimation scheme for Jaccard similarity.

A beautiful idea of Li and König , known as $b$-bit min-wise hashing, helps reduce the size of a sketch by storing only a $b$-bit hash per sample. While this results in some “accidental” hash collisions, this can be remedied by taking into account the effect of these collisions and taking a larger number of samples. This gives more compact sketches but may require a longer time for sketch generation.

For the unweighted case Li, Owen and Zhang showed how to drastically speed up the computation of sketches by computing 200, say, (near-)independent samples in one shot using only a constant number of hash function evaluations per element, instead of computing each sample one-by-one. Unfortunately however, this “one permutation”-technique does not easily extend to weighted sampling.

In this paper, we bring this level of performance to weighted sampling, producing an algorithm which produces a sketch in time proportional to the number of positive-weight elements in the item. We do this by picking two or more scales and converting the weighted set into an unweighted one by randomized rounding. This sampling step introduces a negligible error and bias and leads to a small unweighted set on which any unweighted sketching technique can be applied. The size of this set is a tunable parameter which can be beneficial for the subsequently used unweighted sketching step. We apply this new algorithm, and the older ones, in a variety of settings to compare the variance in accuracy of approximation. These improvements come at a marginal cost. Our algorithm takes as input an interestingness threshold $\alpha$, say $\alpha=\frac{1}{2}$, such that similarities smaller than $\alpha$ are considered uninteresting. Given two weighted sets, it either returns an accurate estimate of the similarity, or correctly declares that the similarity is below $\alpha$. Since in applications, one is not usually interested in estimating similarity when it is small, we believe that this is an acceptable tradeoff.

Background

Given two finite sets $S$ and $T$ from a universe $U$, the Jaccard similarity of $S$ and $T$ is defined as:

A weighted set associates a positive real weight to each element in it. Thus a weighted set is defined by a map $w:U\rightarrow\Re_{+}$, with the weight of the elements outside the set defined as 0. We denote the support of $w$ by $supp(w)=\{a\in U:w(a)>0\}$. An unweighted set is then the special case where the weight is equal to one on all of its support.

This definition of Jaccard similarity can be extended to weighted sets in a natural way. Given two mappings $w_{S}$ and $w_{T}$ with supports $S$ and $T$ respectively, their weighted Jaccard similarity $jacc(W,V)$ is defined as

Given a weighted set $w$, we denote by $n(w)$ the support size $|supp(w)|$, and by $W(w)$ the total weight $|w|_{1}$. When the weighted set if clear from context, we will simply use $n$ and $W$ to denote these quantities. We will be concerning ourselves with fast algorithms for creating a short sketch of a weighted set from which we can quickly estimate the Jaccard similarity between two sets.

Empirical observations place Jaccard similarity below $\approx$ 0.7 as probably not near-duplicates, and above $\approx$ 0.95 as likely near- or exact-duplicates. We will be concerned with fast and accurate sketching techniques for Jaccard similarity.

Sampling techniques which pick without replacement can closely approximate Jaccard: the oldest such, working in a limited setting where weights are integers (or integer multiples of some fixed base constant) replaces item $a$ with weight $w(a)$ by new items $(a,1),\ldots,(a,w(a))$, all of weight 1. By taking a hash function $h$, and computing it multiple times for each input item, we can map each pair of item, sample number to a positive real number. To select the $j^{th}$ sample, consider ${h(x,j)}$ for all items $x$, and choose the pair producing the numerically smallest hash value. This leads to the generation of $k$ samples in time $O(Wk)$.

Manasse, McSherry and Talwar extended this classic scheme to the case of arbitrary non-negative weights, using the “active index” idea of Gollapudi and Panigrahy . Their scheme had the additional advantage that only expected constant time per element is required, independent of its weight, which leads to a total expected run-time of $O(nk)$ for generating $k$ samples, independent of $W$. Ioffe improved this to worst-case constant time, by carefully analyzing the resulting distributions, reducing the per input per sample cost to choosing five random uniform values in the range between zero and one. This gives a worst case run-time of $O(nk)$.

In a deployed implementation, the principal costs for this per element are: (a) Seeding the pseudo-random generator with the input, (b) computing roughly 200 sets of 5 random values in $$, and manipulating them to compute a 200 hash values, and (c) comparing these hash values to a vector of the 200 smallest values discovered to date, and replacing that value if smaller.

Li, Owen and Zhang , using a technique first explored by Flajolet and Martin compute a single hash value for each element, as well as a random sample number; the hash value then contends for smallest only among those values with equal sample number. This approach does not seem to extend to weighted sampling, because an item with very large weight may need to contend for multiple samples in order to sufficiently influence the predicted similarity. Another deficiency of this approach is that when sets are small, the accuracy of the estimator suffers. Recent works by Shrivastava and Li attempt to address the later concern.

More recently Li and König found it effective to instead store up to 256 smallest values, but store only 1 or 2 bits derived randomly from the smallest values. Accidental collisions will happen a quarter or a half the time, but we can get equivalent power for estimating the Jaccard value by computing enough extra samples to account for the matches that occur due to insufficient length of the recorded value. For 2 bit samples, with 136 samples, we expect 34 to match randomly, leaving us with 102 samples that match with probability equal to the Jaccard value; naïve Chernoff bounds allow us to conclude that estimates of the true value will be accurate to within 0.1. For 1 bit samples, drawing 200 results in 100 accurate samples; the storage space required without these modifications is on the order of 800 bytes. The 2 bit variant takes 34 bytes to hold (with 800 bytes needed in memory prior to the 2 bit reduction, since the minimization step needs to done accurately), while the 1 bit variant needs 25 bytes; a further variant instead computes 400 results, reduces each to 1 bit, and then computes the exclusive-or of pairs of bits to reduce back to 200 bits, each of which will match randomly half the time; this gives us an estimator for $p^{2}$, rather than $p$, which we can then take the square root of.

In our new algorithm, we seek to gain for the weighted case the space efficiency of , while producing a sample set as efficiently as do for the unweighted case.

Algorithm rationale and design

A sketching based similarity estimation scheme consists of two subroutines:

A sketching algorithm $Sketch$ that takes as input a single (possibly) weighted set (and usually, a common random seed) and returns a sketch, and

an estimating algorithm $Estimate$ that takes as input two sketches generated by the sketching and returns an estimate of the Jaccard similarity.

The property one wants from this pair of algorithms is that for any pair of weighted sets $w_{1}$ and $w_{2}$, the estimate $Estimate(Sketch(w_{1},r),Sketch(w_{2},r))$ is “close” to the true Jaccard similarity, with high probability over the randomness $r$. Moreover, we want the run-time and the output size of the Sketch algorithm to be small.

We will present our algorithm in two parts. We first describe a reduction that given a weighted set $w$ and a random seed $r$ outputs an unweighted set $ReduceToUnwtd(w,r)$ such that:

(a) the expected size of the unweighted set is $|w|_{1}$, and

(b) given any two weighted sets $w_{1}$ and $w_{2}$, the resulting unweighted sets $S_{1}=ReduceToUnwtd(w_{1},r)$ and $S_{2}=ReduceToUnwtd(w_{2},r)$ satisfy the property that $jacc(S_{1},S_{2})$ is approximately $jacc(w_{1},w_{2})$ with high probability, as long as $|w_{1}|_{1}$ and $|w_{2}|_{1}$ are large enough.

We will formalize these statements in the next section. We will then describe how such a reduction can be used along with an unweighted similarity estimation scheme to generate fast and small sketches for weighted sets. In this second part, we will assume that we are given a threshold $\alpha$ such that similarities smaller than $\alpha$ need not be estimated accurately.

The reduction is a simple randomized rounding scheme. Consider an element $a$ with weight $w(a)$. We write $w(a)=j_{a}+f_{a}$, where $j_{a}=\lfloor w(a)\rfloor$ is the integer part of $w(a)$ and $f_{a}\in[0,1)$ is the fractional part. We add to $S$ an element $(a,i)$ for $i=1,\ldots j_{a}$. Additionally, we add $(a,j(a)+1)$ with probability exactly $f_{a}$; we do this by computing a hash $h(r,a,j_{a})$ and adding $(a,j_{a}+1)$ to $S$ if and only if $h(r,a,j_{a})<f_{a}$. Using the same hash function seeded with the element $a$ ensures consistency in our rounding, which is crucial for (approximately) preserving Jaccard similarity. The resulting ReduceToUnwtd algorithm looks as follows:

This ReduceToUnwtd algorithm furthermore provides the following guarantees, whose proof we defer to the next section.

Let $w_{1}$ and $w_{2}$ be weighted sets and let $S_{1}=ReduceToUnwtd(w_{1},r)$ and $S_{2}=ReduceToUnwtd(w_{2},r)$ for a random seed $r$. Then for each $i=1,2$ and any $\delta>0$,

(Size Expectation) ${\mathbf{E}}[|S_{i}|]=|w_{i}|_{1}$.

(Size Tail) \Pr[\big{|}|S_{i}|-|w_{i}|_{1}\big{|}\geq 3\sqrt{|w_{i}|_{1}\ln\frac{2}{\delta}}]\leq\delta.

Further let $W=\max(|w_{1}|_{1},|w_{2}|_{1})$. Then

(Bias) \big{|}{\mathbf{E}}[jacc(S_{1},S_{2})]-jacc(w_{1},w_{2})\big{|}\leq\frac{1}{W-1}.

(Tail) $\Pr[|jacc(S_{1},S_{2})-jacc(w_{1},w_{2})|\geq\sqrt{\frac{27\ln\frac{4}{\delta}}{W}}]\leq\delta$.

A variant of this algorithm will be useful when we want to even further improve on the number of hash computations that need to be performed. In particular, we propose the algorithm ReduceToUnwtdDep which uses $h(r,a)$ instead $h(r,a,j_{a})$ to determine whether $(a,j_{a}+1)$ is added. Except for this small change in Step 4 the algorithm is identical to ReduceToUnwtd.

This slight change in ReduceToUnwtdDep compared to ReduceToUnwtd introduces some dependencies in the rounding. For example, if $w_{a}=1.5$ and $w^{\prime}_{a}=2.5$, then the outputs of ReduceToUnwtdDep on these two weight functions $S$ and $S^{\prime}$ will have the events $(a,2)\in S$ perfectly correlated with the event $(a,3)\in S^{\prime}$, whereas in the original ReduceToUnwtd algorithm these events are independent. Nevertheless, the following theorem, which is also proved in the next section, shows that the Jaccard similarity of $S$ and $S^{\prime}$ is still close to that between $w$ and $w^{\prime}$.

Let $w_{1}$ and $w_{2}$ be weighted sets and let $S_{1}=ReduceToUnwtd(w_{1},r)$ and $S_{2}=ReduceToUnwtd(w_{2},r)$ for a random seed $r$. Then for each $i=1,2$ and any $\delta>0$,

(Size Expectation) ${\mathbf{E}}[|S_{i}|]=|w_{i}|_{1}$.

(Size Tail) \Pr[\big{|}|S_{i}|-|w_{i}|_{1}\big{|}\geq 3\sqrt{|w_{i}|_{1}\ln\frac{2}{\delta}}]\leq\delta.

Further let $W=\max(|w_{1}|_{1},|w_{2}|_{1})$. Then

(Bias) \big{|}{\mathbf{E}}[jacc(S_{1},S_{2})]-jacc(w_{1},w_{2})\big{|}\leq\frac{1}{W-1}.

(Tail) $\Pr[|jacc(S_{1},S_{2})-jacc(w_{1},w_{2})|\geq\sqrt{\frac{27\ln\frac{4}{\delta}}{W}}]\leq\delta$.

2 Similarity Estimation Scheme

A more pressing matter though is the following: if we know the sets $w_{1}$ and $w_{2}$, we can carefully pick $\gamma$, but the whole point of the sketch is that it summarizes $w_{1}$ without knowing which $w_{2}$ we would want to compare it with. Thus, we will need to decide on one or more scaling factors $\gamma$ for a set $w$ without knowing which other weighted sets we will compare it with.

To describe our scheme, we will introduce a few more parameters. The input parameter $\alpha<1$ is the interestingness threshold, and our scheme may report ”$<\alpha$” instead of outputting an estimate if the Jaccard similarity is smaller than $\alpha$. The parameter $k$ will correspond to the final number of comparable samples (or $b$-bit hash values) for a pair of weighted sets of interest. This determines the accuracy of the scheme, which is of the order $\frac{1}{\sqrt{k}}$, the standard deviation of $k$ independent random measurements. Thus to get accuracy about $0.05$ in the estimate of the Jaccard similarity, we will use $k$ to be about $400$. An additional parameter $L$ is the redundancy we want to use when using an unweighted similarity estimation scheme. Roughly speaking, for generating $k$ samples, we will assume that the unweighted similarity scheme we use works well on sets of size at least $Lk$. For a scheme such as the one we use , $L$ being a small constant such as $5$ suffices. Finally, a parameter $\beta$ will determine the scaling factors we use, and $t$ will denote the number of scales we use for each weighted set. For simplicity, we first describe the algorithm with $\beta=\alpha$.

Observe that if $w_{1}(U)/w_{2}(U)\not\in[\alpha,1/\alpha]$, then the Jaccard similarity $jacc(w_{1},w_{2})<\alpha$. Thus for such sets, we can safely report “similarity $<$ $\alpha$”. If on the other hand, the ratio $w_{1}(U)/w_{2}(U)\in[\alpha,1/\alpha]$, then the first scaling factors $s_{1}$ and $s_{2}$ chosen for $w_{1}$ and $w_{2}$ are either equal or differ by $1$. In either case, they share at leat $t-1$ scaling factors, and we can use those for estimation of the distance. This gives us $k$ comparable samples, as desired.

More generally, we can pick an integer $\tau\in[1,t]$, and setIn principle, $\beta$ can be chosen arbitrarily in $[\alpha^{1/\tau},\alpha^{1/\tau+1})$, and a value more conducive to floating point operations may be picked. $\beta=\alpha^{1/\tau}$, We then use $\frac{k}{t-\tau}$ samples for each scales, and pick our scales starting from $s=\lceil\log_{1/\beta}\frac{Lk}{(t-\tau)w(U)}\rceil$. It is easy to verify that this choice ensures that for any pair of sets with $w_{1}(U)/w_{2}(U)\in[\alpha,1/\alpha]$, we are guaranteed to find $t$ comparable samples.

We formalize the sketching and the estimating algorithms next. We assume access to a subroutines UnwtdSketch($S,k,r$) that takes in an unweighted set $S$, parameter $k$ and a seed $r$ and returns a sketch consisting of $k$ samples. In addition, we assume that UnwtdEstimate($sketch,sketch^{\prime}$) outputs an estimate of the Jaccard distance based on the sketches. The $b$-bit hashing scheme of would give a candidate pair of instantiations of these subroutines. In the description below, we assume that the randomness source $r$ can be partitioned into sources $r_{i}$, $r^{\prime}_{i}$, for $t$ different values of $i$.

We note that as stated, the number of hash computations required in the reduction steps is $tn$. However, using the dependent version $ReduceToUnwtdDep$ of the reduction, this can be reduced to $n$, which may be a substantial saving when $n$ is large.

While our algorithm can be used with any unweighted similarity estimation scheme, using it with the one permutation hashing scheme of will give us unweighted sets of expected size at most $\beta^{-1}\frac{Lk}{t-\tau},\ldots,\beta^{-t}\frac{Lk}{t-\tau}$. The number of hash evaluations in the unweighted sketching scheme is equal to the set size, so that for the typical setting of $\beta=\alpha=0.5$, $t=3$, the total cost is $7Lk$ hash evaluations. The running time is of a similar order. Here $L$ is a small constant such as $4$. Recall that the best previously known weighted scheme required $5nk$ hash evaluations, which we are reducing to $n+7Lk$.

3 Discussion

In this section, we discuss some finer implementation details, and how they may affect our choices of parameters.

The benefits of tunable unweighted size

One immediate benefit of the set size being tunable is that we can arrange the parameters so as to ensure that at each of the scales that a set is involved in, the size of the unweighted set resulting from the reduction is at least $\frac{Lk}{t-\tau}$. As discussed earlier, this has the benefit of making empty samples rare enough that they can be ignored. This does not just simplify the sketch comparison but more importantly relieves us from having to store whether or not a sample is empty, leading to noticeable savings in the sketch size.

We remark that even for unweighted sets, the one permutation approach of suffers when sets are small. With many bins being empty the accuracy of the scheme drops drastically. Subsequent works have proposed modifications to address this issue. Nevertheless, the authors still pay for sparseness: the variance initially falls off as $\frac{1}{k}$ as $k$ increases, but flattens out once $k$ becomes much larger than the set size. We note that treating an unweighted set as a weighted one, and applying our approach gives a simple solution to this problem, and results in a $1/k$ fall in variance for arbitrarily large $k$, irrespective of the support size, without paying any penalty in the running time. Thus, even for unweighted sets, the approach proposed in this work is useful.

A more subtle benefit comes from the fact that the size of the unweighted set is at most $\beta^{-t}\frac{Lk}{t-\tau}$, so that an average sample gets at most $L\beta^{-t}$ items. For typical values, $L=5,t=3,\beta=0.5$, this is $40$. Thus when computing the hash value to compute the minimum in the bin, we can do with, say a 13 bit hash value. Using these many bits makes it exceedingly unlikely that one of the bins will not have a unambiguous minimum. Thus when generating hash values for $(a,1)\ldots,(a,j)$ for some $a$, we can use $\log_{2}\frac{k}{t-\tau}$ bits to generate the bin, 13 bits to figure out the minimum, and an additional $b$ bits to be stored for the winner in the bin. Thus we need $7+13+2=22$ bits per $(a,i)$. Thus we can generate a sequence of pseudorandom bits seeded with $a$, and then break it up into chunks of 22 bits each, using the $i$th chunk for $(a,i)$. In the rare event that we do not get a unique minimum in some bin, we can reseed with $(a,1)$ and generate several additional bits per $i$ sequentially, and so on. Since this is a rare enough event it does not impose a significant cost. Note that in contrast, without such an upper bound on the required number of bits, the bucketing of any large document would lead to a large number of elements landing in the same bin which would require a larger number of bits to identify the minimum. One thus has to either reseed for each $(a,i)$ or make other assumptions on the document size.

The effect of the threshold for interestingness

The threshold $\alpha$ which determines what values of Jaccard similarity we consider interesting would typically depend on applications. While we presented this work with $\alpha=0.5$, lower or higher similarity values may be preferable in other settings. When $\alpha$ is close to 1 (say 0.95), then other optimizations may be possible. Indeed, note that for sets that are so similar, the sketches, even for a large values of $b$ would agree in nearly all the locations. Intuitively, each stored values gives us little information as there is at most say $5$ out of $100$ $b$-bit values that are different. One could ameliorate this by compressing the sketch in a careful manner. For example, one can take 10 $b$-bit values and just store their XOR, thus saving a factor of 10. In return, we can now generate a 1000 $b$-bit values instead of 100, but store only the 100 resulting XORs. For similarity more than 0.95, at least half of the 10-bin-blocks would be identical, and thus their XOR would be the same. Since we can account for accidental collision of the $b$-bit values, we can account for them. A careful look at this process shows that we would get an estimate of $Sim^{10}\approx(1-10(1-Sim))$ for $Sim$ close to 1, from which a more accurate estimate of the similarity can be obtained. This idea is not new and has been suggested in Li and König , who show that taking $b$ to be $1$ is already better when similarity is at least $0.5$, and show that xoring pairs (the $b=\frac{1}{2}$) case) gives a further improvement for larger similarities. It is natural to pick the appropriate value of $b<1$ when $\alpha$ is close to $1$.

Using more scales than 3

Recall that with the proposed choice of 3 scales, we get two common scales for sets whose weights are within a factor of $\alpha$ of each other. But even for sets whose weights are within a factor of $\alpha^{2}$, we have one common scale and thus get a similarity estimate with error commensurate with $k/2$ samples instead of $k$. By choosing more scales, we get a better trade-off between space and accuracy for every similarity value: we store at many scales, but have fewer samples for each scale. As $t$ increases, a larger fraction of our samples $(1-\frac{1}{t})$ are shared between two sets within weight $\alpha$. And we get a smoother fall-off in accuracy for smaller values of similarity: e.g., even sets with weights within a factor of $\alpha^{2}$ have $t-2$ scales in common, and thus a $(1-\frac{2}{t})$ of our samples can be used for estimating similarity. By setting $\tau$ to be larger, say $\tau=3$, and larger $t$ (say 10), we get as much accuracy as the $\tau=1,t=3$ case for similarities around 0.5, but a smoother decay in accuracy for smaller similarities, and in fact a higher accuracy for higher similarities. The only way that we may have to “pay” for this is that as the size of the unweighted sets now becomes smaller the error in the reduction step may increase. In our experiments, even for unweighted sets of size 50, the error introduced was only a few percent, and moreover the errors over different scales seemed to largely cancel each other out.

Finally, we note that while the variance of the similarity estimate from different scales varies slightly. For the larger scales, the scaled weight is larger, so that the reduction has smaller variance. While at most a factor of $\frac{1}{L}$ of the variance from the unweighted sketch, this small difference in variance of the estimators from each scales can be taken into account while averaging the estimates from different scales. This would give a small improvement in the variance of the final estimate, at the cost of a slightly more complex estimation algorithm.

Proofs

In this section, we prove Theorems 3.1 and 3.2.

We start by stating and proving a useful inequality that relates the expectation of the inverse of a sum of independent -$1$ variables to the inverse of a closely related expectation. This is a special case of a result of and we present a simple proof here for completeness.

Let $\{X_{i}\}_{i=1}^{N}$ be a sequence of independent Bernoulli random variables with ${\mathbf{E}}[X_{i}]=\mu_{i}$ and let $\mu\stackrel{{\scriptstyle def}}{{=}}\sum_{i}\mu_{i}$. Then for $A\geq 1$,

The first inequality follows by applying Jensen’s inequality to the function $\phi(X)=1/(A+X)$, which is convex for $X\geq 0$.

To prove the second inequality, we use a result from who gave a formula for negative moments of random variables. We reproduce the proof of the case we use for completeness. Observe that for every $t,x>0$,

Setting $t=1$ and taking expectations over random $x$, we get

2 Proof of Theorem 3.1

We set up some notation first. Given weighted sets $w_{1}$ and $w_{2}$ , we define $w_{\min}:U\to\Re$ as

and similarly define $w_{\max}:U\to\Re$ as

Recall that $S_{i}=ReduceToUnwtd(w_{i},r)$, and let $S_{\min}$ and $S_{\max}$ denote the outcomes $ReduceToUnwtd(w_{\min},r)$ and $ReduceToUnwtd(w_{\max},r)$ respectively.

Our threshold-based rounding has the property that there is no loss of generality in assuming that $w_{1}=w_{\min}$ and $w_{2}=w_{\max}$. This is because the Jaccard similarity $jacc(w_{1},w_{2})$ equals the similarity $jacc(w_{\min},w_{\max})$, and moreover for any value of $r$ we have that $(a,j)\in S_{1}\cap S_{2}$ if and only if $(a,j)\in S_{\min}$, and similarly $(a,j)\in S_{1}\cup S_{2}$ if and only if $(a,j)\in S_{\max}$. Therefore, $jacc(S_{1},S_{2})=jacc(S_{\min},S_{\max})$ for every value of $r$. For the rest of this proof we will therefore assume that $w_{1}=w_{\min}$ and $w_{2}=w_{\max}$.

Let $Z_{1}:U\to\{0,1\}$ be the indicator function for the set $S_{1}$ and similarly define $Z_{2}$. Note that both $Z_{1}$ and $Z_{2}$ are random variables. For a function $f:U\to\Re$, let $f(U)$ denote $\sum_{a\in U}f(a)$.

Part (1) of Theorem 3.1 is now immediate by linearity of expectation, since for $i=1,2$ we have that

Part (2) of Theorem 3.1 follows by a direct application of Chernoff bounds (see e.g. ).

The Jaccard similarity between $S_{1}$ and $S_{2}$ on the other hand is

Also, note that for $i=1,2$ and for each $a\in U$, the random variables $Z_{i}(a,j)$ are all Bernoulli random variables.

For $e=(a,j)$, define $X_{e}=Z_{1}(e)$, and $Y_{e}=Z_{2}(e)-Z_{1}(e)$. These random variables then satisfy the following properties:

$X_{e}$ and $Y_{e}$ are Bernoulli random variables.

The random variables $\{(X_{e},Y_{e}):e\in\hat{U}\}$ are independent of each other. Thus, $X_{e}$ may depend on $Y_{e}$ but not on $X_{e^{\prime}}$ for $e\neq e^{\prime}$.

For any $e$, at least one of $X_{e}$ and $Y_{e}$ is zero. Thus, ${\mathbf{E}}[X_{e}Y_{e}]=0$.

$\sum_{e\in\hat{U}}{\mathbf{E}}[X_{e}]=w_{1}(U)$.

$\sum_{e\in\hat{U}}{\mathbf{E}}[X_{e}+Y_{e}]=w_{2}(U)$.

We first prove part (4). This is an easy consequence of Chernoff bounds applied to the sums of Bernoulli random variables $X_{e}$, and to the sum of $(X_{e}+Y_{e})$. Let $X$ denote $\sum_{e}X_{e}$ and $Y$ denote $\sum_{e}Y_{e}$. Let $\mu_{x}=E[X]=w_{1}(U)$ and $\mu_{y}=E[Y]=w_{2}(U)-w_{1}(U)$.

Without loss of generality we can assume that $E[X]\geq E[Y]$ (or else can argue about $\frac{Y}{X+Y}$). Now by standard Chernoff bounds,

Thus, except with probability $4\exp(-\alpha^{2}\mu_{x}/3)$, we have

Thus, $|\frac{X}{X+Y}-\frac{\mu_{x}}{\mu_{x}+\mu_{y}}|\leq 3\alpha$ and setting $\alpha=\sqrt{\frac{3\ln 4/\delta}{\mu_{x}}}$ implies that

thus proving part (4). We remark that we did not attempt to optimize the constants here.

Finally, we will prove the following result, which implies part (3).

Let $(X_{1},Y_{1}),\ldots,(X_{m},Y_{m})$ be a sequence of independent tuples of Bernoulli random variables such that ${\mathbf{E}}[X_{i}]=p_{i}$, ${\mathbf{E}}[Y_{i}]=q_{i}$ and ${\mathbf{E}}[X_{i}Y_{i}]=0$ (i.e., they are never 1 together). Let $\mu_{x}=\sum_{i}p_{i}$ and $\mu_{y}=\sum_{i}q_{i}$. Let $X=\sum_{i}X_{i}$ and $Y=\sum_{i}Y_{i}$. Then assumingWe use the convention that $0/0=1$ for the left inequality, and $0/0=0$ for the right one. that $\mu_{x}+\mu_{y}>1$,

When $X=0$, the expression inside the outer expectation is zero. For $X\geq 1$, we apply Lemma 4.1 to conclude that

Now recall that ${\mathbf{E}}[Y_{i}|X_{i}=1]=0$. It follows that ${\mathbf{E}}[Y_{i}|X_{i}]=(1-X_{i})q_{i}/(1-p_{i})$. Thus,

where $\beta_{i}=\frac{q_{i}}{1-p_{i}}$ and $\gamma_{i}=1-\beta_{i}$. This expression is easily seen to be concave in each $X_{i}$ (for any fixing of the other $X_{j}$’s). Indeed denoting the numerator by $f$ and the denominator by $g$, the partial derivative $\frac{\partial f/g}{\partial X_{i}}=\frac{1}{g}-\frac{\gamma_{i}f}{g^{2}}$ and $\frac{\partial^{2}f/g}{\partial{X_{i}}^{2}}=-\frac{2\gamma_{i}}{g^{2}}(1-\gamma_{i}\cdot\frac{f}{g})$. Since both $f/g$ and $\gamma_{i}$ are at most 1, the concavity follows. Thus, using Jensen’s inequality, we can one-by-one replace the random variable $X_{i}$ by its expectation. Rearranging we get

which implies the second inequality. By symmetry

Noting that $\frac{X}{X+Y}=1-\frac{Y}{X+Y}$ then implies the first inequality. ∎

This implies that both ${\mathbf{E}}[jacc(S_{1},S_{2})]$ and $jacc(w_{1},w_{2})=\frac{w_{1}}{w_{2}}$ are sandwiched in the interval $[\frac{w_{1}-1}{w_{2}-1},\frac{w_{1}}{w_{2}-1}]$. Since this interval is of size $\frac{1}{w_{2}-1}$, this implies part (3) and completes the proof of Theorem 3.1.

3 Proof of Theorem 3.2

To prove this, we will need to handle additional dependencies between the tuples $(X_{e},Y_{e})$ as defined above. For a fixed $a$, let $e_{a}$ denote $(a,\lceil w_{1}(a)\rceil)$, and $e^{\prime}_{a}$ denote $(a,\lceil w_{2}(a)\rceil)$. If $e_{a}=e^{\prime}_{a}$, then the only non-deterministic random variable amongst $\{(X_{e},Y_{e}):e=(a,j)\}$ is the tuple $(X_{e_{a}},Y_{e_{a}})$. If on the other hand, $e_{a}<e^{\prime}_{a}$, then $X_{e^{\prime}_{a}}$ is deterministically and $Y_{e_{a}}=1-X_{e_{a}}$. Moreover the random variables $X_{e_{a}}$ and $Y_{e^{\prime}_{a}}$ are correlated through a common threshold $thresh$, with $X_{e_{a}}=\mathbf{1}(thresh<w_{2}(a)-\lfloor w_{2}(a)\rfloor)$ and $Y_{e^{\prime}_{a}}=\mathbf{1}(thresh<w_{2}(a)-\lfloor w_{2}(a)\rfloor)$.

Suppose $(X_{1},Y_{1},Y^{\prime}_{1}),\ldots,(X_{n},Y_{n},Y^{\prime}_{n})$ is a sequence of independent tuples of Bernoulli random variables such that ${\mathbf{E}}[X_{i}]=p_{i}$, ${\mathbf{E}}[Y_{i}]=q_{i}$, ${\mathbf{E}}[Y^{\prime}_{i}]=q^{\prime}_{i}$, and ${\mathbf{E}}[X_{i}Y_{i}]=0$, i.e., $X_{i}$ and $Y_{i}$ are never 1 simultaneously. Further suppose that either (a) $q^{\prime}_{i}=0$ or (b) $q_{i}=1-p_{i}$, $X_{i}=\mathbf{1}(thresh<p_{i})$ and $Y^{\prime}_{i}=\mathbf{1}(thresh<q^{\prime}_{i})$ for threshold $thresh$ chosen uniformly in $$. Let$X=\sum_{i}X_{i}$,$Y=\sum_{i}(Y_{i}+Y^{\prime}_{i})$,$\mu_{x}={\mathbf{E}}[X]$and$\mu_{y}={\mathbf{E}}[Y]$. Then assumingWe use the convention that$0/0=1$for the left inequality, and$0/0=0$for the right one. that$\mu_{x}+\mu_{y}>1$,

When $X=0$, the expression inside the outer expectation is zero. For $X\geq 1$, we once again apply Lemma 4.1, which applies since conditioned on $X_{i}$, either $Y_{i}$ is fully determined, or $Y^{\prime}_{i}$ is deterministically zero. In either case, at most one of $Y_{i},Y^{\prime}_{i}$ is random. We conclude that

We now need to estimate these expectations. We will compute ${\mathbf{E}}[X_{i}+Y_{i}+Y^{\prime}_{i}|X_{i}]$. We consider several cases. In each case, we will show that this expectation can be written as $\beta_{i}+\gamma_{i}X_{i}$, with $\gamma_{i}\leq 1$.

Case 1: $q^{\prime}_{i}=0$. This case is similar to the setting of Theorem 4.2. Here ${\mathbf{E}}[Y_{i}|X_{i}=1]=0$. It follows that ${\mathbf{E}}[X_{i}+Y_{i}+Y^{\prime}_{i}|X_{i}]=X_{i}+(1-X_{i})q_{i}/(1-p_{i})=\frac{q_{i}}{1-p_{i}}+X_{i}\frac{1-p_{i}-q_{i}}{1-p_{i}}$. Clearly, $\gamma_{i}\leq 1$.

Case 2(a): $q_{i}=1-p_{i},q^{\prime}_{i}\geq p_{i}$. In this case, $X_{i}=\mathbf{1}(thresh<p_{i})$, so that $X_{i}=$ implies that $Y^{\prime}_{i}=1$ as well. If $X_{i}=0$, then $Y^{\prime}_{i}$ is $1$ with probability exactly $(q^{\prime}_{i}-p_{i})/(1-p_{i})$. Moreover, $Y_{i}=1-X_{i}$. Thus in this case, ${\mathbf{E}}[X_{i}+Y_{i}+Y^{\prime}_{i}|X_{i}]=1+X_{i}+(1-X_{i})(q^{\prime}_{i}-p_{i})/(1-p_{i})=1+\frac{q^{\prime}_{i}-p_{i}}{1-p_{i}}+X_{i}\frac{1-q^{\prime}_{i}}{1-p_{i}}$. By assumption $\gamma_{i}\leq 1$.

Case 2(b): $q_{i}=1-p_{i},q^{\prime}_{i}<p_{i}$. In this case $X_{i}=0$ iff $thresh>p_{i}$ in which case $Y^{\prime}_{i}=0$ as well. If $X_{i}=1$, then $Y^{\prime}_{i}$ is $1$ with probability exactly $q^{\prime}_{i}/p_{i}$. Once again, $Y_{i}=1-X_{i}$. Thus in this case, ${\mathbf{E}}[X_{i}+Y_{i}+Y^{\prime}_{i}|X_{i}]=1+X_{i}\frac{q^{\prime}_{i}}{p_{i}}$. By assumption $\gamma_{i}<1$.

with $\gamma_{i}\leq 1$. This expression is then easily seen to be concave in each $X_{i}$. Indeed denoting the numerator by $f$ and the denominator by $g$, the partial derivative $\frac{\partial f/g}{\partial X_{i}}=\frac{1}{g}-\frac{\gamma_{i}f}{g^{2}}$ and $\frac{\partial^{2}f/g}{\partial{X_{i}}^{2}}=-\frac{2\gamma_{i}}{g^{2}}(1-\gamma_{i}\cdot\frac{f}{g})$. Since both $f/g$ and $\gamma_{i}$ are at most 1, the concavity follows. Thus using Jensen’s inequality,

It remains to compute the value of the denominator. Since ${\mathbf{E}}[X_{i}+Y_{i}+Y^{\prime}_{i}|X_{i}]=\beta_{i}+\gamma_{i}X_{i}$, it follows that ${\mathbf{E}}[X_{i}+Y_{i}+Y^{\prime}_{i}]=\beta_{i}+\gamma_{i}{\mathbf{E}}[X_{i}]$. Thus the denominator is exactly ${\mathbf{E}}[X+Y]-1$. This implies the second inequality.

To prove the first inequality, it will once again suffice to argue that ${\mathbf{E}}[\frac{Y}{X+Y}]$ is bounded above by $\frac{\mu_{y}}{\mu_{x}+\mu_{y}-1}$. Unlike Theorem 4.2, the variables $X$ and $Y$ are not symmetric. The proof however is relatively straightforward and we sketch it next. We will now write

When $Y=0$, the expression inside the outer expectation is zero. For $Y\geq 1$, we once again apply Lemma 4.1 to write

We once again handle the two cases separately. In the case that $q_{i}=1-p_{i}$, the variable $X_{i}$ is fixed given $Y_{i}$, and the term $Y_{i}+Y^{\prime}_{i}+{\mathbf{E}}[X_{i}|Y_{i},Y^{\prime}_{i}]$ is equal to $1+Y^{\prime}_{i}$ (i.e., a deterministic quantity under the conditioning). If on the other hand, $q^{\prime}_{i}=0$, then $Y^{\prime}_{i}$ is deterministically 0, and the term $Y_{i}+Y^{\prime}_{i}+{\mathbf{E}}[X_{i}|Y_{i},Y^{\prime}_{i}]$ can be written as $\beta_{i}+\gamma_{i}Y_{i}$ with $\gamma_{i}\leq 1$. Thus we can apply Jensen’s inequality to derive the claimed bound. ∎

This then implies part (3) of Theorem 3.2 and completes its proof.

Synthetic Test Results

We produced pseudo-random artificial sets of weights, which we modified to center around a few chosen levels of exact weighted Jaccard similarity: 95%, 90%, 85%, 80%, 70%, 65%, 60%, 55%, 50%, and 40%. We implemented a single scaling version of our algorithm, so that we could estimate Jaccard for all pairs, as well as implementing Ioffe’s algorithm. We selected full-length samples, as well as 2-bit, 1-bit, and half-bit compressions; the number of samples was chosen from 64, 128, 256, and 512.

The first figures we present compare Ioffe sketching against our algorithm using exact Jaccard and our algorithm using binning, measuring the error between the values these algorithms produce, versus the underlying truth. In Figure 5, the yellow bars show the average absolute error when estimating weighted Jaccard using 128 Ioffe samples, shown at a variety of underlying true Jaccard values ranging from 0.40 (on the right) to 0.96, while the blue bars show the estimate using our algorithm computing an estimated 1024 samples randomly assigned to 128 bins. The green bars show the average absolute error introduced by randomized rounding, in which every input item is reassigned to an integer close to its true weight, and the Jaccard value of these roundings are computed exactly. We display these because, following the theorems above on bias, all bias away from true Jaccard is introduced by rounding; both Ioffe’s sampling, and binning preserve expected Jaccard values. At high true Jaccard values both Ioffe and we perform well, missing a true Jaccard value of 0.96 by approximately 0.01; this corresponds to getting a mismatch in slightly over one bin; due simply to quantization in 128 bins, we have to expect an error of at least one in 256. We observe that our algorithm is insignificantly worse than Ioffe at very high Jaccard values from 0.9 to 1.0 (largely due to errors introduced by rounding. Our algorithm is repeatably somewhat better than Ioffe at Jaccard values between 0.8 and 0.9, and is roughly equivalent for Jaccard values down to 0.5, below which point Ioffe sampling is better than our technique, although the absolute error for our technique never exceeds 0.035, corresponding to getting an average excess mismatch of approximately 4 bins.

The next figure, Figure 5 shows the same bars, but with a new color assignment (Ioffe is now blue, our algorithm is now red, and randomized rounding is gray), and computes the standard deviation of the observation made above corresponding to each true Jaccard value. In this graph we see that our standard deviation is smaller than Ioffe’s except at the lowest true Jaccard value, at which point the mismatch in scalings starts to dominate the computation. We also see that the standard deviation is nearly as large as the absolute error, mostly coming from estimates which are closer to the true value.

Conclusions

We have presented a simple scheme to reduce weighted sets to unweighted ones efficiently, in such a way that the size of the resulting unweighted set is tunable, and the Jaccard between sets of comparable sizes is preserved very accurately. We have shown how to use this scheme for the problem of building sketches for Jaccard similarity estimation for weighted sets. The resulting scheme is two orders of magnitude faster than previously known schemes for typical setting of parameters, and does not suffer any significant loss in quality. We prove that the scheme has a non-zero but negligible bias, and satisfies tail inequalities similar to the unweighted case. We also show empirical results showing that this computational benefit comes at negligible cost in accuracy in the interesting case of large similarity.

References