Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters [r-libre/1857]

Graf, Thomas Mueller et Lemire, Daniel (2020). Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters. Journal of Experimental Algorithmics, 25 (1). https://doi.org/10.1145/3376122

Fichier(s) associé(s) à ce document :

PDF - Xor_Filters__Faster_and_Smaller_Than_Bloom_and_Cuckoo_Filters.pdf
Contenu du fichier : Manuscrit soumis (avant évaluation)
Licence : Creative Commons CC BY.

Télécharger

Catégorie de document :	Articles de revues
Évaluation par un comité de lecture :	Oui
Étape de publication :	Publié
Résumé :	The Bloom filter provides fast approximate set membership while using little memory. Engineers often use these filters to avoid slow operations such as disk or network accesses. As an alternative, a cuckoo filter may need less space than a Bloom filter and it is faster. Chazelle et al. proposed a generalization of the Bloom filter called the Bloomier filter. Dietzfelbinger and Pagh described a variation on the Bloomier filter that can be used effectively for approximate membership queries. It has never been tested empirically, to our knowledge. We review an efficient implementation of their approach, which we call the xor filter. We find that xor filters can be faster than Bloom and cuckoo filters while using less memory. We further show that a more compact version of xor filters (xor+) can use even less space than highly compact alternatives (e.g., Golomb-compressed sequences) while providing speeds competitive with Bloom filters.
Déposant:	Lemire, Daniel
Responsable :	Daniel Lemire
Dépôt :	17 déc. 2019 20:22
Dernière modification :	09 oct. 2020 15:22

Actions (connexion requise)

RÉVISER