블룸필터 썸네일형 리스트형 Bloom filter (블룸 필터) 란? 블룸 필터 (Bloom filter) 는 집합안에 들어있지 않은, 원소를 걸러내기 위해 사용됩니다. 하지만 100% 걸러낼 수 는 없습니다. 예를 들어, 집합에 N개의 원소가 있고, bloom filter를 만드는데, M개의 hash function을 사용한다고 합시다. N 사이즈의 bitmap을 정의합니다 (bitmap은 1 아니면 0, 데이터 사이즈 작음) 각 원소는 각 hash function을 거쳐 M개의 해시 값, bitmap index 를 리턴합니다. bitmap의 M 개의 위치에 1로 업데이트 해줍니다. -> 그럼, 총 M*N번 업데이트하게 됩니다. 이 때, 다른/같은 원소가 다른/같은 hash function을 통해 이미 1로 표시된 중복된 index 위치를 return할 수 있습니다. (.. 더보기 이전 1 다음