5P by xguru 2019-12-21 | favorite | 댓글 1개

특정값이 집합에 속해있는지를 검사하는데 사용하는 블룸필터를 좀더 빠르고 작게 구현.
Cuckoo필터처럼 핑거프린트를 사용하지만 Xor하여 처리.
더 적은 비트수로 거짓양성(FP,1종 오류) 확률이 더 낮다고.
Go코드는 300줄 가량. C버전은 싱글헤더로 쉽게 사용가능. Java/C++ 버전도 있음.

실제 논문 - Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters
https://arxiv.org/abs/1912.08258

한국어로 된 블룸필터 설명 - BloomFilter는 언제 쓰나요?
https://meetup.toast.com/posts/192