5 ms·

> check the literature for various alternatives that are better in specific situations For direct replacements, see Xor(+)-Filters: https://arxiv.org/abs/1912.

by f_devd 1y ago

> check the literature for various alternatives that are better in specific situations For direct replacements, see Xor(+)-Filters: https://arxiv.org/abs/1912.08258 https://arxiv.org/abs/1912.08258 and the subsequent evolution into Binary Fuse Filters: https://arxiv.org/abs/2201.01174 https://arxiv.org/abs/2201.01174

samuel 1y ago
Interesting, but not quite the same: Xor and binary fuse filters require access to the full set of keys at construction time. In this sense, they are immutable. Alternatives have typically a fixed memory usage and a maximal capacity, but they also allow more flexibility such as progressive construction (adding keys one by one).
virexene 1y ago
I may have missed something when skimming the paper, but it sounds like Xor filters are constructed offline and can't be modified efficiently afterwards, whereas Bloom filters can be inserted into efficiently. So they don't seem to be an exact replacement
- f_devd 1y ago
  No, you are correct. I misremembered with cuckoofilters.
sparkie 1y ago
Also quite recent are Ribbon filters: https://arxiv.org/abs/2103.02515 https://arxiv.org/abs/2103.02515 But these, and xor/binary-fuse-filters are only direct replacements for Bloom filters in some problems. There are still problems for which Bloom filters are a better solution. Bloom filters have the advantage that the filter produced by adding two elements, is the same as the bitwise-or of a pair of filters made by adding each element separately. bloom([x, y]) == bloom([x]) | bloom([y]) Also, the filter produced by bitwise-and, `bloom([x]) & bloom([y])`, cannot have any bits set in it which are not also set by `bloom([x, y])`. We can assert that bloom([x]) & bloom([x, y]) == bloom([x]) bloom([y]) & bloom([x, y]) == bloom([y]) (bloom([x]) & bloom([y])) | bloom([x, y]) == bloom([x, y]) There are practical applications that this can provide which are not satisfied by the "optimized" variants. The bitwise-or does set union (or least upper bound), and the bitwise-and does a set intersection (or greatest lower bound), though the filter produced by `bloom([x, y])` has a higher false positive rate than the filter produced by `bloom([x]) & bloom([y])`. bloom([x]) | bloom([y]) == bloom([x, y]) 🡥 🡤 bloom([x]) bloom([y]) 🡤 🡥 bloom([x]) & bloom([y])
- f_devd 1y ago
  Also based on Ribbon, the BuRR filters: https://arxiv.org/pdf/2109.01892 https://arxiv.org/pdf/2109.01892 which seem to get very close to the theoretical optimum, 0.1%-0.5% overhead comparatively

by f_devd 1y ago

samuel 1y ago

Interesting, but not quite the same: Xor and binary fuse filters require access to the full set of keys at construction time. In this sense, they are immutable. Alternatives have typically a fixed memory usage and a maximal capacity, but they also allow more flexibility such as progressive construction (adding keys one by one).

virexene 1y ago

I may have missed something when skimming the paper, but it sounds like Xor filters are constructed offline and can't be modified efficiently afterwards, whereas Bloom filters can be inserted into efficiently. So they don't seem to be an exact replacement

f_devd 1y ago
No, you are correct. I misremembered with cuckoofilters.

sparkie 1y ago

Also quite recent are Ribbon filters: https://arxiv.org/abs/2103.02515 https://arxiv.org/abs/2103.02515 But these, and xor/binary-fuse-filters are only direct replacements for Bloom filters in some problems. There are still problems for which Bloom filters are a better solution. Bloom filters have the advantage that the filter produced by adding two elements, is the same as the bitwise-or of a pair of filters made by adding each element separately. bloom([x, y]) == bloom([x]) | bloom([y]) Also, the filter produced by bitwise-and, `bloom([x]) & bloom([y])`, cannot have any bits set in it which are not also set by `bloom([x, y])`. We can assert that bloom([x]) & bloom([x, y]) == bloom([x]) bloom([y]) & bloom([x, y]) == bloom([y]) (bloom([x]) & bloom([y])) | bloom([x, y]) == bloom([x, y]) There are practical applications that this can provide which are not satisfied by the "optimized" variants. The bitwise-or does set union (or least upper bound), and the bitwise-and does a set intersection (or greatest lower bound), though the filter produced by `bloom([x, y])` has a higher false positive rate than the filter produced by `bloom([x]) & bloom([y])`. bloom([x]) | bloom([y]) == bloom([x, y]) 🡥 🡤 bloom([x]) bloom([y]) 🡤 🡥 bloom([x]) & bloom([y])

f_devd 1y ago
Also based on Ribbon, the BuRR filters: https://arxiv.org/pdf/2109.01892 https://arxiv.org/pdf/2109.01892 which seem to get very close to the theoretical optimum, 0.1%-0.5% overhead comparatively