4 ms·

Ribbon filters also look promising https://engineering.fb.com/2021/07/09/data-infrastructure/ribbon-filter/ https://engineering.fb.com/2021/07/09/data-infrastru

• thomasmg 5y ago
  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 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 https://arxiv.org/pdf/1907.04749.pdf
  • gigatexal 5y ago
    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"?
    • gigatexal 5y ago
      Bonus points if someone starts this and breaks it down for the more pedestrian IQ'd folks like myself.