Video 2-1: Move-to-root heuristics

0:01 In the next chapter we'll look at adaptive trees uh by which I mean fixing this this last point from the previous unit where I said sometimes if some items are accessed much more often or much more frequently than others it would be cool if our data structures could adapt to that and profit from that.

0:25 Uh there's um different variants of what this could mean that we'll look at. Uh for the first one um uh I want to stay with binary search trees and this uh similar model as what we've looked at before. Uh a lot of these data structures are co-authored by Bob Tarjan who has this this picture of a self-adjusting binary search tree on his page and you can see it somehow uh reconfigures itself. That's going to be a little bit the the guide there. Uh in particular it should be some set of rules that knows nothing about the scenario it's used in and yet somehow automatically profits from whatever there is something to exploit. Uh that's probably a bit vague. You'll see several instantiations of what that could mean. Created actually by Yeah. Yeah.

1:25 Um is everything held or is there something floating in air? All right. This this cool. Um some of this chapter is a bit in historic order. Uh and the first structure um I want to motivate uh is the the move-to-root heuristic in binary search trees. Um we'll only really get to the the first part. Hmm. Remember rotations?

2:01 Uh in binary search trees, uh there's a right rotation and a left rotation. Uh what we mean by that is that here, this blue edge, I can flip into one that now points the other way by promoting A up a level and Y down a level. And then the three subtrees hanging from them reattached in the same left-to-right order. In terms of the actual pointers that need to change, it's really just this guy, right? This is now attached to Y instead of A. Uh the left and rightmost trees are still attached to the same node. So, a rotation is really just changing a handful of pointers, two if you only have down pointers. And you can do this in both directions. Now, what I want to point out, um if you have some some [clears throat] node that you care about, this node A here, there's one one operation that uh you can do in in both cases, whether A is a left child or a right child of its parent.

3:09 There's one rotation you can do to make A move a level up. And uh I'll denote both by rotate parent, even though they're really just uh the the two separate cases, right? The kind of pointer changes you need to do depend on whether you're a left or a right child. But conceptually, you're just moving one level up. Uh so, that's something we can do. Let's play a bit with that and see uh what it can get to us. That's the move-to-root heuristic. Whenever you access some element, let's rotate that up until it's at the root, in the hope that if we touch this element soon again, it's still up there or close to the root and will be much cheaper to find the next time.

4:02 This is the kind of self-adjusting rules that this tree with the hands is supposed to stand for. It's completely agnostic to what actually happens. Maybe this guy that I'm touching now is never going to be accessed again, then all this work to bring it up to the root was in vain, but if it is accessed again soon, I'm going to profit from it.

4:23 Uh this idea is is published 1978. So, a while ago. Um you'll see a couple of papers from that time and the preceding and the the decade after. Uh and you've seen an even older result. Probably many of you will have seen this move-to-front heuristic for linked lists. Has anyone not seen this or who has seen move-to-front? Who has not seen move-to-front?

4:53 Okay. Um so, let me let me briefly sketch what this what this looks like. Um It's the same scenario. The idea is that you have a singly linked list of elements.

5:17 I feel we'll spend most of today looking at linked lists. But this time no jump pointers. It's just a plain list. And you have a pointer to the beginning. Now, this will store This is not a sorted list, okay? This is an unsorted linked list.

5:46 And it will store some elements that we might want to find. Now, because it's unsorted, if I want to find some element, there's there's no relation between these X1 that these are I just labeled them by index. But, if I want to find some element Y, there's nothing I can do but linearly search. So, I can go to the first, ask, "Are you my Y?" If no, "Are you my Y?" If no, go to the next pointer until you've found it, or maybe you've reached the end and it wasn't in there. So, searching something that's far into the list is more expensive. You have to walk a lot of pointers. So, ideally you want elements at the beginning of the list. The problem is that there's not much space at the beginning of the list. Everyone wants to sit in the first row on the bus. Uh, so you can't stuff everything there, but maybe you can at least have the elements be roughly ordered by access frequency.

6:55 The most needed guy is at the front, then the next element is the second most most accessed, and so on. If only you knew up front how often elements are going to be accessed, you could do that. But, oftentimes you do have you do not have that knowledge. So, the move-to-front heuristic is an idea of making uh, iterative adjustments to the list that approach this this know- knowledgeable state without ever exploiting explicitly that knowledge. And the idea is, uh, if you've spent all this time to find your element Y down here in the list, let's hope that it will be accessed soon again, and move it to the front, hence the name. So, the list afterwards uh, and the cute thing is you can just bend a few pointers around. So, um Afterwards, this head pointer now points to Y. This shortcuts Y and Y's next pointer is the old head. So, now I've inserted Y at the beginning of the list.

8:13 Because it's a linked list, I can do this by bending a a handful of pointers around. I don't have to move all the other elements.

8:22 But now, if I'm going to access Y soon again, it's closer to the beginning of the list, so it's cheaper to access. Okay? Uh that's the idea. A move-to-front is often used to implement something like a least recently used cache. Because uh the heuristic makes elements over time sorted by when they were accessed last. That's maybe not the same as being accessed often, but if things are roughly independently accessed, the elements that are accessed often will also end up close to the beginning over time. And so, if this keeps running, you're going to pay less for the elements that are more accessed often accessed more often. And so, overall, save uh access cost. There's many good things known about this move-to-front heuristic that I'm I've only uh qualitatively mentioned so far. You can prove um very strong properties um more rigorously that I don't want to go into, but I want to motivate why this move-to-root is such a promising idea.

9:33 So, move-to-front is known to be at most twice as bad in the overall the typical cost than the optimal static ordering, which means if you knew the access frequencies, so you have an entire sequence of accesses and you count how often each element is accessed over the entire sequence. If you knew the access in advance, you could have arranged the list in order of decreasing frequencies. If you had done that, if you know the accesses in advance all you can save is a factor two over this move-to-front heuristic. It's so good in adjusting to these frequencies that only this factor two can be gained. Uh similarly, who knows about online algorithms and competitive analysis? Nobody?

10:27 Okay, then we'll have to talk about that a bit more next time. Um who has not heard of online algorithms and competitive analysis? Okay. Uh it's is in a way similar to this first statement, but a bit stronger. You're uh two competitive means this move-to-front heuristic is at most two times as expensive as any offline algorithm, so any algorithm that is given the access sequence in advance and can do whatever it wants with that knowledge. It could in particular do this first part, compute one ordering on the list and then stick with it. But it could also say, "Ah, I see in the first half of the list I'm accessing these elements and then in the second half of the list it's different, so I'm going to change the order of the list mean between this first and second half." It's going to have to pay for the changes but maybe this is still cheaper overall.

11:26 And this this statement says, "No matter what clever uh cleverness you put into this optimal offline algorithm that knows the sequence in advance, you're never going to save more than a factor two in parentheses under a certain model of what changes cost. At this point, you have to be a bit more precise about what the algorithm is allowed to do. But in under some somewhat reasonable assumption, um you can prove the strong statement that this simple heuristic is at most twice as expensive as whatever you could possibly do.

12:06 Has anyone heard of the paging problem? If you've not heard online algorithms, maybe not. The paging problem? It's what what any cash has to do, right? Yeah. So, paging just says it's the abstraction of caching. I have objects. I have a small amount of cash that I can fill with objects. When the next access comes, if I have it in cash, it's for free. If it's not in cash, I have to bring it in cash and evict something else. And then the hope is that over time you have most elements cached and don't have much cost. Question? I have question about like the when we do if we do move to root a lot, can it unbalance the tree like significantly? But is that a discussion for next week? That's a discussion for tomorrow, yeah. Yeah, next lecture. Yeah.

13:01 That's right, yeah. Um indeed, you can think about this what move to root could possibly be uh Because we have doing wrong. I don't think we care about what happens to other elements other than the one we are moving. So, Sure. The various it can be a very skewed skewed tree too, like left skewed or right right skewed. So, the height could be like very That's right. Um on the other hand, it's it's a bit more subtle in a in the sense that we'll first show a somewhat positive result. Uh but that notwithstanding, there is a there are bad cases for move to root. Mhm. It's a bit funny that for move to front in the list setting, they're not really uh showing. But I guess that's because you're always in all these algorithms, you're comparing with another list. So, uh you're still paying this linear cost. And so, it's not showing as much. Whereas move to root, we now compare with binary search trees, so worst case is already log n if you do a balanced tree, right? This is a much stronger comparison.

14:17 Yeah, the paging problem uh is this problem you're given requests to pages, you can only cache a few of them. How do you decide which page to evict if you don't know what's coming in the future? And a popular heuristic is this LRU, least recently used. So, you evict the page that was accessed previously the longest time ago, the least recently used page. Uh and you can use move to front to simulate that.