Video 2-18: Adaptive online multiple selection

0:03 Uh before before we go to the analysis, let me step through the code um a little bit more carefully so that we all on the same page about what what the algorithm is doing. Uh this is getting two arrays as input. The array of elements and the array of ranks that we're trying to select from or that give the position in x that we want to select. Uh it's a recursive algorithm. So if uh there's no elements left in let's say the capital R if uh the set of ranks is empty then we can stop otherwise we use the linear time selection median of medians from before to find the median of the elements X that is P. We split uh the elements according to smaller and larger to p the two halves. Probably this will be one step in the actual algorithm but uh I split it just for being conceptually cleaner. Uh then we can also determine r the rank of p which is going to be n half + minus one.

1:16 Then I'm also partitioning the ranks namely according to this this rank of the pivot the median that I split to know which ranks are in the left and which are in the right half and then I'm going to to do two recursive calls on the left half with the left half ranks and same on the right and in between I report if my element is one of this the ranks that I'm supposed to select. Uh the reason for putting this in the middle is that then over the course of the recursion I'm going to report the elements in sorted order which is a nitpick in the definition of multiple selection that doesn't matter much here but uh you can do it that way. Why would that algorithm which simply selects the median and doesn't do anything to deserve this good runtime on the surface why does that actually achieve this runtime? uh all that's needed is um a more careful analysis and that is somewhat of a preparation in in in some sense. So uh let's do this carefully. Uh I've drawn here already some uh run of the algorithm on some example that we uh that I'm using to illustrate this. Uh the key trick is to charge the deltas these gaps between ranks a certain amount of the total cost of the algorithm and then bound these parts and what we'll do is that we charge to gap delta I on each level of the recursion. So um I guess we start with zero and this might go on for a while. The algorithm uh doesn't necessarily have few recursive steps starting at zero one and so on.

3:31 What we charge it is this term the smaller of either its size or this 2 * this mysterious term and the claim is that this will uh essentially pay for the entire cost of the algorithm.

4:03 First of all, if we charge to every gap on each level, either its size or this um this green outside part, we're good because of the following reason. So, this is the the green part, that's the blue part.

4:25 Note that the uh the length of these boxes on the level is fixed. we've cut in half D times. So this 1/2 to the D * N is the number of elements in each sub problem. I'm ignoring the rounding. Maybe there's a plus minus one. uh but we uh we usually lose a bit maybe for the for the rank. So it's probably an upper bound. So if I'm on one of the higher levels then certainly my my gap will be smaller than this than this thing and then I can charge the contribution of this gap delta to the overall cost of the algorithm which is always going to be at most n. And so I can always if every gap pays its length I'm always paying n. So everything is covered on the upper uh levels. And things start to get interesting when the subpros are so small that they might uh that delta might be might be larger than these sub problems. In which case um the minimum here might be the green term the blue term no longer the green term.

6:01 Now note that we we only charge okay let me first finish why this covers the cost as soon as let's let's zoom into this part a bit so what does this look like in large um there are boundaries of this of this gap And what's our delta?

6:32 And suppose now we're somewhere on the levels below here. And the sizes of the sub problems are such. This middle one maybe let me make it even more extreme, even smaller.

6:55 These are clearly all equally long as you can see. Um, all of these middle ones, they won't be recursed on further. And indeed, in this case, because they're so small, they don't even exist. They're already terminating a level above.

7:12 And all that's potentially left are these two elements at the outside that straddle the boundary. Those I might still recurse on because this query rank might force me to uh continue recursing. But all this uh wide range in between is going to be empty and not going to I don't have to pay for this further down.

7:41 So on each level I'm only paying for two subpros at most. And here I'm even generous. I'm paying for the entire size of these sub problems even if they stick out of the gap. I'm taking twice the size of the sub problems here. That's even overpaying slightly. But that's uh why this pays for everything.

8:19 visually because every box is covered with some color if you uh were to copy the colors to the other to the other columns. The second step is to bound the sum of this overall deltas by our ominous b + n because that's the actual bound we care about.

8:45 So for that we need an observation about how often we can charge the green cost. and for that the green has to be the minimum. So this has to be smaller than this.

9:16 In other words, d has to be less than log of 2n divided delta i or of course that's the same as log n / delta i + 1 which is essentially the term that we charge uh that we find again in our I don't have this anymore around. Okay. So, we only charge this for that many levels and then the green part, the the blue part takes over. But for the blue part, it's exponentially decaying uh by definition. So this is upperbounded It's two times at most. um the total length and we might overshoot by a factor too but it's a linear in delta I.

10:44 Now if you sum up this this term for all the gaps the total cost is at most this let's pretend the levels keep going and then what we charge each uh gap was this part and we've separately bounded these two parts right um we have at most that many levels the first term maybe I can even write it in green And the blue part is upper bounded by delta i for a single delta. And I can uh sum this overall.

12:06 So overall this turns into a linear term. And we didn't even get a different constant here. Is that that sounds Let me write it like this to uh be on the safe side.

12:40 I think the constant um is a bit questionable because uh I'm charging the gap delta I whereas finding the median is linear in that but there's a constant factor hidden there. So I think from the start this needs a big O around it to be the actual comparisons. uh let's say this is some hypothetical cost and for the comparisons you need to multiply with the constant factor from selecting the median. So in that sense you could say this this C is indeed B plus order N.

13:24 uh but the actual number of comparisons will only be big O of C. Uh there's another constant missing there. Uh but that was all that we claimed for this theorem. So indeed our algorithm here simply doing dividing conquer over the elements uh gives you uh an optimal algorithm up to the constant factor.

13:56 Um just as a citation from uh a paper, you could even if you care about the number of comparisons very much get rid of this constant factor even though finding the median cannot be done with n comparisons. You need strictly more. It's by the way an open problem whether you can do it. We know that finding the median deterministically needs something between 2n and 3n comparisons strictly between 2n and 3n. There's some 2 plus epsilon * n lower bound and some 3 minus epsilon x* n upper bound and we don't know what the truth is. Uh but that aside for multiple selection because you allow this linear extra term you can precisely meet this B with a different algorithm that's more complicated and not so useful for extending in the way I plan. So this is just as a side note. We'll actually continue working with the algorithm that I've shown you and that we analyzed uh because that algorithm has a nice cute property which you can see here.

15:10 The partitioning steps themselves are only chosen depending on the values of the elements. I'm picking the median each time and they're completely independent of the ranks that we select and that's a property we can use for the following observation. That's what I'd said. Uh multis selects recursion all the recursive calls and also the partitioning steps don't at all depend on the ranks. Uh so you could say the algorithm is the median your way through algorithm.

15:51 That means you can also add another rank after the fact once the algorithm is done if you remember where it had pivots placed. You could just continue from where it left off. The way we described the algorithm in the analysis was layer by layer. That is maybe inconvenient. Uh but there's going to be if you currently have some ranks here and here, the algorithm will recurse and recurse, right?

16:25 And so on and it will leave some sub problems uh unchanged. Let's say we're we're lucky we hit this rank guy right here. We could stop. If I now want to add another rank, say I want to select this one as well. I check where it falls. It's in this sub problem and then in this sub problem and then I stop previously because there was no query rank in this range. But now there is. So now I continue just from here until that part is solved for me and I find my element there. And uh for this additional rank, I only pay the red part in addition. All the black parts I can reuse from whatever ranks the algorithm previously looked for. Okay. So I can turn this algorithm in an online algorithm where the ranks I'm interested in arrive one after the other and I don't need to know them up front. The algorithm always just cuts things in the middle using medians and keeps going from where it left off. All we need to do for this is uh you could call this quick sort interrupterss maybe. Uh that's the name I I I made up. Uh all you need to do for this is remember where you had a pivot element, one of these medians.

17:50 So you can uh say store an array of booleans. This is a pivot. Yes. No. Uh then when you get another rank that you are trying to find, you find the closest pivots that you've had so far. That gives you this this red range here.

18:09 Find the closest pivot. Closest pivot boundary counts as pivot. And then you uh continue from there. And note that also the analysis we've done in this proof, you could apply it to the state before adding this new rank or after. The algorithm is going to do the same steps just maybe in a slightly different order. If I analyze this part here, including this red arrow, I'm going to analyze all these steps as they are drawn if you're color blind. And uh the algorithm will have done the same effort except that maybe it did the black part first and then the red part for some weird reason afterwards. But the total cost is the same. So you can say it's uh same as running this offline multi select just on a funny schedule where you do certain things later than others uh because you only learned about this rank after the fact.

19:12 So with the same algorithm with this one extra twist that you remember where the pivots that you've used before are canur can serve online rank queries.

19:25 So you get this very simple extension from an inherently offline problem where I tell you all the ranks up front to this online problem where the ranks come over time. And look how this algorithm can easily do this. Whereas the other algorithm, the divide and conquer over the ranks where you take the middle rank, find that first and recurse on the left and right half. This would entirely fail because if you if I give you another rank, your previously chosen middle rank is no longer the middle and everything is very unclear if the analysis still works. But here it works fine. Um because the uh steps of the algorithm themselves are independent of the ranks. Uh we can even easily work out what is the cost of this red part. If I add another rank, how much do I have to pay to partition that part? Because now that we've done the analysis with our B, it's just the new B minus the old B.

20:40 let me draw the picture for that. So the setup is um we have one extra query. We previously had some query here R I and some query R I + one. Now we get this new query somewhere in here R I prime. Now after the fact I should renumber all the queries which is a bit annoying. So this becomes uh I think that naming makes very little sense. This should this should be RA I + 1 prime, right? Uh or we make this I minus one. But I'm going to mess up all the indices. So let's uh let's just keep it like this and uh don't obsess about the indices please. There's just a new one coming at this position although it is the i + first uh slightly questionable choice of names. This previously was delta i. It's now split into two.

21:47 And let's just call these delta i prime and delta i + 1 prime uh with a slight same abuse of u notation. because the analysis of this theorem remains valid. It's just the difference between the new B and the old B I guess with some uh linear term that's uh we're going to ignore uh because it cancels. You can work it out if you do the analysis. you can work out that the this this isn't really here because all that changes is is the leading term part and this we can work out um using our formula for B right this is from all the queries delta I log N / delta I now most of the gaps don't change the gaps here and the gaps here. They're the same in B prime with the new rank and in B without. It's only these three here that change. So we have the new ones.

23:51 And now because these two the delta i prime and delta i + 1 prime sum to delta i. Uh we can essentially cancel this n. I have n delta i prime n login plus delta i + 1 prime login minus delta i login that cancels.

24:21 Um and I can move this delta i with a minus to the top of the logarithm and make it a plus. And then you see that this is uh what we are trying to prove.

24:49 So, not really uh hard to show this. It's just the difference of the be of the B's. And note again that um there's a vite range how big this quantity is. This extra red cost. uh it could be linear in delta I if the rank is somewhere in the middle then we have to do essentially another median query. It could also be as low as logarithmic in the length if essentially this is one element to the out to the one one further ra i + one or r i r i + 1 minus one.

25:29 Okay. Um this is a foreshadow of what is to come in the following sense. Uh it was relatively easy to add another query and we could work out exactly how much it is supposed to cost and there was a matching lower bound that told us you can't do much better and this is precisely how much you're going to pay.

25:59 We're going to start with this uh tomorrow for full but let me show you already a bit what the problem is in making this more general. So far again the set of elements was fixed and I started this whole section saying ah what if you can do insertions can we do those cheaper so we want to do a dynamic data structure that supports insertions and deletions but I also want to keep somehow uh we need to keep this idea of query ranks so that uh we don't have to sort the entire set and we've seen it was relatively easy to add more query read ranks precisely uh specified what it should cost in a very very clean math etc. Uh what happens if we also want to try to insert to do insertions and deletions. Well, first single uh simple step is that keeping everything in a single array. That was fine for partitioning. That's not convenient now because if you have to insert something in the middle, you have to make make room. But that is actually a non-issue. This is easy to fix.

27:12 You can for all that follows and all that we've done so far pretend that everything sits in a linked list. And let me maybe briefly recap from the algorithm why that's the case.

27:24 um all the way back to this one, the median of medians algorithm. This algorithm you can essentially do on linked lists because all you need is sequential access. The partitioning can be done with sequential read and swap. Sorting five elements or it's just five elements you do whatever. uh swapping elements out to the beginning also works in sequential access. The recursive calls are on uh contiguous areas. So the whole median selection algorithm works as soon as you have some sequential access and so scanning is good enough. A linked list would have been fine. The constant factors in practice are horrible but forget about that for now. Um and the same is true for this algorithm because it's based on essentially these two ingredients. It does median selection and partitioning and that's it. So this also can be simulated if you have sequential axis.

28:37 Everything we do is scanning based. So it works fine if you do it as a linked list. And then of course inserting into a link list always works in constant time. No matter where the position is, you can always make room.

28:54 So for an insertion, if you uh have such a data structure that remembered pivot elements as we've done so far, you can for a new element find which of the gaps uh it should go to. If you have some extra data structure that allows you to access the pivots efficiently, you can binary search over the pivots or you can keep them in a binary search tree, something of that sorts. We'll revisit that and you can find, okay, this is the gap delta i that my new element x should go in. And then you just add it to this linked list and leave it there. No sorting, right? So there's the potential that this insertion is much cheaper because you're only looking you're only doing a a search among the pivot elements but not all of the elements that are in these gaps in between.

29:53 Now uh conceptually this is what we want to build as a data structure. we have somehow a search tree over the pivots over the boundaries and then inside the gaps between these pivots are just some bags of elements where we hopefully don't need to know much more. Uh for insert we simply find the right back stick a new element in are done. And for a query well we have to find the right back and now we have to get the back open and split it. But most queries are fine with linear time. So maybe this is good enough. Uh but already I said foreshadow if your new query is one of these extreme cases where you're supposed to be essentially logarithmic in the size of your bag. That's not going to work if you have to linearly scan through such a a bag of uh unstructured elements. But at this point, I think it's not so clear what we should even aim for.