Jeongchul Kim

Bloom Filter(블룸 필터) 블룸 필터(Bloom filter)는 원소가 집합에 속하는지 여부를 검사하는데 사용되는 확률적 자료 구조입니다. 1970년 Burton Howard Bloom에 의해 개발되었습니다. 그 당시 컴퓨터의 저장 공간은 매우 부족하였습니다. 사용자가 입력하는 password의 보안을 올리고자, 영어 사전에 나오는 단어에 해당하는지 검사를 개발하였습니다. 코딩을 해보자면 hash-table이나 binary-search-tree로 구현할 수 있겠으나, 그 당시의 적은 저장 공간과 메모리로 어떻게 개발할 수 있을까요? 모든 단어를 집합의 원소로 생각하고 입력으로 들어온 패스워드가 집합에 속해있는지 검색을 하는 방식으로 구현할 수 있습니다. 여기서 membership checking..