Bloom Filter 자료구조
안녕하세요, 오늘은 Bloom Filter 와 변종들중에 하나인 Scalable Bloom Filter 에 대해서 알아보는 시간을 가지려고 합니다. 너무 자세하거나 수학적인 설명은 배제하고 직관적인 이해를 기반으로 포스팅하겠습니다! 자세한건 그냥 논문을 보세요… Bloom Filter 란? Bloom Filter 는 집합내에 특정 원소가 존재하는지 확인하는데 사용되는 자료구조입니다. 이러한 “membership test” 용도로 사용되는 자료구조들은 Bloom Filter 외에도 다양합니다. 대표적이고 널리 알려진 것으로는 Balanced Binary Search Tree (AVL, red-black tree 등) 과 해시 테이블등이 있습니다. 이 자료구조들의 특징은 100% 정확도로 membership test 를 수행할 수 있다는 것 입니다. Bloom Filter 는 이러한 정확도를 희생해서 메모리 사이즈를 최소화하는 것을 목표로 합니다. Bloom Filter 구조 Bloom Filter 자료구조는 기다란 비트 배열로 구성됩니다. 그리고 “원소 추가” 와 “원소 검사” 연산을 수행하기 위해 서로 다른 해시 함수들이 사용됩니다. 비트 배열의 길이를 m, 해시 함수의 개수를 k 라고 하겠습니다. k개의 해시 함수들은 [0, m) 범위의 해시 값을 출력하게 됩니다. 그러면 Bloom Filter 의 2가지 연산에 대해서 알아보겠습니다. 원소 추가 추가하려는 원소에 대해서 k개의 해시 값을 계산한 다음, 각 해시 값을 비트 배열의 인덱스로 해서 대응하는 비트를 1로 세팅합니다. 원소 검사 (membership test) 검사하려는 원소에 대해서 k개의 해시 값을 계산한 다음, 각 해시 값을 비트 배열의 인덱스로 해서 대응하는 비트를 읽습니다. k개의 비트가 모두 1인 경우 원소는 집합에 속한다고 판단하고, 그렇지 않은경우 속하지 않는다고 판단합니다. 매우 간단하죠? Bloom filter by example 사이...