Triển khai Bloom filter dùng để kiểm tra một giá trị cụ thể có thuộc một tập hợp hay không theo cách nhanh hơn và gọn hơn.
Giống như Cuckoo filter, nó sử dụng fingerprint nhưng xử lý bằng phép XOR.
Theo đó, với số bit ít hơn, xác suất dương tính giả (FP, lỗi loại 1) còn thấp hơn.
Mã Go dài khoảng 300 dòng. Bản C là single-header nên có thể dùng dễ dàng. Cũng có phiên bản Java/C++.
1 bình luận
Bài báo gốc - Xor Filters: Nhanh hơn và nhỏ hơn Bloom filter và Cuckoo filter
https://arxiv.org/abs/1912.08258
Giải thích về Bloom filter bằng tiếng Hàn - Khi nào nên dùng BloomFilter?
https://meetup.toast.com/posts/192