Feature Description
For a variety of use cases, we need to be able to support bucketing. Bucketing is when one or more elements of a database exist in one address. All it really is, is a particular DB layout that changes what would be a sparse database into a packed database. For example, let's say there are 2^18 items, each 128 bits long, uniformly distributed. Storing these items in their native format would require a sparse database with 128-bit addresses, or something like cuckoo hashing. Another approach is to use 2^16 buckets, with on average 4 items per bucket. The first 16-bits of the item is used as the bucket address, and then the remaining bits are stored within the bucket.
Is your feature request related to a problem?
This is needed to efficiently support PSI (and PSI-CA) over sparse databases.
Feature Description
For a variety of use cases, we need to be able to support bucketing. Bucketing is when one or more elements of a database exist in one address. All it really is, is a particular DB layout that changes what would be a sparse database into a packed database. For example, let's say there are 2^18 items, each 128 bits long, uniformly distributed. Storing these items in their native format would require a sparse database with 128-bit addresses, or something like cuckoo hashing. Another approach is to use 2^16 buckets, with on average 4 items per bucket. The first 16-bits of the item is used as the bucket address, and then the remaining bits are stored within the bucket.
Is your feature request related to a problem?
This is needed to efficiently support PSI (and PSI-CA) over sparse databases.