Set similarity joins compute all pairs of similar sets from two collections of sets. Set similarity joins are typically implemented in a lter-verify framework: a lter generates candidate pairs, possibly including false positives, which must be veri ed to produce the nal join result. Good lters produce a small number of false positives, while they reduce the time they spend on hopeless candidates. The best known algorithms generate candidates using the so-called pre x lter in conjunction with length- and position-based lters. In this paper we show that the potential of length and position have only partially been leveraged. We propose a new lter, the position-enhanced length lter, which exploits the matching position to incrementally tighten the length lter; our lter identi es hopeless candidates and avoids processing them. The lter is very e cient, requires no change in the data structures of most pre x lter algorithms, and is particularly e ective for foreign joins, i.e., joins between two di erent collections of sets.
The set similarity join computes all pairs of similar sets from two collections of sets. The similarity is assessed using a set similarity function, e.g., set overlap, Jaccard, or Cosine similarity, together with a threshold. A pair of sets is in the join result if the similarity exceeds the threshold.
Set similarity joins have many interesting applications
ranging from near duplicate detection of Web documents to
community mining in social networks [
The best algorithms for set similarity joins are based on
an inverted list index and the so-called pre x lter [
We revisit candidate generation, candidate reduction, and e cient veri cation techniques discussed in literature. The main concepts of this section are summarized in Figure 1. 2.1
We shorty explain the pre x lter, translate normalized thresholds to overlap thresholds, revisit length- and position-based lter conditions, and discuss pre xes in index implementations of set similarity joins.
Pre x Filter. The fastest set similarity joins are based
on the pre x lter principle [
Threshold for normalized set overlap. Normalized set similarity measures take the set sizes into account. For 1In a self join, both input relations are identical, which cannot be assumed in a foreign join. the purpose of set similarity joins, the normalized threshold is translated into an overlap threshold (called minoverlap). The overlap threshold may be di erent for each pair of sets. For example, for the Cosine threshold tC (join predicate js0 \ s1j=pjs0j js1j tC ), minoverlap(tC ; s0; s1) := tC pjs0j js1j. Table 1 lists the de nitions of well-known set similarity functions with the respective overlap thresholds.
Length lter. For a given threshold t and a reference
set s0, the size of the matching partners must be within
the interval [minsize(t; s0); maxsize(t; s0)] (see Table 1).
This was rst observed for the PartEnum algorithm [
Pre x length. The pre x length is js0j tO + 1 for
a given overlap threshold tO and set s0. For normalized
thresholds t the pre x length does not only depend on s0,
but also on the sets we compare to. If we compare to s1, the
minimum pre x size of js0j is minpre x(t; s0; s1) = js0j
minoverlap(t; s0; s1) + 1. When we index one of the join
partners, we do not know the size of the matching partners
upfront and need to cover the worst case; this results in the
pre x length maxpre x(t; s0) = js0j minsize(t; s0)+1 [
For self joins we can further reduce the pre x length [
Positional lter. The minimum pre x length for a pair of sets is often smaller than the worst case length, which we use to build and probe the index. When we probe the index with a token from the pre x of s0 and nd a match in the pre x of set s1, then the matching token may be outside the optimal pre x. If this is the rst matching token between s0 and s1, we do not need to consider the pair. In general, a candidate pair s0; s1 must be considered only if o + minfjs0j p0; js1j p1g; (1) where o is the current overlap (i.e., number of matching tokens so far excluding the current match) and p0 (p1) is the position of the current match in the pre x of s0 (s1); positions start at 0. t js0j
The positional lter is stricter than the pre x lter and is applied on top of it. The pruning power of the positional lter is larger for pre x matches further to right (i.e., when p0; p1 increase). Since the pre x lter may produce the same candidate pair multiple times (for each match in the pre x), an interesting situation arises: a pair that passes the positional lter for the rst match may not pass the lter for later matches. Thus, the positional lter is applied to pairs that are already in the candidate set whenever a new match is found. To correctly apply the positional lter we need to maintain the overlap value for each pair in the candidate set. We illustrate the positional lter with examples.
Example 1. Set s0 in Figure 2 is the probing set (pre x length maxpre x = 4), s1 is the indexed set (pre x length midpre x = 2, assuming self join). Set s1 is returned from the index due to the match on g ( rst match between s0 and s1). The required overlap is dminoverlapC (0:8; s0; s1)e = 8. Since there are only 6 tokens left in s1 after the match, the maximum overlap we can get is 7, and the pair is pruned. This is also con rmed by the positional lter condition (1) (o = 0, p0 = 3, p1 = 1).
Example 2. Assume a situation similar to Figure 2, but the match on g is the second match (i.e., o = 1, p0 = 3, p1 = 1). Condition (1) holds and the pair can not be pruned, i.e., it remains in the candidate set.
Example 3. Consider Figure 3 with probing set s0 and indexed set s1. The match on token a adds pair (s0; s1) to the candidate set. Condition (1) holds for the match on a (o = 0, p0 = 0, p1 = 0), and the pair is not pruned by the positional lter. For the next match (on e), however, condition (1) does not hold (o = 1, p0 = 1, p1 = 4) and the positional lter removes the pair from the candidate set. Thus, the positional lter does not only avoid pairs to enter pred: C(s0, s1) ≥ 0.8 ⇒ dminoverlap(s0, s1, 0.8)e = 8
7 s0: c e f g ? ? ? ? ? ? probing set (pr) s1: a g ? ? ? ? ? ? indexed set (idx)
7
The pre x lter often produces candidates that will be
removed immediately in the next lter stage, the positional
lter (see Example 1). Ideally, such candidates are not
produced at all. This issue is addressed in the mpjoin
algorithm [
Consider condition (1) for the positional lter. We split the condition into two new conditions by expanding the minimum such that the conjunction of the new conditions is equivalent to the positional lter condition: The mpjoin algorithm leverages condition (2) as follows. The probing sets s0 are processed in increasing size order, so js0j grows monotonically during the execution of the algorithm. Hence, for a speci c set s1, minoverlap grows monotonically. We assume o = 0 (and justify this assumption later). For a given index entry (s1; p1), the right side of condition (2) is constant, while the left side can only grow. After the condition fails to hold for the rst time, it will never hold again, and the index list entry is removed. For a given index set s1, this improvement changes the e ective length of the pre x (i.e., the part of the sets where we may detect matches) w.r.t. a probing set s0 to minpre x(t; s0; s1) = js1j minoverlap(t; s0; s1) + 1, which is optimal. On the downside, a shorter pre x may require more work in the veri cation phase: in some cases, the veri cation can start after the pre x as will be discussed in Section 2.3. 2.3
E cient veri cation techniques are crucial for fast set similarity joins. We revisit a baseline algorithm and two improvements, which a ect the veri cation speed of both false and true positives. Unless explicitly mentioned, the term pre x subsequently refers to maxpre x (probing set) resp. s1: a e h ? ? ? ? ? ? idx midpre x (indexing set) as discussed in earlier sections.
Since the sets are sorted, we compute the overlap in a merge fashion. At each merge step, we verify if the current overlap and the remaining set size are su cient to achieve the threshold, i.e., we check positional lter condition (1).
(A) Pre x overlap [
(B) Position of last match [
Small candidate set vs. fast veri cation. The
positional lter is applied on each candidate pair returned by
the pre x lter. The same candidate pair may be returned
multiple times for di erent matches in the pre x. The
positional lter potentially removes existing candidate pairs
when they appear again (cf. Section 2.1). This reduces the
size of the candidate set, but comes at the cost of (a) lookups
in the candidate set, (b) deletions from the candidate set,
and (c) book keeping of the overlaps for each candidate pair.
Overall, it might be more e cient to batch-verify a larger
candidate set than to incrementally maintain the candidates;
Ribeiro and Harder [
In this section, we motivate the position-enhanced length lter (PEL), derive the new lter function pmaxsize, discuss the e ect of PEL on self vs. foreign joins, and show how to apply PEL to previous algorithms.
Motivation. The introduction of the position-enhanced length lter is inspired by examples for positional ltering e z i s t1000 e s 800 0
C A
D
maxsize probing set size pmaxsize minsize
B 100 position in prefix maxprefix 200 like Figure 5(a). In set s1, the only match in the pre x occurs at the leftmost position. Despite this being the leftmost match in s1, the positional lter removes s1: the overlap threshold cannot be reached due the position of the match in s0. Apparently, the position of the token in the probing set can render a match of the index sets impossible, independently of the matching position in the index set. Let us analyze how we need to modify the example such that it passes the positional lter: the solution is to shorten index set s1, as shown in Figure 5(b). This suggests that some tighter limit on the set size can be derived from the position of the matching token.
Deriving the PEL lter. For the example in Figure 5(a) the rst part of the positional lter, i.e., condition (2), does not hold. We solve the equation minoverlap(t; s0; s1) js0j p0 to js1j by replacing minoverlap with its de nition for the di erent similarity functions. The result is pmaxsize(t; s0; p0), an upper bound on the size of eligible sets in the index. This bound is at the core of the PEL lter, and de nitions of pmaxsize for various similarity measures are listed in Table 1.
Application of PEL. We integrate the pmaxsize upper bound into the pre x lter. The basic pre x lter algorithm processes a probing set as follows: loop over the tokens of the probing set from position p0 = 0 to maxpre x(t; s0) 1 and probe each token against the index. The index returns a list of sets (their IDs) which contain this token. The sets in these lists are ordered by increasing size, so we stop processing a list when we hit a set that is larger than pmaxsize(t; s0; p0).
Intuitively, we move half of the positional lter to the pre x lter, where we can evaluate it at lower cost: (a) the value of pmaxsize needs to be computed only once for each probing token; (b) we check pmaxsize against the size of each index list entry, which is a simple integer comparison. Overall, this is much cheaper than the candidate lookup that the positional lter must do for each index match.
Self Joins vs. Foreign Joins. The PEL lter is more powerful on foreign joins than on self joins. In self joins, the size of the probing set is an upper bound for the set size in the index. For all the similarity functions in Table 1, pmaxsize is below the probing set size in less than 50% of the pre x positions. Figure 6 gives an example: The probing set size is 1000, the Jaccard threshold is 0:8, so minsize(0:8; 1000) = 800, maxsize(0:8; 1000) = 1250, and the pre x size is 201. The x-axis represents the position in the pre x, the y-axis represents bounds for the set size of the other set. The region between minsize and maxsize is the base region. The base region is partitioned into four regions (A, B, C, and D) by the probing set size and pmaxsize. For foreign joins, our lter reduces the base region to A+C. If we assume that all set sizes occur equally likely in the individual inverted lists of the index, our lter cuts the number of index list entries that must be processed by 50%. Since the tokens are typically ordered by their frequency, the list length will increase with increasing matching position. Thus the gain of PEL in practical settings can be expected to be even higher. This analysis holds for all parameters of Jaccard and Dice. For Cosine, the situation is more tricky since pmaxsize is quadratic and describes a parabola. Again, this is in our favor since the parabola is open to the top, and the curve that splits the base region is below the diagonal.
For self joins, the only relevant regions are A and B since the size of the sets is bounded by the probing set size. Our lter reduces the relevant region from A + B to A. As Figure 6 illustrates, this reduction is smaller than the reduction for foreign joins. For the similarity functions in Table 1, B is always less than a quarter of the full region A + B. In the example, region B covers about 0:22 of A + B.
Version using pmaxsize for foreign join; input : Sp collection of outer sets, I inverted list index covering maxpre x of inner sets, t similarity threshold output: res set of result pairs (similarity at least t) 1 foreach s0 in Sp do 2 M = fg; /* Hashmap: candidate set ! count */ 3 for p0 0 to maxpre x(t; s0) 1 do 4 for s1 in Is0[p] do 5 if js1j < minsize(t; s0) then 6 remove index entry with s1 from Is0[p]; 7 else if js1j > pmaxsize(t; s0; p0) then 8 break; 9 else 10 if M [s1] = ; then 11 M = M [ (s1; 0); 12 M [s1] = M [s1] + 1; 13 end 14 end 15 /* Verify() verifies the candidates in M */ 16 res = res [ V erif y(s0; M; t); 17 end
Algorithm. Algorithm 1 shows AllPairs-PEL2, a version of AllPairs enhanced with our PEL lter. AllPairsPEL is designed for foreign joins, i.e., the index is constructed in a preprocessing step before the join is executed. The only di erence w.r.t. AllPairs is that AllPairs-PEL uses pmaxsize(t; s0; p0) instead of maxsize(t; s0) in the condition on line 7. The extensions of the algorithms ppjoin and mpjoin with PEL are similar.
An enhancement that is limited to ppjoin and mpjoin is to simplify the positional lter: PEL ensures that no candidate set can fail on the rst condition (Equation 2) of the split positional lter. Therefore, we remove the rst part of the 2We use the -PEL su x for algorithm variants that make use of our PEL lter.
minimum in the original positional lter (Equation 1), such that the minimum is no longer needed.
Note that the removal of index entries on line 6 is the easiest solution to apply minsize, but in real-world scenarios, it only makes sense for a single join to be executed. For a similarity search scenario, we recommend to apply binary search on the lists. For multiple joins with the same indexed sets in a row, we suggest to use an overlay over the index that stores the pointer for each list where to start.
We compare the algorithms AllPairs [
DBLP3: Snapshot (February 2014) of the DBLP bibliographic database. We concatenate authors and title of each entry and generate tokens by splitting on whitespace.
TREC4: References from the MEDLINE database, years 1987{1991. We concatenate author, title, and abstract, remove punctuation, and split on whitespace. ENRON5: Real e-mail messages published by FERC after the ENRON bankruptcy. We concatenate subject and body elds, remove punctuation, and split on whitespace.
Table 2 lists basic characteristics of the input sets. We conduct our experiments on an Intel Xeon 2.60GHz machine with 128 GB RAM running Debian 7.6 'wheezy'. We compile our code with gcc -O3. Claims about results on \all" thresholds for a particular data set refer to the thresholds f0:5; 0:6; 0:7; 0:75; 0:8; 0:85; 0:9; 0:95g. We stop tests whose runtime exceeds one hour.
Foreign Joins. For foreign joins, we join a collection of sets with a copy of itself, but do not leverage the fact that the 3http://www.informatik.uni-trier.de/~Ley/db/ 4http://trec.nist.gov/data/t9_filtering.html 5https://www.cs.cmu.edu/~enron/ collections are identical. Figures 7(a) and 7(b) show the performance on DBLP with Jaccard similarity threshold 0.75 and Cosine similarity 0.85. These thresholds produce result sets of similar size. We observe a speedup of factor 3:5 for AllPairs-PEL over AllPairs with Jaccard, and a speedup of 3:8 with Cosine. For mpjoin to mpjoin-PEL we observe a speedup of 4:0 with Jaccard and 4:2 with Cosine. Thus, the PEL lter provides a substantial speed advantage on these data points. For other Jaccard thresholds and mpjoin vs. mpjoin-PEL, the maximum speedup is 4:1 and the minimum speedup is 1:02. For threshold 0.5, only mpjoin-PEL nishes within the time limit of one hour. Among all Cosine thresholds and mpjoin vs. mpjoin-PEL, the maximum speedup is 4:2 (tC = 0:85), the minimum speedup is 1:14 (tC = 0:95). We only consider Cosine thresholds tC 0:75, because the non-PEL variants exceed the time limit for smaller thresholds. There is no data point where PEL slows down an algorithm. It is also worth noting that AllPairs-PEL beats mpjoin by a factor of 2:7 with Jaccard threshold tJ = 0:75 and 3:3 on Cosine threshold tC = 0:85; we observe such speedups also on other thresholds.
Figure 7(c) shows the performance on TREC with Jaccard threshold tJ = 0:75. The speedup for AllPairs-PEL compared to AllPairs is 1:64, and for mpjoin-PEL compared to mpjoin 2:3. The minimum speedup of mpjoin over all thresholds is 1:26 (tJ = 0:95), the maximum speedup is 2:3 (tJ = 0:75). Performance gains on ENRON are slightly smaller { we observe speedups of 1:15 (AllPairs-PEL over AllPairs), and 1:85 (mpjoin-PEL over mpjoin) on Jaccard threshold tJ = 0:75 as illustrated in Figure 7(d). The minimum speedup of mpjoin over mpjoin-PEL is 1:24 (tJ = 0:9 and 0:95), the maximum speedup is 2:0 (tJ = 0:6).
Figure 8(a) shows the number of processed index entries (i.e., the overall length of the inverted lists that must be scanned) for Jaccard threshold tJ = 0:75 on TREC. The number of index entries increases by a factor of 1:67 for AllPairs w.r.t. AllPairs-PEL, and a factor of 4:0 for mpjoin w.r.t. mpjoin-PEL.
Figure 8(b) shows the number of candidates that must be veri ed for Jaccard threshold tJ = 0:75 on TREC. On AllPairs, PEL decreases the number of candidates. This is because AllPairs does not apply any further lters before veri cation. On mpjoin, the number of candidates increases by 20%. This is due to the smaller number of matches from the pre x index in the case of PEL: later matches can remove pairs from the candidate set (using the positional lter) and thus decrease its size. However, the larger candidate set for PEL does not seriously impact the overall performance: the positional lter is also applied in the veri cation phase, where the extra candidate pairs are pruned immediately.
Self joins. Due to space constraints, we only show results for DBLP and ENRON, i.e., the input sets with the smallest and the largest average set sizes, respectively. Figure 7(e) and 7(f) show the performance of the algorithms on DBLP and ENRON with Jaccard threshold tJ = 0:75. Our PEL lter provides a speed up of about 1:22 for AllPairs, and 1:17 for mpjoin on DBLP. The maximum speedup we observe is 1:70 (AllPairs-PEL vs. AllPairs, tJ = 0:6); for tJ = 0:95 there is no speed di erence between mpjoin and mpjoin-PEL. On the large sets of ENRON, the performance is worse for AllPairs-PEL because veri cation takes more time than PEL can save in the probing phase (by reducing the number of processed index entries). There is almost no 500 400 300 200 100 sec
sec
Summarizing, PEL substantially improves the runtime in foreign join scenarios. For self joins, PEL is less e ective and, in some cases, may even slightly increase the runtime.
Sarawagi and Kirpal [
We presented PEL, a new lter based on the pmaxsize upper bound derived in this paper. PEL can be easily plugged into algorithms that store pre xes in an inverted list index (e.g., AllPairs, ppjoin, or mpjoin). For these algorithms, PEL will e ectively reduce the number of list entries that must be processed. This reduces the overall lookup time in the inverted list index at the cost of a potentially larger candidate set. We analyzed this trade-o for foreign joins and self joins. Our empirical evaluation demonstrated that 150 sec sec sec s -sLEP LEP 100 lliraP lliraP ijopn ij-opn 50 A A m m 0 0 0 0 (a) Foreign join, (b) Foreign join, (c) Foreign join, (d) Foreign j., ENDBLP, tJ = 0:75. DBLP, tC = 0:85. TREC, tJ = 0:75 RON, tJ = 0:75 0 0 (e) Self join, (f) Self join, EN
DBLP, tJ = 0:75 RON, tJ = 0:75 sec the PEL lter improves performance in almost any foreign join and also in some self join scenarios, despite the fact that it may increase the number of candidates to be veri ed.