Bloom Filter

Stream 형태의 무한한 데이터를 다루기 위한 알고리즘 중의 하나는 '필터링 알고리즘'이다. 스트림에서 X라는 속성을 가지는 데이터들을 걸러내는 알고리즘으로써 여러 메일들의 스트림을 입력받았을 때, 스팸메일을 걸러주는 프로그램등이 이 필터링 알고리즘을 적용한 예에 속한다. Filtering Data Streams 이전 포스팅의 예제와 마찬가지로 데이터 스트림의 각 원소는 Tuple(튜플, 순서쌍)의 형태로 입력이 된다. 이때 필터링 알고리즘의 문제는 S라는 Key set이 들어왔을 때, 입력되는 튜플들의 스트림 중 S에 속하는 튜플들을 걸러내는 것이 된다. 이를 해결하기 위한 가장 명백한(Obvious) 방법은 해시 테이블(Hash Table)을 이용하는 것이다. 해시 함수는 같은 키 값이 들어오면 무..

2019.04.11