Video 6-6: MMPHF & Elias-Fano

0:02 And, let me mention one cool thing. This I'll I'll just do briefly. That's just overview mode, right? You high uh cruise altitude. You can use bit vectors to implement an insane hash function. If you think about what we've already done with representing sets, you can make a hash function from some set to the first M integers that is monotone and minimal and perfect.

0:30 Which means it doesn't have collisions. That's perfect. We've talked about that at length, you'll remember. Uh it's minimal in that it's not just perfect, it doesn't use any extra slots. Every slot is occupied. It's a bijection. And on top of that, it should be monotone, so the elements retain the order they have. If the set is just some numbers, that's the assumption. Or some other Well, let's let's say it's numbers. So, I can take an arbitrary set of numbers and map it to the first M integers and even keep the order intact. A very very restricted notion. Um you can just use a bit vector for the set and take the rank of an element as its hash code. That satisfies these properties, if you think about it. It's It's kind of obvious. Um Now, of course, there's a caveat. Um evaluating rank is very fast. We've built constant time indices, but the space is uh We've talked about this. If you want constant time, either your set is almost as big as the universe, or you won't have optimal space and your space usage is closer to the universe than to the size of the set.

1:51 A compressed bit vector is that way is one option how to build such a monotone minimal perfect hash function. Uh but um um it isn't actually a best possible uh because you need a lot of space. It's uh It's only space efficient in the regime from above.

2:22 close to the universe. And there's one part of the definition that we with our bit vector didn't really exploit. Uh the general definition says such a hash function can return an arbitrary value if the element I'm I'm putting in is not in the set. So, you can't re- reconstruct the set from this hash function. Because all you get back is some random numbers. Now, if you get for two elements the same value, you know only one of them can be in the set or neither. I mean, you know nothing. And um the bit vectors don't exploit that, right? They give the same value for everything between two consecutive elements in your set. Rank stays the same until you hit the next element in the set. And indeed, from a bit vector, you can reconstruct the set. So, amazingly, um if you just want this hash function thing, you could do way better in terms of space and time.

3:17 These are very different constructions that have nothing to do with the bit vectors anymore. I feel it's a kind of natural construction to use a bit vector to do this part. And the second part, you can forget about except that note there is a way to be much better. This one is a cute um application of bit vectors. I still think this is uh behind many applications in disguise. Often, when we use this sparse array trick, we're kind of doing that. If we store say for um we can implement with bit vectors an array of variable sizes where the cells I mean the um is one long bit string. Think of the Huffman example where I said uh where does the ith character start? Well, let me ask a bit vector for the position of the ith one. All of these things are essentially doing the same kind of trick um that is also behind these monotone minimal perfect hash functions via rank.

4:20 But if that is all you need, you can do with uh well, with a very complicated construction, you can do much better. >> [snorts] >> The last thing I promised earlier was uh an encoding that at least gives you something when you want to have uh a more space-efficient representation for a set of numbers where you're far away from this threshold where we can achieve constant time worst case. So, I'm I'm in this regime that my number of ones is much much smaller than this n divided log n kind of bound where I still uh not violate the predecessor bound. So, shouldn't hope for worst can't get worst case constant time.

5:17 But maybe we can do something, and there's a a cute heuristic, the Elias Fano encodings. Um I think it's it's it's it's cute and worth knowing about.

5:30 It doesn't have strong worst case guarantees, so it's kind of um more of a for typical not too adversarial inputs, it'll work fine. We store again uh I think of it rather as storing a set where the bits are one.

5:53 Then storing um a bit vector itself. So, we store a set and size of the set is M. You can think of this as a long bit vector over the universe that we want to store in compressed form.

6:11 And what we'll use is M log U over N. That's the optimal lower bound. Plus 2M plus little O of M bits. This is very good. It's very close to the lower bound. If you compare it with what we previously had.

6:32 So, at some point we'll have to suffer a bit. So, we'll support um select, selecting the I've smallest element in S. I mean this is this is really just select on the bit vector. This we can even do in constant time. Note that the predecessor lower bound only says you cannot have rank and select both be constant time. Both together give you predecessor. If one of them is constant time, doesn't there's no violation. Um for rank or predecessor both uh you can support on this. But in the worst case uh you need log U over N. Log U log U over M time.

7:31 So, this is not super inspiring. Log U uh I mean this is kind of a binary search. So, if you just store the numbers, it's not much better than that. Uh but in some a bit vague sense, average case average is over the elements that you query.

7:58 So, I think it achieves something non-trivial that is is not obvious how to do without this construction, but is also uh not completely robust. So, um doesn't contradict any lower bounds.

8:11 Which is always good. How does the encoding work? Uh think of these these num- elements in S. Some element in S is uh collection of bits.

8:33 And how many are there? Well, it's a from this universe U, so it'll be log U long. We'll take the most significant log n bits.

8:55 There's some most significant digits and then there's some least significant digits. Uh it's just more significant and less significant in this case. We're just dividing them into two parts. Um Now, the the choice of these log n first bits um no we'll we'll think of U being substantially larger than n. Um I think I've changed from n to m here. Let's let's uh say this is m. I'm sorry. I'll probably mix this up a few more times. Mm.

9:32 Usually, this will be much smaller than log U. Uh if if uh m is much smaller than U. And the point is that these log M bits should round about be enough to distinguish most of these elements in in S. Because we have already two to the log M, so M different choices for how these most significant digits look like. If we're lucky, they nicely spread the elements apart.

10:01 So, we use these first log M bits to index a bucket for the numbers. You can say it's a hash code that uses the first log M bits.

10:26 Um and so, it'll work as well as hashing would work in this case. If all the elements are tiny and hash to the same bucket, the whole scheme is not going to work well, and we have to live with this worst case for the query times. If the set is somewhat more typical, then it'll spread things out somewhat okay, and most of the query times will be fast. I will not further comment on this part. It's kind of a an empirical argument that often it works, but there's no no more guarantees and no less than for hashing. What I want to show you is how to represent this in this space, because that's not at all clear so far, right? I can't use a simple hash table in the usual way. In particular, I still somehow need to represent the set S, and that already has M elements, each of log U bits, whereas this is less than M times log U, right?

11:20 So, how do we do this? Well, >> We use a clever encoding for these buckets. Namely, you just count how many elements hash into each of these buckets. So, if I take uh this is corresponding to all zero all so on, the first bucket, second bucket, and so on. Up to um the mth bucket.

12:12 I guess m minus one, right? These are the possible combinations I can have as most significant dig- digits, and there's going to be elements in there.

12:24 m in total. I don't know how they distribute. Maybe some buckets are empty. I'm going to encode um just the counts, how many elements hash into each bucket as this first step.

12:43 So, this would be two, one, zero, four, and so on. But, I'm encoding this in unary. So, this is stored as 110. This is as 10. This is just zero. 11110, and so on. Note that the number of ones in total is the number of elements m by definition. The number of ones is number of numbers. And how many zeros do I have? Well, also m because there's m buckets. So, this overall bit vector has precisely 2m bits.

13:18 And guess what? That's these 2m bits, right? And these little o of m is a rank and select data structure on this. >> And then the least significant digits you just store in sorted order of the of the most of of the numbers in a plain array.

14:02 Each of the least significant digits is log n minus log m, so log u over m. That's this one. And I have m of these. That's that contribution. And now um for for the operations you can puzzle out uh how do you get to the precise time? Uh for select that's the easiest. If I want the fifth number in my representation here, I find the fifth one. That gives me the right bucket. And then I find the the fifth least significant digits digit digits stitch stitch them together and return the value. And for rank and predecessor I can get which bucket I'm in using rank on the bit vector here. But then within the buckets I'm left with searching. So I have to binary search the elements within a bucket. In the worst case all of them in there. Um why is this not log m but this uh slightly potentially slightly better log u over m?

15:04 Well, there can't be too many things in such a bucket because there's only so many different uh there's only so many bits in there. So I can't have more than 2 to the power of that different elements in one bucket. Like even though this uh this this may be even minimum of this and log m, right? I don't know which one is smaller in general.

15:42 So, it's just coming from I do a binary search in the bucket. I guess I should have called it gave given this bit vector some name, say A.

16:05 And then binary search inside the bucket. So, I get last time log of the size of the bucket. How big can the bucket be? At most all elements, m, or at most as many different LSDs as I can have. And that's uh 2 to the log u divided m.

16:39 So, bucket is at most m, but it's also at most 2 to the log u divided m, which is u divided m. And so, which of the two is smaller uh depends on the parameters. Okay.