News for hackers. Stuff that matters.

A comment on Bloom Filters: More than a space-efficient hashmap. Parent comment

Re:Bloom Filters: More than a space-efficient hashmap by boyter on Wednesday August 11, 2021 @03:00AM (#28138927)
Ribbon filters also look promising https://engineering.fb.com/2021/07/09/data-infrastructure/ri...
[ Parent | on HN ]
Re:Bloom Filters: More than a space-efficient hashmap by thomasmg on Wednesday August 11, 2021 @03:27AM (#28139090)
Yes. Some variants of ribbon filters are very fast, and other variants (which are a bit slower thought) need very little space: only a few percent more than the theoretical lower bound.

For static sets, ribbon filters and binary fuse filters (e.g. here: https://github.com/FastFilter/xor_singleheader) are very competitive. Both are based on recent (2019 and newer) theoretical work from Stefan Walzer, e.g. this one https://arxiv.org/pdf/1907.04749.pdf

[ Parent | on HN ]
Re:Bloom Filters: More than a space-efficient hashmap by gigatexal on Wednesday August 11, 2021 @05:21AM (#28139827)
Is anyone curating the latest developments in this space? I feel like I only stumbled upon Vacuum filters and now Ribbon filters just because of the top comment on a HN thread. Is anyone doing a "latest/developments in the datastructure/algo space"?
[ Parent | on HN ]
Re:Bloom Filters: More than a space-efficient hashmap by gigatexal on Wednesday August 11, 2021 @02:27PM (#28145784)
Bonus points if someone starts this and breaks it down for the more pedestrian IQ'd folks like myself.
[ Parent | on HN ]