ITPE * JackerLab

개요Cuckoo Filter는 Bloom Filter의 한계를 극복하기 위해 개발된 확률적 자료구조로, 빠른 멤버십 쿼리, 낮은 False Positive 확률, 그리고 효율적인 삭제(delete) 연산을 지원합니다. 인서트 실패 확률을 낮추면서도 메모리 사용량과 성능을 최적화하여, 데이터베이스, 네트워킹, 캐싱 시스템 등 다양한 분야에서 널리 활용되고 있습니다.1. 개념 및 정의 항목 내용 정의해시 기반 버킷에 작은 지문(fingerprint)을 저장하여 멤버십 쿼리 및 삭제를 지원하는 공간 효율적 확률적 자료구조목적빠르고 공간 절약적인 멤버십 테스트와 삭제 지원필요성Bloom Filter의 삭제 불가성과 False Positive 문제를 개선Cuckoo Filter는 특히 삭제와 동적 크기 조정이 ..

개요Bloom Filter는 주어진 요소가 집합에 속하는지를 빠르고 공간 효율적으로 검사할 수 있는 확률적 자료구조입니다. 일부 허위 긍정(False Positive)은 허용하지만, 허위 부정(False Negative)은 발생하지 않는 특성을 가지며, 대규모 데이터셋에서 빠른 membership query(멤버십 검사)가 필요한 다양한 분야(검색 엔진, 네트워크 라우팅, 데이터베이스 캐시 등)에서 널리 사용됩니다.1. 개념 및 정의 항목 내용 정의비트 배열과 다수의 해시 함수를 이용해 집합 멤버십을 테스트하는 공간 효율적 확률적 자료구조목적빠르고 적은 메모리 사용으로 존재 여부 검사필요성초대규모 데이터셋에 대해 공간-시간 복잡도 최적화 필요Bloom Filter는 메모리 제약이 큰 환경에서도 고속 검..