Eine schnellere und kompaktere Implementierung des Bloom-Filters, der verwendet wird, um zu prüfen, ob ein bestimmter Wert zu einer Menge gehört.
Wie beim Cuckoo-Filter werden Fingerprints verwendet, aber die Verarbeitung erfolgt per Xor.
Mit weniger Bits soll die Wahrscheinlichkeit für False Positives (FP, Fehler 1. Art) noch geringer sein.
Der Go-Code umfasst rund 300 Zeilen. Die C-Version ist als Single-Header leicht nutzbar. Es gibt auch Versionen für Java/C++.
1 Kommentare
Das eigentliche Paper – Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters
https://arxiv.org/abs/1912.08258
Eine koreanische Erklärung zu Bloom-Filtern – Wann verwendet man BloomFilter?
https://meetup.toast.com/posts/192