Bloom Filter란

Bloom Filter는 1970년 Burton H. Bloom이라는 분의 "Space/time trade-offs in hash coding with allowable errors"이라는 논문을 통해 처음 공개되었습니다.

특정 원소가 집합에 속하여 있는지 검사하는데 사용하는 확률형 자료구조 입니다.

여기까지만 보면, Map이라는 좋은 자료구조가 있는데 왜? 쓰지? 라는 생각이 들 수 있습니다.

그치만 Bloom Filter란 친구는 Map보다 빠르고 공간을 적게 소모하여 해당 값이 존재하는지 확인할 수 있습니다.

어떻게? Map보다 공간을 적게 소모하고 빠르게 조회할 수 있는거지?

지금부터 Bloom Filter의 방식과 활용 방안에 대하여 이야기해보고자 합니다.

Bloom FIlter 작동 방식

입력

모든 값이 0으로 초기화 되어져 있는 m크기의 비트 배열이 선언됩니다.
데이터가 들어온다면 이를 hash함수를 태워 m보다 작은 수의 k개의 수로 만듭니다.
비트배열의 k개 index의 값을 1로 바꿉니다.

검색

검색하고자 하는 데이터를 hash 함수를 태워 k개의 숫자로 바꿉니다.
m크기의 비트배열에 k개 index의 값이 모두 1인지 확인합니다.
모두 1이면 해당 데이터가 있다는 것이고, 아닐 경우 해당 데이터가 존재하지 않다는 의미입니다.

예시

x(2, 6, 14), y(5, 12, 17), z(4, 6, 12)라는 데이터가 있다 라는 것을 알고 있는 상태
w(5, 14, 16)라는 데이터가 있는지 확인하기 위한 상태

문제점

처음에 말했던 대로, 해당 자료구조는 확률형 자료구조 입니다.
- 해당 데이터가 없어도, 존재할 수 있다고 합니다.
삭제 연산이 불가능하다
- 데이터의 값들이 변경이 된다면, Bloom Filter를 재선언 후, 데이터를 넣는 작업을 거쳐야 합니다.

사용하는 이유

이러한 문제점들이 있는데도 Bloom Filter를 사용하는 이유가 있습니다.

데이터가 없을 때, 있다고 할 순 있지만 있는데 없다곤 할 수 없습니다.
m개의 비트배열만큼의 적은 메모리를 소모하고, O(k)의 시간 복잡도를 가지고 있다.
bloom filter를 먼저 태운 후, 데이터가 있는 경우 IO 요청이 들어가게 되므로, 전처리 기능을 수행한다.
hashMap과 같은 경우 hash 충돌이 발생할 경우, hash 함수를 다시 태우거나 링크드리스트 방식으로 추가하는 반면, Bloom Filter는 덮어쓰기를 통해 처리가 가능하다.

구현

Bloom FIlter는 google의 외부 라이브러리인 guava를 import하여 사용이 가능합니다.

public static void bloomFilterTest(){
        long count = 1000;
        double falsePositiveProbability  = 0.1;

        BloomFilter<String> bloomFilter = BloomFilter.create(
            Funnels.stringFunnel(StandardCharsets.UTF_8),
            count,
            falsePositiveProbability
        );

        bloomFilter.put("apple");
        bloomFilter.put("banana");
        bloomFilter.put("cherry");

        System.out.println("Is 'apple' in Bloom Filter? " + bloomFilter.mightContain("apple")); // true
        System.out.println("Is 'orange' in Bloom Filter? " + bloomFilter.mightContain("orange")); // false
    }

현재 사용중인 곳들

728x90

저작자표시 비영리 변경금지