어떠한 집합 S에 요소 E가 속할 수도 있는지/속하지 않는지 빠르게 파악할 수 있도록 해주는 자료구조입니다.
S에 E가 없을 때는 블룸 필터를 통해 확실히 없다는 사실을 알 수 있지만, E가 있을 때는 블룸 필터로는 확실히 E의 존재 여부를 확정할 수 없습니다. 따라서, 블룸 필터를 통해 S에 E가 존재함을 알아내더라도 실제 S에 E가 속하는지 살펴보아야 합니다.
구현
블룸 필터는 복수의 해시 함수와 배열로 구성됩니다.
해시 함수는 아래의 조건을 만족할수록 좋습니다.
- fast
- evenly and randomly distributed
- collisions are okay
- collisions are rare as possible
블룸 필터에 추가
요소 E를 추가한다고 가정합시다.
X = hash_function(E)
Array[X] = 1
각 해시 함수에 대해 위와 같이 해줍니다.
블룸 필터에서 색인
요소 E를 블룸 필터에서 색인한다고 하면,
모든 해시 함수에 대해
X = hash_function(E)
Array[X] == 1 가 만족하면 E는 실제 집합에 존재할 수 도 있음을 나타냅니다.
만약 하나라도 값이 0이라면 , 실제 집합에는 E가 없음을 나타냅니다.
사용 사례
-
CDN
3/4 정도의 데이터는 딱 한 번만 접근된다고 합니다. 따라서, CDN provider는 블룸 필터를 사용하여 해당 데이터가 과거에 접근된 이력이 있는지 확인하고, 블룸 필터를 통해 이력이 있다고 판단되면 캐싱을 하게됩니다. -
DBMS
NoSQL에서는 존재하지 않는 키에 대한 색인의 cost가 만만치않다고 합니다. 따라서, 블룸 필터를 사용해 최대한 성능을 향상시키고자 NoSQL DBMS에 사용됩니다. (RDB인 PostgreSQL에도 사용된다고 합니다.)
결론
블룸 필터는 정확한 결과는 아니지만, 빠르게 어떠한 요소가 실제 집합에 없는지 알 수 있다는 장점이 있습니다. 따라서, 성능 향상을 위해 많은 부분에 사용됩니다.
