Cuckoo filter는 2014년에 소개된 확률적 자료구조로, 특정한 원소가 집합에 속하는지 여부를 확인합니다.
해당 필터에서 false positive는 허용되나 false negative는 허용되지 않습니다. 즉, 원소가 집합에 없는데도 있다고 나올 수는 있지만, 있는데 없다고 나올 수는 없습니다.
Cuckoo filter는 블룸 필터와 비슷한데, 블룸 필터는 이미 좋은 글들이 많이 있으니 찾아보시면 도움이 되실 수 있습니다.
Cuckoo filter는 Cuckoo hashing(뻐꾸기 해싱)을 사용합니다. 그래서 Cuckoo filter이기도 하고요. Cuckoo hashing 역시 좋은 글들이 많이 있습니다.
그렇다면 블룸 필터와 Cuckoo filter의 차이점은 무엇일까요?
여러 구현의 차이가 있지만, 가장 대표적인 특성은 Cuckoo filter의 공간 사용 효율성에 있습니다.
Cuckoo hashing을 사용하는 Cuckoo filter는 유사한 성능에서 블룸 필터보다 낮은 공간 오버헤드를 달성합니다.
