Une implémentation plus rapide et plus compacte des filtres de Bloom, utilisés pour vérifier si une valeur donnée appartient à un ensemble.
Comme les filtres de Cuckoo, ils utilisent des empreintes, mais les traitent avec un XOR.
Avec moins de bits, ils offriraient une probabilité de faux positifs (FP, erreur de type I) encore plus faible.
Le code Go fait environ 300 lignes. La version C est fournie sous forme d’un en-tête unique, donc facile à utiliser. Il existe aussi des versions Java/C++.
1 commentaires
Article original — Xor Filters: plus rapides et plus compacts que les filtres de Bloom et de Cuckoo
https://arxiv.org/abs/1912.08258
Explication des filtres de Bloom en coréen — Quand utilise-t-on BloomFilter ?
https://meetup.toast.com/posts/192