Video 2-19: Lazy Search Trees

0:02 In the next section, we'll look at how to make this dynamic where you can also insert and delete queries. And I've started to illustrate yesterday uh that there's something more complicated going on. So, we take for granted we know how to do queries even if they arrive one after the other. Um we've already talked about the non-issue being the array where we currently the multiple selection algorithm I pretended or assumed that everything is in one big array. That was convenient for partitioning. We can replace everything with linked lists and the algorithms that we use uh work fine. Um that's not a problem. It's also in principle not a problem to have something like an insertion where you find the right the right gap that uh so the the range between two previously queried elements, you can remember where these are. And then you can do a binary search and insert the element into this linked list.

1:00 Also fine. So, where's the problem? Um why does it seem like this is not going to work? Um and for that let's let's uh have a bit of um augmented notation or slightly changed notation to better suit the purpose of this section. And then I'll try to show you um what is the goal? What are from the lower bound that we have, what should we expect to be able to do? Um or rather, what should we not expect to be able to do? And can we match the lower bound? And um that will make it very clear that something is much more complicated if you do insertions and queries combined. That's that's the plan for the first part.

1:50 Um some things have not changed. Uh one thing that is different is that I'm separating here the number of gaps that we have, which previously in the multiple selection problem, this was just Q plus one. If I have Q queries or Q ranks, then I get M one more gap. Uh here we try to separate it because you could potentially ask for the same rank again later. Uh so it's it's maybe a a good idea in general to to keep these two things separate. The number of queries could be larger than the number of gaps if you hit the same query rank again. Um also in a slight change from previous uh notation, this used to be just the size of the gap. So the difference in rank between pivots. Now I'm I'm using this as a first-class object to refer to this set of elements that are between two pivots. Uh that's just convenient because we have to talk about this all the time.

2:50 And we can still say the size of this thing is the number of elements. So that is uh Previously this was just the size. Now you could just replace that with absolute value for for denoting the size. Um Also, it's more convenient here to say that a query answers such a Well, we answer a query by producing gaps so that in this gap either the smallest or the largest element is the element that you're looking for and the gap remembers this kind of boundary value. Uh it's of course the same in in the selection problem. It's a bit more natural to say that you have a a pivot value singled out. And then there's the parts left and right. I guess a very ugly drawing. Let me do this again. Slightly better. Uh so then you have three parts, right? Everything strictly smaller, everything strictly bigger, and the element itself. Here we're kind of giving up on one of these boundaries Uh that makes the few definitions cleaner.

4:00 Okay, I think the notation with the deltas is actually the same as before. I glossed over this difference a bit in the multiple selection problem where it didn't really make a difference.

4:20 Is the notation clear for now? You see that it still closely follows what we've done before. This is just in preparation. Now it would be good to have the lower bound again. Maybe let me briefly copy it.

4:47 So here this was the lower bound. Um All right, take the entire thing. The goal will now be to see what happens to the lower bound when we do another query or another insertion. We've done the first part, what happens upon a query we've kind of figured out already.

5:17 Here. That lemma tells you what happens if you add a query. We'll kind of redo this with a slightly different set of parameters but it's the same same computation. I'll just rephrase it in a slightly different way. What's new is we'll also have to do this for insert. That's what we haven't done so far.

5:40 Okay. So at any point in time or if you want to argue from the lower bound perspective you could say you can uh suppose you had such a dynamic data structure that you can insert elements into when you do can do queries. You can clearly use that data structure to solve the multiple selection problem by inserting everything and then doing all the rank queries. So, the same lower bound should apply to such a data structure. Uh and hence if you um add a new operation at the end, more insertions, more queries, you can still view the whole thing as one long sequence of operations, and that simulates the multiple selection problem. So, the lower bound should hold for the total sequence if you add a few more operations.

6:31 Okay. Here's the lower bound if you uh Please keep in mind this this entropy form, the sum of the the delta I log n over delta I. Uh as to be precise, now we should have the size of the deltas here instead of delta. Change the change notation. Goody.

6:54 Uh the first is what we've proven before in a different parametrization, as I said. So, here um Here, the idea is to rewrite um the lengths a bit. If previously the gap was split into That's our old delta I. Now, we do another query, so we get two new deltas, delta I prime, that's the same notation from last time, and delta I plus one prime. Um Let's call the smaller of these two lengths X.

7:43 And here I'm I'm pretending without loss of generality that the left one is smaller. Of course, this is uh symmetric. This is a smaller is called X and the other is called C * X.

7:56 And for that to make sense, uh C always will be larger than one. So, this kind of um a split into two parts where one is of size X and the other is times is C * X, this will occur all the time. And you can rewrite then the cost of such a query as X * log C. It turns out this is the very same uh same term that we've had before. It's just rewritten.

8:23 Um but it's a bit more convenient to work with that going forward. So, I In principle, I think we can split a few things.

8:59 We've already derived that the the difference was was this entropic form. was the size of this new delta log of old delta divided this new one and then the same term for I + 1.

9:33 And now if we insert what we um defined these like. >> Then this is X, this is CX, right? So, it's it's just X times log uh delta over I, the original thing is X plus CX, otherwise known as C plus 1 times X, right?

10:11 Now, note that we can cancel the X inside the logs. And also that there is a few terms that are shared. The log of C plus 1 occurs here and here. So, we can uh First of all, we can take the X out of um parenthesis. Then you have C C times log C plus 1 and 1 times log C plus 1, that's C plus 1 times log C plus 1.

10:52 And we have uh we subtract C times log C and here is zero. >> [snorts] >> And this one for for C greater equal 1 always going to be non-negative. So, this overall thing is larger than X log C plus 1. And that's what we wanted to prove. Now, I think in all this section, uh you should read log as um Sorry, log of something is meant to be at least one.

11:47 So, these these two things uh don't differ really. Um this is only really relevant in some cases where where we have fractions inside the log that may get small. Um you could have probably in in in all cases just rewrite the bounds to have a a plus constant. Uh so, we could say it's it's X plus X log C. That's the same. Uh this is to um make a few cases shorter to write.

12:22 Um right, so that's that's the first part. Uh this is this is maybe uh a bit unintuitive what this X log C means. Um uh I'll have an example showing this in a second, but we've already before uh when we discussed this term, figured out that this can be anywhere between linear in the old gap size or logarithmic in the old gap size and anything in between. And this is a bit more a bit more visible here with this X log C. X could be anything between constant or linear. Could be half of the gap, then C is one. Uh that's why we need the plus one here or here the the one. Otherwise, log C could be zero. Uh so, it could be that this is essentially linear in X and or but uh linear in delta I. Or it could be if X is one, then C has to be N my L delta minus one, delta I minus one.

13:28 And then uh it could be up to log, it could be as small as log delta I. Same terms but it's a bit more explicit because X and C can have this this range. This is a second part that we can prove if um whenever we do a query, we have this lower bound but we also have a a different one which just says log n or n the total number of elements across all all gaps. So even though you may be doing a query in a very tiny gap where you very narrowly fits in it's never going to be cheaper than log n if you do this for a sequence of queries.

14:21 Um I think the yeah, this is again technically it's not number of queries, it's the number of gaps. We need at least two gaps. If you have a single gap, the whole thing becomes a bit degenerate. Uh for the second part, let's rewrite a bit what B was.

14:41 In the new notation, summing from one up to M, size of the delta I's log n over the delta I's. >> [snorts] >> And the claim is that this is at least m log n when m is greater equal to Uh for that you just need to have a a clever case distinction of what these terms could be. Um one option is that the the deltas are uh somewhere in the large-ish range, so between log n delta I log n delta I You know what? Let me abbreviate delta as the length of this. We'll need it a couple of times here. It's just shorter to write.

15:47 Just as a local abbreviation. Um This thing uh this this inside of here because the delta I is at most n half, this will be at least two. And so, the log is at least one. So, this is at least delta.

16:07 And that's also greater than log n by the lower bound. So, for all the deltas in this typical range, say that's what most I mean there can only be one that's larger than n half anyways, um that's also the second case. Uh And so, uh by dropping this from the sum, if m is at least two, you have at least one other gap. So, you only lose this. I guess here it's technically m minus one. But of course, that's the same.

16:56 So, we just ignore this potentially single gap. Uh most will be in maybe this range, and then we'll handle the the small ones separate. For those in this range, we find that all of them are at least contributing a log n in terms of this uh delta I log n over delta I. Uh and for the tiny gaps, they're still going to be at least a single element by definition.

17:23 Uh I guess strictly less. Uh for those we can separately bound this term. Now again we use the upper bound, so this is greater than n divided log n. Well, then I can uh I can rewrite this as taking the log separate. So, I'm I'm uh I'm even dropping the delta. This could be up to um up to one, but uh it's never going to be smaller than one. And I'm I have to subtract a log log from this from this fraction. But again, that's a lower order term. So, if I sum up these, uh these terms and these terms, I get essentially a log n per gap. Maybe except for one, and I'm subtracting a a sub-logarithmic term.

18:26 So, that's that's good news. Uh let's interpret this a bit. Uh remember, we're trying to study what the lower bound does to help us guide what is a good amortized cost for operations. And for queries, it says on the one hand what we already knew in a in a slightly different uh notation, you can take some time that is depending on where in the gap you do the split, but also you can always take log n time per query easy. At least amortized, because uh the lower bound grows by that much anyways.

19:02 Uh okay. The second part is what happens upon insertions. We kind of already knew queries, but insertion is the the the more interesting part. And there the statement is that the bound increases by an amount that is depending on where I do the insertion. So here suppose the insertion goes into a gap delta I. Then the longer this the bigger this gap is the cheaper the insertion should get. That's fun, right? But maybe intuitive because I'm I'm inserting it into a big crowd, so uh I learn less about this element. Uh the proof is a bit funny in that we do we do two steps. We first consider So we study what the lower bound B plus n does if I arbitrarily fix n at the old value and only increase the delta I value. And then in the second step we bound what happens when n increases. This is is fine for the analysis. Of course, it never works like this in real life. It would uh always increase together.

20:20 But you'll see it's easier to bound this way. Let's do the same abbreviation as before. Now increasing one delta where we insert this. Uh I guess increasing delta. Um turns uh in the contribution to B this term delta log n over delta into well, that thing with delta plus one.

21:01 And so the relative change is this guy minus minus this guy. >> I'm getting impatient with my writing. Sorry about that. Uh so let's study what this change looks like and for that um let's look at this function that this essentially mimics. If we if we treat n as a fixed fixed value as a constant that we can look at this um Sorry. No plus one. Just this n over x.

21:51 So what we're trying to bound is the difference between f of x plus one and and f of x. And the only point to do it this way is to make it a bit more visible that uh this is essentially something like a a difference quotient. So this is going to be at least one times the smallest value of the derivative.

22:27 Yeah, the function is differentiable and and all that. So um uh it's it's a very it's a relatively tame function um it just has uh issues when x gets too small, but none of this is is really an issue here. And you can you can compute what the derivative is.

22:45 Uh and um this is surprising that despite the somewhat ugly term it cancels into something relatively clean. Uh I'm not going to I have it written down, but I'm not going to copy it. It's just the taking the derivative. You can also ask some computer algebra if you prefer. Uh the term is this is essentially just this without the X and a constant offset. Kind of I don't know if you if you follow the rules, I find it surprising, but that's the outcome. Uh So, if we insert that here, what's what's the smallest value for this? Well, uh you have to put the largest value for X in uh for for Y. So, this should be Y.

23:40 And so, that is log n divided X plus Well, okay, let me let me continue with the star from above directly. So, the difference between those two things is I guess intuitively, you could say this log changes so slowly that essentially you get delta plus one times a constant minus delta times a constant, so it's one times that thing. That's all all we're really saying. And you have to take the the smaller one of the two. Uh but don't forget this constant offset, which is roughly this.

24:22 Now, that was this first step where uh we pretend n is unchanged. We do have to change n, but increasing n can only make B go up.

24:45 And of course, the second part of the lower bound, that plus n, goes up by one. So, in total with uh adjusting constants a bit, you can make it take away this minus 1.4 something. Um the leading term if n is not too small certainly will be this one. And so, that's what's written here.

25:28 So, again, let's interpret what this means. If you look at this, this may invoke memories of some running time of a data structure. I don't know if it rings a bell for you. Can anyone remember where we've seen log of something big divided something specific to an element where we've seen that before?

26:01 Let me give you a a hint then. It starts with bias. Uh we've seen this is the run time of a bias search tree when the elements have size of this delta I as the weight. I'm not going to go back the gazillion slides, but there was this statement that um you can Let me show it here. Uh what we'll do is use a bias search tree over the gaps. Okay, so here's again some um example for for ranks that define the gaps in between. And we can put a bias search tree on top that uses the length of these things as weights. And uh the way we wrote it back then was log of the total weight of all the items divided the weight of the item you access. That's your access time for this element. Which again, if the element is important, has large weight, like these guys, they're going to sit close to the root. Whereas less important people can sit down in the tree.

27:02 Uh in our notation, if we pick as the weights, the sizes of the gaps, we get precisely this this bound. So, in a way, we can keep all the gaps in a search tree, which is dynamic. Oh, uh second second part. What was a biased search tree? Well, that's any search tree that gives you these running times. But, what is an implementation of this of this abstract data type? We've seen several in a way, but in detail, we've seen splay trees that get this as amortized time, even without doing anything with the weights, right? The splay trees, this was just in the analysis. You don't do anything in the tree with the weights. Uh it just happens so, uh that the a sequence of accesses has this guarantee for the running time. So, you could just use a splay tree and store the gaps in that, and that's going to be okay.

28:02 Now, what do I mean by okay? Um so, again, let's be a bit more precise. We can um we can use this biased search tree. It's a bit of an awkward one. If we do an insert in the overall data structure, if we want to add a new element, that's a a find in this biased search tree over the gaps, because I have to find where to add it. And then I have to change the weight. That's an actual change to the uh the gap data structure. Um but, that's a bit funny. And it's also vice versa. If you do a query in the overall data structure, that means I'm splitting one gap. So, I get an old gap removed and two new gaps inserted. So, a query it into a a structural change on the gap data structure. A bit awkward, but that's how it is. Question? This I The elements in those gaps, they are unsorted, right?

28:59 Yes, the elements in the gaps are not sorted. That's right. Where do we actually sort them? Do we just append it at the end or Yeah, you could append it at the end. Um for now, everything within the gap is completely unstructured, so it could be an unsorted linked list.

29:17 Finally, go through the paper. Um so, a query, I haven't really told you how to do the queries in a sensible efficient way. A simple case would be, say you're asking for an element whose rank happens to be here. Somewhere in the middle of this gap delta two.

29:39 In that case, um it will be good enough remember the the query cost is this X log C is what the lower bound goes up by. So, if we achieve X log C query time, we're happy. And uh if you're close to the middle, both X and C X are roughly delta half. So, this is linear in this. So, uh for such a query, you have the time to to say linearly scan through the entire unsorted list of elements.

30:17 Um there's a reason why this says step one. This is not going to work uh for all the queries yet. Um so, in a way, uh you're giving me the perfect segue to point out where the problem could be, but let's focus on the positive thing one more time. We can find the right gap to do this insertion. Uh all these animations. We can find the right gap to do the animation uh to do the insertion in precisely the time that the lower bound goes up. So, that is good. We're matching what the lower bound allows us to spend up to this point.

30:59 Now, indeed insertions are kind of fine so far, right? We find the gap, we add the element there, we leave everything else unchanged. That's precisely matching the lower bound. The problem are the queries. And let me illustrate uh a dramatic um kind of example that shows why maintaining this lower bound from the multiple selection problem, this fine-grained bound with B, uh if you're also allowing insertions is substantially harder than just the previous problem where you added one more rank, but kept the set of elements the same. Uh so, suppose somehow um the the lower bound says, "You're essentially allowed to spend log X log C time." Which, if you're query lands here, is roughly linear in in delta I. Let me say linear in delta, so then it that's the size again. Uh whereas if you're closer to the boundary, then that should cost essentially log delta.

32:08 How are you going to in log delta time search through an unsorted set of size delta? Like not, it's not possible. Right? You you don't uh have the time to find this. Now, why didn't our multiple selection algorithm have the same problem? It also did the same. Every Everything it did was split around medians. That's a linear time operation. It got around doing that by not completely stopping here, but it said, "Okay, this is Let me Let me draw maybe the the bigger array." Suppose that was the original thing. It always split around medians and kept doing so until there was no rank anymore. And if they say the original ranks the original queries were here and here, then it would have to split the overall array once And it would keep splitting this part here further and further until it's very close to this red part. All right. Say like this. So, I would have to draw a few more layers here.

33:27 It's only one-sided in the sense that uh Okay, out of out of space. Uh um And eventually here is the the red rank. And similar here. Now, if I do a new query like this one that is very close to a previous one, maybe it's going to land uh close to this thing. But then it will also be in one of the relatively small lower levels. And I can work from there. And maybe my new rank now is here. So, uh all I I have to do is continue splitting here. That's the new split here. That's why this previous algorithm was cheap. It it did actually more than just split at the query ranks. It established this median structure so that within a gap you actually have from the outside of the gap towards the middle, something like an exponentially increasing subdivision. A very fine towards the rank and more coarse grained outside. Um of course there I would have the same here.

34:51 Now, what happens if I allow insertions? Some mean person can come along and hammer insertions here, lots of them. So, by the time our algorithm tries to do the query, this thing is no longer that small. It's actually that big now. And all these elements um paid nothing in an amortized sense for the mess they caused. And now I'm doing a query that is in rank maybe close to um I'm still doing this red query. It's still close in rank to the previous boundary. So, I'm only allowed this very cheap increase of the lower bound. But, there's no way for me to scan through all these new elements for free. So, we have to somehow make them pay upon insertion. Otherwise, it's not going to work. Uh and this is this is a problem that didn't occur when you only had queries. It's the combination of insertion and query that makes this a bit harder.

36:00 Uh and maybe that's why this took a bit longer to solve. Um Okay, here's my uh uh conceptual picture. Um We have to do something like this multiple selection algorithm. We have to somehow establish structure within these these gaps. And which is called those intervals. So, it's any kind of extra pivots that you have. Previously, this was always some medians, but they're going to shift over with insertions anyway, so let's not even call them like that. And it's just additional splits. So, conceptually, it's the same as the gaps. It's unsorted sets of values that are separated, so everything in this one is smaller than everything here, but within they're unsorted. Uh but it's a hierarchical thing. There's the gaps, and within the gaps, there are intervals.

36:58 And there's of course the obvious trade-off. Uh we would like small intervals because that makes queries faster. On the other hand, if we have more intervals, the insertions now have to find the right interval, not just the right gap, so that's going to cost more, especially if there's tons of these. So, there's some uh some trade-offs to be solved.

37:23 And let me briefly comment on two things that do not work. Um one general option, we could instead of um allowing this mess to happen, that the insertions here blow up this this one part so bad that it's expensive to query, we could somehow try not to do that. And in a way, inside of this tree, have insertion buffers at these gaps. When an element wants to be inserted into this gap, I'm not going to immediately write it there. I'll I'll keep it in some extra buffer on the side and try to handle this later. This is This is an approach that sometimes works. Um but it seems here to fail on on at least both of these kind of uh it's not clear how to handle the queries in the time you're allowed to because the insertion buffer, again, could be very big, and you would have to search through it linearly. So, it's just shifting the problem somehow.

38:23 Uh there's a second problem if if you look at what the biased search tree is doing, it occasionally has to rebalance and do rotations. Uh good luck with that doing that with insertion buffers. Also, something uh we didn't find a solution. Um Another thing that is is classic for data structure design is that somehow you want like the medians that these intervals double in size as you move away from the boundary. Or maybe something between double and quadruple or you know, leaving a bit of slack. But an exponential increase as you move away from the boundary. That sounds like the right thing for the query time. But it seems not clear how to maintain it because you have these Uh let me go to this picture, say. Uh you could have a split a new query could split here. And now you want the new query to have the same structure, so you have to do all this all this splitting here to get the exponential sizes again. It seems that is unclear how to do it in the right time.

39:32 Just because it might Uh the example I drew is a bit uh okay, but if it's closer to the boundary, you may not have the time to touch this large part for the new query to look the same. So, it seems like it's a bit too strict. Okay. Uh this is vague, right? Maybe this can be made to work if you're a bit more clever about it.

40:03 Let me show you what we came up with and then we'll do a little break before I show you how it works. Uh So, we we eventually came up with some solution for this that we called lazy search trees. Um and let me first tell you what it does and then uh we'll talk a bit about how to get there. Uh it basically tries to solve this the same problem. We can do insertions and we can do queries. Uh here it says rank-based query because you can you can uh jointly handle um different queries. They could either ask for an element or for rank and it's all essentially the same for the analysis. I'll I'll have a slide on this later. So, insert Okay, this is the the full full version where you can do a little bit more. But really you should focus just on this part. This is the the time for the lower bound and then there's an extra log log.

41:00 That one um that one is is suboptimal. And for query we get this X log C plus log and that was precisely the amortized lower bound.

41:15 Um you can also re-express This is per operation in an amortized sense. You can re-express it as a sequence of insert and queries. Uh with a slight nuisance that it has to be no duplicate queries. But then you can tie it back to this B from the multiple selection lower bound. Because we pay a bit more for the insertions than we should have. We have an N log log N overhead on top of this B, not just plus N, but N log log N. Okay.

41:45 Uh there's other queries you can support. There's faster construction and you can do general deletes, etc. Um these are mostly going to ignore here. Just a bit of advertisement that you can push this a bit further. They can essentially do all the operations that you would want from a a search tree. Uh and the short version is we meet essentially this lower bound in an amortized sense, except that insert is uh uh, has this this slight extra term that we couldn't get rid of. Um, but it was subsequently removed with a more complicated construction than the one I'm going to show you. Uh, that's the same same co-author, Bryce, who, uh, was a PhD student in in Waterloo when I was postdoc there. And, uh, so you can even get rid of this at the expense of making the data structure a bit more complicated.