So the high level idea as I understood it seems to be this: Use a hash function b(x) to transform keys into fixed length bitvectors. Now we want to build a fu

So the high level idea as I understood it seems to be this: Use a hash function b(x) to transform keys into fixed length bitvectors. Now we want to build a function b'(x) such that b'(x) = b(x) for any keys in our set, and such that b'(x) is a random value for other keys. Checking if b' and b agree will be our membership test. They construct b'(x) as h(x)· Z, where h is a vector with binary entries and Z is a matrix with binary entries. By taking all the elements we want and computing h(x) for each of them we get a bunch of vectors that we can arrange into a matrix H. Z can be found by gaussian elimination on that matrix. The name ribbon filter comes from the fact that H is constructed in a particular way that gives it a ribbon shape. That shape makes the whole thing efficient in time and space.