블룸 필터에서 삭제할 키의 비트를 지우면 왜 다른 키도 없다고 나올 수 있나요?

여러 키가 같은 비트를 공유하므로 한 키 삭제를 비트 0으로 표현하면 남은 키의 검사도 음성이 될 수 있습니다. 기본 블룸 필터의 거짓 음성 없음 보장을 임의 삭제가 깨뜨립니다.

동작 원리와 전제

counting Bloom filter는 비트 대신 카운터를 사용해 삽입 때 증가·삭제 때 감소시킬 수 있습니다. 그러나 존재하지 않은 키를 삭제하거나 중복 삽입 횟수를 잘못 관리하면 카운터가 틀어지고 거짓 음성이 생길 수 있습니다.

선택과 실패 처리

카운터 overflow·포화·동시 갱신·메모리 비용을 관리합니다. 삭제가 드물면 원본 집합으로 새 필터를 재구축하는 편이 단순할 수 있습니다. 재구축 중 신규 삽입·삭제를 놓치지 않게 snapshot과 증분을 연결합니다.

구체적인 사례와 검증

키 A와 B가 같은 비트를 공유할 때 A 삭제로 비트를 0으로 만들면 B 검사도 실패할 수 있습니다. 카운터라면 A·B 삽입 후 2이고 A 삭제 후 1이 남아 B를 보존합니다. 그러나 A를 두 번 삭제하면 다시 0이 되어 같은 문제가 생깁니다. 삭제의 존재·횟수를 원본 상태와 맞추는 이유입니다. 카운터가 포화됐을 때 단순 감소를 허용하면 실제 참조 수를 잃을 수 있어 구현의 포화 정책과 재구축을 확인합니다. 동시 증가·감소도 원자적이어야 하며 메모리 최적화가 정확한 부재 판단의 전제를 깨뜨리지 않도록 시험하겠습니다.

충돌 키·중복 삽입·반복 삭제·카운터 경계·재시작을 시험합니다. 필터는 권위 저장소가 아니며 부재 판정을 쓰기 전파와 맞춰야 합니다. 삭제 지원이라는 이름이 모든 잘못된 업데이트까지 안전하게 만든다는 뜻은 아닙니다.