Video 6-4: Select-Index for Succinct Bitvectors

0:02 In the next subsection, we look at how to support the select query. And in the same kind of model, I'm assuming I have my bit vector somewhere written, and I'm adding a little bit of extra space to uh the space for the bit vector itself. The goal will be the same, little-o of n extra bits, and constant time for selection queries.

0:23 Uh let's first see what we can do without um too many complicated constructions. Uh the definition um in case you've forgotten since earlier uh today um is again on the slide. Now, it's on the slide to make one specific point. We're computing the minimum of some set. And uh this the set is constructed over a function that if I make the argument larger, it's only going to get larger. Rank is monotonic in the index, right? The further to the right I go, I can only see more ones. I don't lose any ones. And there's no negative numbers in our prefix sums.

1:07 So, if I have some monotonically increasing set, so the rank uh values at increasing array indices, then I can do binary search over this to find the certain position where the rank flips from one to the next number, which is more the position I want in select. Right? I can specifically find the smallest such j, blah blah blah. That's always possible, and it's worth keeping in mind that sometimes in practice, this is not the worst option. In theory, log n time is horrible because we want constant time. Uh the structures I'm going to show you get there asymptotically. Um but sometimes it happens that a plain binary search is actually better. Uh so, So is worth keeping in mind. On the other hand, um not satisfactory for a theoretical solution. Now, uh of course, we have the other option of storing all all answers. Uh for the rank queries, we certainly didn't want that because every index has some number, and we have to report that.

2:18 Now, for select, it's a little different if the bit vector has few ones. Because uh I only have as many different selection queries as I have one positions in the array. There's some default value. If I uh the way it's defined here, right? I'm going to return n if I put some too large value of r in, more than the number of ones in my array, I just get this dummy value if there's none. Um here formally just n, the position behind the bit vector. So, um there's only going to be m log n extra bits if m is the number of ones. Now, of course, in the worst case, this doesn't help at all because m and n could be the same, or at least could be roughly the same. So, uh if m is theta of n, then clearly this is not succinct, and we don't want that. You can tweak again, kind of a playing with the parameters a bit, store every k-th select, and then work your way between the k-th and k-th plus first uh or between the Uh well, between some between two consecutive multiples of k, you can do your binary search.

3:33 Uh the problem in the worst case is that this doesn't help at all to bring the running time down because select can be really uh nasty. There could be some ones here, and the other ones here. And who knows, maybe one one somewhere hidden here, the needle in the haystack. So, if you want this one, then all you get from this uh subsample is some range here, something here. So, you might still binary search over some portion of the array of size n or roughly n n half, whatever you want. Uh in terms of the asymptotic running time, it's almost as bad as not doing the subsampling. This is, of course, very pessimistic. It would only work to this log n time for certain queries now, whereas most queries in this case would be very efficient. But we want something robust, every case good. Can we do better? Uh yes, we can do better. Um here's the the results this time first, and then I'll try to show you on the next slide.

4:44 Uh we can have a bit vector, and again, in linear time over the bit vector computes an index that is a slight bit larger this time. Notice log log squared divided log n. Uh but it's still the low of n bits, and then we can answer select queries in constant time. And the rest is as before. I can do this even if I have my bit vector only with oracle access to certain to chunks of log n size.

5:16 Okay, there was a slide prepared for that. No. Then let's just start here as well. Given how you that you've seen the rank index, it sounds very natural to try the same thing. So, um maybe this is not part of the proof because uh the way I'm phrasing it, you'll already guess that it's not going to work out.

5:51 If [snorts] I were to say break this into mini arrays of a certain regular size, uh well, very regular. Let me try again. Okay, last one can be shorter. Sticks out at the end. So, the problem is I don't know how much uh I can get from this. The number of ones could be distributed very unevenly. I could have a lot of ones here and then maybe nothing and then a few more here. Maybe there's a stray one here. If I'm trying to select a certain number of ones, it's not clear how do I even find the right green chunk to start in. It feels like now I would have to write down for each argument of select, which green chunk should I jump to? That's a tiny bit less information than storing the actual result, but actually not that less not that much less. The the full result would be log n and now this how many chunks are there? Well, n divided some poly-logarithmic function.

7:08 So, I would have log of the number of chunks to write down it a chunk ID. But this essentially n, that's essentially log n bits again.

7:25 So, I would need log of the number of chunks and that's log of say n divided some L. That's really log n minus log L.

7:40 And it doesn't matter too much what I choose my capital L like is going to be essentially log n. So, I don't seem to win anything from this.

7:56 Indeed, the um Now, I should I should frame this carefully because there is a way to make this work, but it's more complicated and more intricate. Um there's a way to also use somehow such regular intervals. Um but it's much more complicated than the version I want to present. It seems for select much more convenient to do the blocking differently. Namely, to have blocks according to how many ones are in a certain area. So, if you imagine again your your bit vector, and let me draw some some ones in there, and the rest is zeros.

8:42 Uh let's have some dense part here. And maybe some more. Um Okay, now I didn't didn't pay attention to the counts. Okay. Now, let's say we break this into my mini blocks, but so that the number of ones is a certain number. So, the first mini block ends where the the four ones are collected.

9:14 Then I may have um blocks of very different size. Um Maybe I want to make this even a bit more extreme. Sorry, but the change of plan.

9:34 Uh let's just add a few more. Doesn't doesn't hurt. >> I guess you get the picture. Um if I always wait until I see a fourth one, I can get one I can get long blocks and short blocks. Uh I have fairly little control over the size of the blocks. They're going to be um let's give this a name, the parameter. Let's say we use K once at this level.

10:35 In principle, such a mini block can be of length K or can be of length N. No worst-case guarantee. Uh and again, we'll choose this to be something like before, log squared N, so that at least um the number of mini blocks is kind of like before bounded. It could be very small if we have few ones, but even if the bit vector is com- completely full of ones, it won't be more than N / K. Right?

11:23 I'm I'm really using big O as an upper bound here. Now, because the blocks are uniform with respect to the number of ones, if I have a certain value R, I know precisely which of the mini blocks I need to jump into. Right? I can take R divided by K and round it down if I start counting at zero. So, the Rth one is in R divided K rounded down with mini block.

12:11 >> [snorts] >> Okay, that's great, but these can be very big. So, how do we make progress? Well, uh here, unlike before, to make progress, we'll have to do a case distinction. Because the way these blocks can look like is very different. It could have a tiny block like this that's essentially full of ones, or I could have this very sparse block that very messy. Let me try to make it a bit Okay. Uh a little bit better. Or it could be very sparse, and we'll have to treat these somewhat differently just because mm maybe for some blocks we can afford to simply write down the result, whereas for some others we may not uh because there's still too many of them.

13:10 And the precise parameters are as follows. If the block is large, I appreciate that's a bit of an oxymoron to have a large mini block, but uh I could say a long mini block, maybe.

13:31 Uh So, say the length of a mini block is LJ. If that is above a certain threshold, and here one that works is the fourth power of log n. So, maybe um this is an extreme example. It covers most of the array. Uh if if that is the case, I'm going to call such a a block large or long.

14:12 And the good thing about these long mini blocks is there cannot be too many of them because they take up so much of the array.

14:26 maybe can be precise uh at most So, very few and each of them contains capital K ones. So, for these we can for sure just write down the number at the K solutions for the selection queries.

15:24 How much space does that take? Well, we have n divided log four such block such blocks. Then we have K ones, which is log squared of n. And each entry is an index in the entire array, so that's another factor of log n. So, n divided log n.

15:49 Very small. The log of n. So, these are dealt with. If I have these long blocks, I can easily uh write down the solutions. And if you're worried about how to store those, you can have a a bit that tells you whether a block is long or short, or long or dense. And for the long ones, you can have an array that gives you all the answers written one after the other. Uh We'd need another rank query on this bit vector.

16:45 Now, from what you've seen before, the instinct will be, "Oh, the length is so small. Now I can write down an index in this mini block with log log n bits, big O of log log n bits." That's kind of true. Um >> I'll need way fewer bits.

17:29 Uh but note that this is not good enough. Um I may have an array full of ones, in which case all mini blocks would be dense. And now I would write down for every bit in my bit vector log log in bits. I'm trying to do little o of one. I'm I'm not even allowed to store a single bit for each bit in my index. So this is is way too much. I can't store that many bits. >> [snorts] >> So the solution there is to further subdivide. We need another layer level of decomposing these mini blocks. And can for example choose log log n for this little k.

18:50 Uh let me circle this here as well. So now for these again, we have to do a case distinction on how they look like. Same as for the others. When I said recursively subdivide, we're really recursing on the case distinction as well.

19:21 >> So, within the dense mini blocks, I may have a And I call these long if their length LJ little LJ is greater than 1/2 log n. And this number you already recognize as a magic number. That's going to work out to exhaustive table lookup.

19:56 But for the luck for the long ones, I cannot do that, but there's only a a certain number of those. >> [snorts] >> So again, n divided log n leaves enough space that I can store log log n bits each. So the long ones feel kind of bad. But I have n divided log n such uh micro blocks. Each contains log log n ones, and for each of those, I'm going to store log log n bits. That's still little o of n. And this is where the worst lower order term comes from, as you'll see uh from uh if you remember the statement of the theorem.

21:05 So we write down all indices of the ones, and that takes 2 n divided log n many such blocks times little k times log log n. I guess here I need to say big O of because there is some constant factor in front. Uh and this k, which is how we had it here, is another log log n.

21:38 So, we in total have n times log log n to the power of two divided log n, which of course is also a very small term, little O of n.

21:55 So, these are also dealt with. Now, we've been there before, right? Uh what's left are the dense micro blocks. Where before it sounded like um escalating further. We had the dense mini blocks where we said, "Oh, we need to recursively subdivide." Do we need to recursively subdivide? Luckily, no, because these are small. They are so small I can use exhaustive table look up.

22:54 Uh specifically for the micro block local operation, and uh to find out which micro block I have to look at, I'm still going to do the same computation on my original R from the select. I first check what is the mini block that I need to go to. That's this one. If that mini block is long, then I have stored the answer explicitly. If the mini block is dense, I have further subdivided it. So I can local to that mini block compute with whatever is left of R after subtracting this. So which micro block do we have to look at?

23:52 We take our original R and we subtract the number of ones that are before. And that's precisely these. And that's the new R prime.

24:13 And then I go into the R prime divided little K rounded down micro block. So I know which one to go to within that mini block. Then I can again store is this a long one? If so, I've precomputed all the indices. And if not, I know what it locally looks like by looking at the bit vector and I can ask my big look up table for the answer. So the answer local to the micro block and I store for each micro block where it starts local to the mini block. That I need to do as well.

25:10 >> [snorts] >> That I have enough space for though. And reading dense mini blocks we also store this mini block local starting index. That's one per micro block though. That again is uh I think with the log log n I can't do that. So the original uses a slightly higher little k here for a worse overall redundancy. Aha, that's why. >> [laughter] [snorts] >> Um I don't think that's easy to fix. Let me see uh So we might need log square root of log n here instead of log log.

26:24 And not much changes here except that the terms gets uh slightly worse. Instead of log log squared, I have k now be square root log n. So I have this down here is only a square root log n.

26:44 And then I can indeed store this because I'm storing log log n bits for every micro block and there's at most n divided square root log n micro blocks. But this part you need unless you're somehow smart about it. And so that's the worst redundancy we can get.

27:06 Which is not quite this. So, here this should be big O of n log log n divided square root log n. It doesn't really change the the gist of the story. It's still little O of n. And I think that's that's the easiest construction. Um but to make it completely work out, let's leave it that at this. let me remark that at the expense of making the whole data structure a good deal more complicated, you can slightly improve the asymptotic bounds.

28:28 And interestingly, this is also necessary. There's a lower bound that says if you do exactly that, keep the bit vector separate and store an index on top of it, then that index needs to have that many bits >> Again, indexing model means I have to store the bit vector in plain or I'm I'm I'm only storing the index on top of some existing bit vector. I can't modify that space itself. Uh Okay. That's kind of the ultimate um space that you can can that you can get. Uh if you leave the indexing model, you can do slightly better, but that's uh for another time. Uh maybe won't do it here. Let me let me recap um what we've achieved. We can now take a bit vector in a linear time build these indices that allow us to do rank and select both in constant time. And the extra space we use is still asymptotically smaller than the bit vector itself.

30:12 Which uh for most of the applications that we've seen is already close to satisfactory. Uh