블룸 필터 분석(Bloom Filter)

목차

1.What is Bloom Filter ?
2.Bloom Filter component
3.How it works Bloom Filter
4.Benefits Bloom Filter
5.Probability of false positives
6.Reference

본문내용

블룸필터(Bloom filter)는 1970년도에 Burton H. Bloom이 고안한 것으로 공간 효율적인 probabilistic data structure이며 구성요소가 집합의 구성원인지 점검하는데 사용된다.
블룸 필터는 해시함수를 통해 데이터 파일의 키값을 생성하고, 키값을 기반으로 주어진 데이터가 있는지 없는지 알려주는 확률 기반의 필터이다.
False positive들이 가능하며, false negative들은 불가능하다.
데이터는 추가될 수 있으나 제거는 되지 않는다.
Counting Filter로 제거가 가능 하다.
블룸 필터는 메모리를 더 사용함으로써 자주 호출되는 함수들의 성능을 크게 향상시키는 방법 중에 하나이다.
1. What is Bloom Filter ?

해시(hash) 함수 : 해시 알고리즘 (double, triple, or others)
Bloom Filter Key : 해시 알고리즘에 의해 반환된 키값
Bloom Filter Index : Bloom Filter Key를 임의의 크기의 비트들의 블록으로 나눈 각각의 값
블룸 필터는 func:
Add() : 데이터 추가
IsExist() : 데이터의 존재 검사.
2. Bloom Filter component

m(bloom filter의 bit 사이즈) = 10
k(hashing functions의 수) = 2
2개의 해시 함수를 h1, h2
Bloom Filter 배열은 아래와 같다.
3. How it works Bloom Filter (1)

참고 자료

없음