1 00:00:03,176 --> 00:00:07,266 We can be even more restrictive in the set of candidates that we look for and, and 2 00:00:07,266 --> 00:00:09,500 matches to a given probe string. 3 00:00:09,500 --> 00:00:11,930 In fact, much more restrictive. 4 00:00:11,930 --> 00:00:16,450 We're going to reintroduce the idea we started with, that the length of strings 5 00:00:16,450 --> 00:00:20,540 are an important similarity clue when the Jaccard distance must be small. 6 00:00:22,280 --> 00:00:26,120 however, we look not at the length of the string as a whole but rather, 7 00:00:26,120 --> 00:00:30,480 we build an index structure that takes in to account both the position of the symbol 8 00:00:30,480 --> 00:00:35,170 in the string's prefix and the length of the portion of the string that follows it. 9 00:00:35,170 --> 00:00:37,030 We call this length the suffix length. 10 00:00:37,030 --> 00:00:38,849 And it changes as the position varies. 11 00:00:42,830 --> 00:00:46,290 We're now going to see an even more powerful scheme for indexing. 12 00:00:46,290 --> 00:00:48,440 Here we're going to index on three things. 13 00:00:51,330 --> 00:00:53,520 The first component of the index key or 14 00:00:53,520 --> 00:00:58,760 bucket name is a character at some position in the prefix of the string. 15 00:00:58,760 --> 00:01:04,660 Remember that the prefix is the position up to the floor of J L plus one, 16 00:01:04,660 --> 00:01:12,420 that's our usual, function. 17 00:01:12,420 --> 00:01:14,990 Where J is the upper bound of the car distance and 18 00:01:14,990 --> 00:01:16,270 L is the length of the string. 19 00:01:18,330 --> 00:01:22,590 The second component of the key is the number of the position in the prefix that 20 00:01:22,590 --> 00:01:23,970 holds the character. 21 00:01:23,970 --> 00:01:27,920 Points one and two are exactly the things we indexed using the previous method. 22 00:01:30,500 --> 00:01:33,800 And the third component of the key is the length of the suffix of the string. 23 00:01:33,800 --> 00:01:38,250 That is, the suffix is portion of the string to the right of the index position. 24 00:01:38,250 --> 00:01:41,450 The addition of the suffix length as a component of 25 00:01:41,450 --> 00:01:44,550 the index key gives us the additional advantage that we do 26 00:01:44,550 --> 00:01:49,150 not have to compare two strings if their lengths are rather different. 27 00:01:49,150 --> 00:01:52,250 Even if they have identical or almost identical prefixes. 28 00:01:53,670 --> 00:01:56,940 Let's see how we can exploit the fact that buckets contain only strings with 29 00:01:56,940 --> 00:01:59,870 a particular suffix length to put a stronger lower bound on 30 00:01:59,870 --> 00:02:02,410 the edit distance between strings. 31 00:02:02,410 --> 00:02:05,970 That will enable us to put a lower bound on the decard distance. 32 00:02:05,970 --> 00:02:08,300 And for some index buckets, the lower bound will be so 33 00:02:08,300 --> 00:02:10,920 great that we know we can't find any matches in the bucket. 34 00:02:13,440 --> 00:02:16,030 So let's consider a probe string S. 35 00:02:16,030 --> 00:02:19,120 And suppose we think we need to compare S with another string T 36 00:02:19,120 --> 00:02:21,470 because the I'th position of S. 37 00:02:21,470 --> 00:02:25,450 Is the first position of s that matches any position of t, and 38 00:02:25,450 --> 00:02:27,490 this position is the jth position of t. 39 00:02:31,170 --> 00:02:34,480 Okay, then we can derive a lower bound on the edit distance between s and 40 00:02:34,480 --> 00:02:35,200 t as follows. 41 00:02:36,980 --> 00:02:40,520 Okay, first, take i plus j minus 2. 42 00:02:40,520 --> 00:02:44,710 This is what we used before as a lower bound on edit distance. 43 00:02:44,710 --> 00:02:48,400 And is justification is that none of the first i minus one positions of 44 00:02:48,400 --> 00:02:52,300 s matches any of the first j minus one positions of t. 45 00:02:52,300 --> 00:02:57,180 So we need to do one edit on each of those positions to convert s to t or visa versa. 46 00:03:00,560 --> 00:03:03,750 But if we know the suffix lengths for the two strings involved. 47 00:03:03,750 --> 00:03:06,710 And there is an additional minimum number of edits equal to 48 00:03:06,710 --> 00:03:10,210 the difference between the lengths of the two suffixes. 49 00:03:10,210 --> 00:03:13,240 Notice that since the index doesn't tell us exactly what symbols are in 50 00:03:13,240 --> 00:03:14,680 the suffix of t. 51 00:03:14,680 --> 00:03:18,410 We can't tell for certain where the edits are needed if we want to convert s to 52 00:03:18,410 --> 00:03:19,960 t by inserts and deletes. 53 00:03:20,990 --> 00:03:25,400 But the strings s and t may look nothing like each other. 54 00:03:25,400 --> 00:03:28,310 And in fact many edits may be needed. 55 00:03:28,310 --> 00:03:32,820 But we know for certain that only an edit can chain to the length of a string, 56 00:03:32,820 --> 00:03:34,930 and it changes it by one. 57 00:03:34,930 --> 00:03:37,590 So, we need at least as many edits in the suffix of 58 00:03:37,590 --> 00:03:41,650 S as the difference in their suffix lengths if we are to turn S into T. 59 00:03:43,980 --> 00:03:48,490 And an important point to observe is that because the positions of S and T. 60 00:03:48,490 --> 00:03:51,370 Just before their suffixes are the same and 61 00:03:51,370 --> 00:03:56,410 all strings have their symbols in sorted order.The only way we can change s 62 00:03:56,410 --> 00:04:01,298 into t by the least number edits would be the suffix of s into the suffix of t. 63 00:04:07,100 --> 00:04:11,669 We also have to rethink our upper-bound on the longest common subsequence, probe 64 00:04:11,669 --> 00:04:16,490 string s and some other string t when we take into account the suffix length. 65 00:04:16,490 --> 00:04:21,510 So again, we suppose that the first match between s and t occurs at s's position i. 66 00:04:21,510 --> 00:04:23,420 And it matches the jth position of t. 67 00:04:24,500 --> 00:04:27,110 And let's let a be the symbol in those positions. 68 00:04:29,060 --> 00:04:32,410 Then the LCS of s and t consists of the a. 69 00:04:32,410 --> 00:04:36,070 And as long as sub-sequences we can make out of it two suffixes. 70 00:04:36,070 --> 00:04:37,720 We don't know what these suffixes are. 71 00:04:37,720 --> 00:04:40,980 But we're sure that they cannot have more symbols in common. 72 00:04:40,980 --> 00:04:42,890 And the shorter of the two suffixes. 73 00:04:42,890 --> 00:04:45,690 That's where we get one plus the length of the shorter 74 00:04:48,780 --> 00:04:51,980 as an upper bound on the length of the longest common subsequence. 75 00:04:58,650 --> 00:05:03,050 As we did for the second variation where we considered positions but not suffixes. 76 00:05:03,050 --> 00:05:08,030 We can start with the fact that E over E plus C is less than or equal to J. 77 00:05:09,230 --> 00:05:13,320 Again, remember that E over E plus C has its minimum value when E, 78 00:05:13,320 --> 00:05:16,170 the edit distance, is as low as possible and C, 79 00:05:16,170 --> 00:05:20,520 the, length of the LCS, is as high as possible. 80 00:05:20,520 --> 00:05:23,929 Thus, we can set E to its lower bound and C to its upper bound. 81 00:05:25,140 --> 00:05:27,650 And we have a lower bound on J. 82 00:05:27,650 --> 00:05:32,000 But we'll make one more change, writing E over E plus C equal to or less than J, 83 00:05:32,000 --> 00:05:36,810 which is, of course that, as E is equal to or 84 00:05:36,810 --> 00:05:41,260 less than J times E plus C. 85 00:05:41,260 --> 00:05:42,790 Simple arithmetic there. 86 00:05:43,820 --> 00:05:44,770 So here's what we get. 87 00:05:50,780 --> 00:06:00,440 Here you can see the lower bound on E twice that’s that’s this. 88 00:06:00,440 --> 00:06:03,616 And here’s the upper bound on C. 89 00:06:09,770 --> 00:06:10,595 ' Kay. This is 90 00:06:10,595 --> 00:06:13,802 just rearranging the terms from the line above. 91 00:06:13,802 --> 00:06:15,480 Trust me it, it works. 92 00:06:17,120 --> 00:06:18,240 We now build an index. 93 00:06:18,240 --> 00:06:20,610 Where the keys are triples consisting of a symbol. 94 00:06:20,610 --> 00:06:22,760 A position holding that symbol. 95 00:06:22,760 --> 00:06:24,060 And a suffix-length. 96 00:06:24,060 --> 00:06:26,019 For each such triple there is a bucket. 97 00:06:27,410 --> 00:06:33,460 And we put into the bucket a, i, k, those strings s that have symbol 98 00:06:33,460 --> 00:06:39,420 a in position i, and i is a position in the prefix of s, and the length 99 00:06:39,420 --> 00:06:43,630 of the portion of the string after position i, that is the suffix, is k. 100 00:06:47,670 --> 00:06:49,140 Here is a simple example. 101 00:06:49,140 --> 00:06:50,570 The string s is a b c d e, 102 00:06:50,570 --> 00:06:56,000 and the lower bound on the Jaccard distance is cap J is 0.2. 103 00:06:56,000 --> 00:07:00,080 And the prefix of s is the first 2 positions. 104 00:07:00,080 --> 00:07:04,362 That's because JL is 1, and the floor of JL + 1 is 2. 105 00:07:07,230 --> 00:07:09,580 So for the first position of s, the symbol is a, 106 00:07:09,580 --> 00:07:14,300 the position is 1, and suffix of s after position 1 has length 4. 107 00:07:14,300 --> 00:07:14,800 Okay. 108 00:07:16,470 --> 00:07:18,095 That gives us this bucket. 109 00:07:21,886 --> 00:07:26,300 And we in to that bucket of course, we'll put string s. 110 00:07:26,300 --> 00:07:28,811 For the second position the symbol is b and 111 00:07:28,811 --> 00:07:32,370 the suffix length after position two is three. 112 00:07:32,370 --> 00:07:33,830 That explains this bucket. 113 00:07:35,604 --> 00:07:38,219 There are no more buckets in to which we put s. 114 00:07:42,920 --> 00:07:45,799 The lookup algorithm is similar to what we've seen before, but 115 00:07:45,799 --> 00:07:47,040 there are more buckets. 116 00:07:47,040 --> 00:07:49,730 Each probably contains many fewer strings and 117 00:07:49,730 --> 00:07:54,260 we have a stronger condition that lets us rule out a larger fraction of the buckets. 118 00:07:54,260 --> 00:07:57,150 So suppose we're given probe string S. 119 00:07:57,150 --> 00:08:01,450 And we want to find strings T that might be within Jaccard distance J of S. 120 00:08:02,820 --> 00:08:05,880 We look at certain buckets for each position of the prefix of S. 121 00:08:08,830 --> 00:08:10,450 Here's what we do for position I of S. 122 00:08:12,840 --> 00:08:17,120 First, suppose that eh, that position contains the symbol A. 123 00:08:17,120 --> 00:08:22,020 Also suppose that the suffix of the after position i is length k, and 124 00:08:22,020 --> 00:08:27,430 for certain values of j, the position of string t and m, which is the suffix 125 00:08:27,430 --> 00:08:32,180 of a length of t after its g position we must look in the bucket a, 126 00:08:32,180 --> 00:08:37,149 j, m, if and only if the following inequality is satisfied. 127 00:08:38,750 --> 00:08:42,130 Ok this is the inequality we derived a few slides ago. 128 00:08:42,130 --> 00:08:47,250 It gives us limits on j and m since I k and 129 00:08:47,250 --> 00:08:51,390 the Jacquard distance capital J are already known. 130 00:08:51,390 --> 00:08:55,650 Its not all that easy to see what values are j and m satisfy this inequality but 131 00:08:55,650 --> 00:08:59,740 there’s actually a nice pattern which we we will show you in a few slides. 132 00:09:04,830 --> 00:09:08,760 So let's see an example of Lookup with the string abcde again. 133 00:09:08,760 --> 00:09:13,524 And again we'll have j is 0.2. 134 00:09:13,524 --> 00:09:21,170 Okay, here again is the inequality that j and m have to satisfy for each i and k. 135 00:09:24,020 --> 00:09:26,630 And here are all the buckets that must be searched. 136 00:09:26,630 --> 00:09:28,590 We'll explain why in, in a minute. 137 00:09:30,260 --> 00:09:32,320 Most of action is when i equals one. 138 00:09:32,320 --> 00:09:34,130 That is, we're considering the por-, 139 00:09:34,130 --> 00:09:36,890 position one of string s. 140 00:09:36,890 --> 00:09:39,490 This position holds a, of course. 141 00:09:39,490 --> 00:09:44,070 When i equals one k, the suffix length of, of s is four. 142 00:09:44,070 --> 00:09:47,110 If we substitute these values for i and k. 143 00:09:47,110 --> 00:09:52,720 As well as substitute 0.2 for the Jaccard distance capital J. 144 00:09:52,720 --> 00:09:54,714 Our inequality becomes this. 145 00:09:58,419 --> 00:10:00,420 I'm not going to do all the details here. 146 00:10:00,420 --> 00:10:02,130 But when J equals 1. 147 00:10:02,130 --> 00:10:03,220 It turns out. 148 00:10:03,220 --> 00:10:08,770 That you need m equals 3 4 or 5 in order to satisfy the inequality. 149 00:10:08,770 --> 00:10:12,900 That is m must be pretty close to 4 the suffix-length of s. 150 00:10:12,900 --> 00:10:15,899 In order to make the magnitude of 4 minus m. 151 00:10:18,773 --> 00:10:20,958 Be small enough. 152 00:10:20,958 --> 00:10:23,730 ' Kay. The case j equals 1 that's gives rise to 153 00:10:23,730 --> 00:10:25,866 these three buckets. 154 00:10:25,866 --> 00:10:27,221 Which must be searched. 155 00:10:34,362 --> 00:10:36,210 Then consider j equals 2. 156 00:10:36,210 --> 00:10:39,750 Now it turns out that m must be exactly 4. 157 00:10:39,750 --> 00:10:43,570 In order to make the magnitude of 4-m small enough. 158 00:10:43,570 --> 00:10:49,200 So we get only this bucket for J equals 2. 159 00:10:50,260 --> 00:10:53,750 There is one more bucket, B 1 3. 160 00:10:55,570 --> 00:10:59,800 This comes from the second position of string S which holds symbol B. 161 00:10:59,800 --> 00:11:02,430 When i equals 2, we have k, the surface length equal to 3. 162 00:11:02,430 --> 00:11:10,120 And here's what the inequality becomes. 163 00:11:15,060 --> 00:11:17,940 It turns out that we have only one way to satisfy it. 164 00:11:17,940 --> 00:11:20,479 J has to be 1 and m has to be 3. 165 00:11:25,740 --> 00:11:29,380 So here's my attempt at a picture of the region in three dimensional space where 166 00:11:29,380 --> 00:11:30,660 the buckets we have to search lie. 167 00:11:33,480 --> 00:11:34,720 One dimension is i, 168 00:11:34,720 --> 00:11:39,160 the position of the probe string s where we find the first match. 169 00:11:40,400 --> 00:11:41,660 So we'll look at slices for 170 00:11:41,660 --> 00:11:46,290 each value of i starting with i equals one as we have done here. 171 00:11:46,290 --> 00:11:52,390 The position and the other string t is the vertical dimension and 172 00:11:52,390 --> 00:11:55,100 the length of the suffix of t is the horizontal dimension. 173 00:11:55,100 --> 00:11:58,970 The pairs of j and m that satisfy the inequality. 174 00:12:00,200 --> 00:12:06,110 Form a triangle with peak at k the length of the suffix for the probe string s. 175 00:12:06,110 --> 00:12:12,610 The reason for the peak is that there is a term magnitude of 176 00:12:12,610 --> 00:12:18,320 m minus k that obviously grows with the difference between m and 177 00:12:18,320 --> 00:12:20,770 k and it doesn't matter which is larger. 178 00:12:22,100 --> 00:12:24,780 So what we see is that the lower the position j, 179 00:12:24,780 --> 00:12:27,920 the bigger the difference between m and k can be. 180 00:12:27,920 --> 00:12:30,090 Eventually j grows too large. 181 00:12:30,090 --> 00:12:33,940 And there's no value of m equal e, even m equals k. 182 00:12:33,940 --> 00:12:37,034 That satisfies the inequality to be satisfied. 183 00:12:43,209 --> 00:12:46,050 When i equals 2 the value. 184 00:12:46,050 --> 00:12:47,940 Of j and the difference between m and 185 00:12:47,940 --> 00:12:51,710 k are more limited so the triangle is smaller. 186 00:12:51,710 --> 00:12:56,680 Notice also that the value of k has changed when we increase i the position in 187 00:12:56,680 --> 00:13:01,520 the probe string we decrease k the length of the suffix by the same amount. 188 00:13:03,940 --> 00:13:05,910 The same change happens for i equals 3. 189 00:13:05,910 --> 00:13:07,810 The triangle gets smaller. 190 00:13:07,810 --> 00:13:09,720 And the value of k shifts to the left. 191 00:13:09,720 --> 00:13:13,220 So that the left sides of the triangles continue to line up. 192 00:13:13,220 --> 00:13:16,290 Eventually the triangles become a single point. 193 00:13:16,290 --> 00:13:19,790 And then for the next hirer value of i there is no triangle at all. 194 00:13:19,790 --> 00:13:21,230 And we can stop our search. 195 00:13:25,980 --> 00:13:28,090 I want to leave with, with one observation. 196 00:13:29,090 --> 00:13:33,150 We saw three different index schemes with one, two and three dimensional indices. 197 00:13:35,980 --> 00:13:38,790 The schemes with higher numbers of dimensions involve searching more 198 00:13:38,790 --> 00:13:40,510 buckets for more matches. 199 00:13:40,510 --> 00:13:43,460 But the total sum of the sizes of all the buckets, searched or 200 00:13:43,460 --> 00:13:45,260 not, is the same for each scheme. 201 00:13:48,350 --> 00:13:51,170 The reason is that each stream is placed in the same number of 202 00:13:51,170 --> 00:13:53,460 buckets regardless of the scheme. 203 00:13:53,460 --> 00:13:58,810 That number is our old friend, floor of JL plus one. 204 00:13:59,880 --> 00:14:02,100 the, length of the prefix of the string. 205 00:14:06,330 --> 00:14:10,283 I claim that the expected number of strings in all the buckets that we have to 206 00:14:10,283 --> 00:14:14,423 search, given a probe string, goes down by a factor of two when we add position 207 00:14:14,423 --> 00:14:18,594 information because we search a triangle instead of the containing rectangle. 208 00:14:22,041 --> 00:14:23,398 When we add suffix length, 209 00:14:23,398 --> 00:14:26,240 we can get a large reduction in the number of candidates. 210 00:14:26,240 --> 00:14:29,050 Depending on the distribution of string lengths. 211 00:14:29,050 --> 00:14:32,980 If lengths can vary widely, the third scheme can eliminate almost all 212 00:14:32,980 --> 00:14:37,210 the false positive candidates we have to consider using the first two schemes.