Video 5-6: x-Fast Tries & y-Fast Tries

0:07 So, we've seen binary tries do okay, but not actually better than binary search trees. And the bottleneck was the search in the try itself. So, let's try to improve upon that.

0:20 Okay, I prepared an empty slide. Um Again, we need to find this longest common prefix between X and the set any any element in the set.

0:43 And if you schematically represent our try like this, uh what we'd really like to do if this is height W, what we did in the try is a bit like linear search from the root downwards. How can we speed up something like linear search by doing binary search? Crazy idea. So, we try to jump to the middle layer of the middle height of the try and check can we somehow find whether the longest common prefix is at least that long or is shorter than that?

1:32 Now, how should we do that? Like we haven't followed the try. I can I can look at the nodes here and I can try to look at their children or uh uh but it seems like the information is in the path to the node. So, from what we've currently stored, I can't. There's no way. Uh but we can make it happen if we store extra things. Okay.

2:03 So, the goal is to binary search over the levels instead of linearly walking down. That means we need to answer these questions. Now, let's do something simple. Um all of the nodes that have a path into this have some uh path from the root that is labeled by some string. Namely, the prefix of length the depth.

2:48 So, let's uh let's say in general, this is maybe not just at a certain depth, but let's let's in general say uh we're at depth D and we want to know is the longest common prefix greater than that. If we can do that for any D, we can do binary search.

3:26 we store the set of all the strings, all the prefixes that end at that level. How do we store those? Um it's a set of integers essentially. I'm describing this here in string terminology with longest common prefix, but it's really just D-bit integers.

4:12 And it's at most N because we have at most N leaves. Well, we have N leaves exactly. And what kind of queries do we need? Well, um I'm querying with a prefix of my query number X. That's another string or another number. And the query I'm asking is is there a node that has a path labeled the same way? So, that's just look up. It's a standard search. So, we can use a hash table. And in particular uh we'll store those using dynamic perfect hashing.

5:09 And that means I can ask this question and in constant time get the answer. Right? So, uh I can now do this binary search for the longest uh length of the longest common prefix. And I know which one it is because I have the the string X.

5:35 Uh log of the height. And once I get that, I know what the longest common prefix is and uh with a little extra, we can make the dynamic perfect hashing also not just store the set but store a mapping from the set to the pointers of the nodes here. So I can also get the jump pointer in that node.

6:03 So in constant time after this I can find the node in the appropriate level D. I can take its jump pointer and do the same predecessor successor operations as before. Okay? So after this step two is the same.

6:40 And now translating this back to N gives you essentially this this next statement. Um, it doesn't actually the caps keeps keeps W. Uh, let's let's first um summarize what this achieves. Uh, these are called X-fast tries and the name the story behind the name wasn't very convincing. Somehow this was trying to speed up search in one dimension and uh, the name name stuck. I should have put the reference. This is uh by Willard.

7:09 I'll I'll put the link somewhere on the page. Um Every data structure that stores a subset of integers all W-bit long and and integers in total. It's now a randomized data structure because remember under the hood we're using dynamic perfect hashing and that is randomized. Now for the uh predecessor search this is a look up in the hash table so that's worst case time. There we don't really need uh randomization. So we can do predecessor in log W worst case time.

7:48 And updates we haven't really talked about. But uh it turns out you don't improve anything there. I'll comment on that in a bit. And now the space is clearly n * W proper. Why? So, um for updates what do you have to do? We're still storing a trie. Let's for me I probably still have this this thing here. Yep.

8:21 I still need to maintain this trie, so I still have to create the path of nodes that uh may now be needed. And on every level I have to update my dynamic perfect hashing dictionary for storing the prefixes.

8:57 So, all of this I need to do uh something per level. So, I'm stuck with linear in W time. Which again you can translate as uh um at least log n. So, uh still still the time of a binary search tree, but this log W is now log log n.

9:25 Or closer to log log n. Uh once you're in the in a double log, the exact details between the numbers become less less exciting. Uh how about the space? Well, this is just from the the dictionaries alone.

9:44 Uh fair enough, at the top parts of the tree, they don't contain that many nodes likely. But uh say we focus on the bottom half, probably you will have branched out a quite a bit. Um So, we're essentially storing these n integers w times, or uh is is a bit pessimistic again. Um but I think you can generate worst-case examples where at least up to constant factors, that's what's happening. Same same bad case as before, you have branched out early and then upon many levels essentially n keys. So, much better search time, predecessor search. Space is not actually great, and update time is not very great either. But we may we're we're getting slowly in the right direction. Okay. Uh One last step to make this into a a proper data structure. Now, how could we improve this further?

11:10 That's maybe something um you can think about. The further improvement of the update time and the space comes from a relatively simple engine generic trick, if you like. Uh that I think can be applied in in different cases. Um and it leads to what's what's known as y-fast tries, because y comes after X. I think that's That's all that's behind that.

11:38 Um The technique is is known under the name of indirection, which I'm not sure is very telling. Um you could also say uh we want the data structure to not change too fast. In a way, we have a good data structure for lookups. We just can't tolerate having all the inserts be actual inserts on the data structure. So, one way to slow down would be to somehow not change the main data structure that we use for searching too much. Uh but I mean I'm not making sense, right? What what does that mean? I can't not do the updates. So, what we can do instead um is to have the elements clustered so that you only have a representative of a cluster in the main data structure. But then you need a way to efficiently deal with the clusters as well. So, it's going to be some some trade-off.

12:41 Again, the idea I think uh at that level of abstraction clearly is more more general than this application. One important component is that they need to be locally searchable.

13:02 So, I can answer queries within a cluster. >> Now, I think I'm I'm I'm still lying a little bit. Locally searchable is fine, but we also need to be able that the combination of a a search in the global data structure and the local one together answer the query. So, I can't arbitrarily throw the insertions into buckets. Uh but if you think about again, our try essentially is in sorted order. We have the integers in this binary try, but that means from left to right the integers are sorted. So, uh it's somewhat natural to think of these leaves in the try as pivots in the quick sort sense. And have those separate clusters.

14:13 Uh now maybe I should have drawn them a little um more to the right. Let's say these are pivots in the sense that they're an upper bound. And then below these, there's a binary search tree over the keys between these uh ranges. So, this one on top is an X-fast try as before.

14:39 And these little ones are binary search trees or say balanced binary search trees. Uh we've talked about many varieties of these. Uh we'll we'll come back to which one is convenient here.

14:53 So, clearly this is not specific enough to tell you what to do. Let's see what we can aim for. Uh we had searches previously in log W time because we could binary search in the levels of the try.

15:16 That's called predecessor search in log W time. How many elements can we keep a binary search tree to allow to keep a search locally in that time? Around W. Maybe a W squared would have been fine, but there there we have some slack. Uh allow a local search in that time. >> [snorts] >> So, what we'll do is use the X-fast trie to find which cluster to look into. And then within the cluster, we resolve the actual query. And there's only one like I say you want to do the predecessor query you find of your of your uh query X the predecessor in the X-fast trie. That's likely going to be the one to the left of the trie you want to look at. So, you need to go to the successor of that and likely you're going to find your answer in this tree. If it happens to be between those two, then you may have to go back and and check the maximum in this subtree.

16:35 There's a constant number of cases, but these are all uh easy to deal with. So, let's say this is our X lies somewhere here.

17:37 >> Okay, C primes BST, I don't know how to write that. I have a collision between the prime and the apostrophe. Okay. So, I think the search is still kind of easy. Um, how can we maintain this though? Uh If I If I want to do this, I need to support insertions and deletions.

18:28 >> Uh, let's maybe first comment on the space because that is a bit easier. The space for the clusters is linear in how many keys are in the clusters.

18:46 So, that's big O of N. And how about the uh X-Fast trie? That used to have space essentially N times W. But now, if I have W bits per cluster, my N prime in there is only N divided W, or And so the space for the trie is n' * w, which is order n. So, space-wise we're now doing good.

20:02 And what the updates do will depend on that choice, so let me postpone that a bit. Basically, there's two options. Uh we need to keep them roughly size w, but we don't care if it's exactly w at all. It's fine if they're varying a bit in size. So, for example, um we could do a deterministic splitting scheme.

20:41 when it has grown too big. And when the cluster has grown too small, say at 1/2 w, you fuse it with the neighbor and split again.

21:09 This guarantees uh two things. Well, for one, the clusters are always between half W and two W. So, theta W. It also guarantees that between successive splits, which are costly, you have a linear number of updates to a cluster. So, you can amortize the cost. This is fine. It's a standard scheme of doing this. Now, uh depending on your worldview, I guess, uh this is potentially a bit dangerous because uh a mean adversary could watch your steps uh if it if it knows what you're doing, it could always query um the deletion of the elements that you voted to be representatives. [clears throat] And then you always have some costly operation. Um uh a somewhat more defensive option, and it fits the theme here well, so let uh let me present that one uh too. We just pick random elements to represent the clusters.

22:27 And so, with probability one over W, um each element is picked as uh a pivot. And we essentially do this when um when we insert um and there's no no splitting actually happening, so it's that's the only place.

23:11 >> And upon a deletion, if I delete the element, the representative, I think this is in both cases. Maybe you can go go down here. So, this um is a bit simpler to think about, maybe, and in particular is robust against an adversary because it doesn't know what we're doing. Even we don't know what we do up front. So, I can't send us updates that deliberately destroy our amortized running time. So, um to support this split and resplit, uh I guess the times would be okay for the amortization if I spent linear time on this. But, we're using binary search trees, so we can actually do these with split and join. Um so, a convenient representation for the clusters is using some binary search tree that can support split and join. Well, almost all do. Uh but, here, nicely fitting the theme is just a a trie. Uh a tree, sorry.

24:16 The whole thing is randomized anyways, so we might as well. Good. So, what do updates look like? Let's look at insertion. Well, uh most of the time, um going to flip a coin.

24:43 And with probability 1 over W, I need to actually insert into the X-fast trie this element. Um >> And if you think about what this looks like, we used to have some subtree here. Now, this new element uh lives somewhere here in the middle and is now added as a pivot. So, I'm going to have to split this key this tree into two now.

25:25 And that's one split operation on the cluster. Now, this insertion into the X-fast trie is expensive, right? This costs order W time. But because we're doing it with small probability, the uh expected time contribution is constant.

25:53 And otherwise, um if it's not nominated as a pivot, And which cluster? Well, we do a successive query. If the element is only in a cluster, then fine, just remove it there.

26:55 uh different options. The easiest maybe we just replace it with its its predecessor in the binary search tree. And so this case is not as bad as um uh as a full insertion, but it does change the X fast try. All right, this is uh you're still replacing one value with a different one. So you may have to update the prefixes. They they're close in sorted order, but they may share only a short common prefix. So you may have to update a lot of levels that dynamic perfect hashing.

27:40 So this time also uh is order W. So for this part as well, we want to make this rare. And that's why the randomization here is is the safer option. Otherwise, you're relying on the adversary of not figuring out which elements you promote as representative and always deleting those away.

28:08 Uh otherwise, in both cases we spend search time in the cluster, that's log W. And we have with probability one over W a cost of W. Uh this is uh one over W was the choice of the the chance that an element is a representative. It's uh actively randomized. So in both cases updates cost um log W for the intra-cluster part.

29:10 And with that we get the overall statement. Y-fast tries can store a set of n integers from the range to the W where they store support predecessor in the same way as before in log W time, worst case.

29:26 I guess we're now using treaps at the bottom, so I'm not sure if that's true, right? Uh there probably is some there's some some expected thing going on. You could say something stronger than expected. Um I think I think this is just a lie from how I presented it to be expected time. And and updates are inherited from X-fast trie amortized because you amortize the the this is inherited from the per- dynamic perfect hashing.

30:00 Um and it's expected in several ways now. It's expected over whether or not you have to add the element as a representative. It's expected over the search time in the treaps, and it's expected because of the dynamic perfect hashing. So there's a ton of randomization going on, but luckily everything is independent of each other.

30:25 Um Oh, and this this is um incorrectly copied. Of course, the space is linear now. That was the whole point of uh one one of the point of this indirection trick.

30:40 Okay, with the patch theorem that is Y-fast tries. Um Again, the the the analysis of the expected time for updates uh you would want to spell out all the different parts, but each each is independent of the rest. That's why the randomization um isn't problematic here.

31:02 Okay. Uh let me wrap up this first part um with a typical assumption that we've worked with before for the hashing part that the worst word size of our uh computers is log n or roughly log n. I guess usually theta even. Uh what this means is that we can maintain a dynamic set of integers from this range to the W where all the following operations are expected log log n time amortized expected but log log n time much much faster than any binary search tree exponentially faster than binary search trees. We can do insert, delete, look up, predecessor, min and max, and decrease key, increase key. In particular, this is a priority queue among among other things. Um but one that does more. A predecessor successor is not a general priority queue operation. Here we can do all of this because the the type of keys is specific. It is integers.