검수요청.png검수요청.png

블룸필터

위키원
gyongmo (토론 | 기여)님의 2019년 8월 16일 (금) 10:09 판 (새 문서: '''블룸필터(Bloom Filter)'''는 특정 원소가 집합에 속하는지 검사하는데 사용할 수 있는 확률형 자료 구조이다.<ref name="heejin">, 〈[https://steemit...)
(차이) ← 이전 판 | 최신판 (차이) | 다음 판 → (차이)
이동: 둘러보기, 검색

블룸필터(Bloom Filter)는 특정 원소가 집합에 속하는지 검사하는데 사용할 수 있는 확률형 자료 구조이다.[1]

블룸필터(Bloom Filter)

개요

블룸필터(Bloom Filter)는1970년 Burton Howard Bloom에 의해 고안되었다. 블룸 필터에 의해 어떤 원소가 집합에 속한다고 판단된 경우 실제로는 원소가 집합에 속하지 않는 긍정 오류가 발생하는 것이 가능하지만, 반대로 원소가 집합에 속하지 않는 것으로 판단되었는데 실제로는 원소가 집합에 속하는 부정 오류는 절대로 발생하지 않는다는 특성이 있다. 집합에 원소를 추가하는 것은 가능하나, 집합에서 원소를 삭제하는 것은 불가능하다. 집합 내 원소의 숫자가 증가할수록 긍정 오류 발생 확률도 증가한다.[2]

등장배경

역사

특징

활용

집합의 크기가 굉장히 크거나 집합의 속해있는 원소의 크기가 커서 원소가 집합에 속해있는지 정확히 판단하는데 시간이 오래걸리는 경우 이 과정의 전처리 과정으로 Bloom Filter를 이용해서 아예 집합에 속할 일이 없는 원소를 미리 걸러낼 수 있다. Google Chrome은 위험한 사이트 검사에 Bloom Filter를 사용한다고 알려져 있다. Bloom Filter를 사용해서 빠르게 대충 검사한 다음, 의심이 가는 사이트인 경우 데이터베이스에 다시 정확하게 검사하는 것이다. 아마 위험 사이트 데이터베이스의 크기가 크고, 검사 요청이 굉장히 빈번하게 일어나기 때문에 Bloom Filter를 전처리 과정으로 사용해서 데이터베이스 요청 부하를 줄이는 것으로 보인다. 비트코인도 내부적으로 Bloom Filter를 사용하는 것으로 알려져 있다. 보통은 Disk IO를 줄이기 위한 최적화 방법으로 많이 사용한다.[1]

종류

문제점.대안

평과와 전망

각주

  1. 1.0 1.1 , 〈알아두면 좋은 자료 구조, Bloom Filter〉, 《steemit》, 2017
  2. 블룸 필터〉, 《위키백과》

참고자료

같이보기

  검수요청.png검수요청.png 이 블룸필터 문서는 블록체인 지원기관에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.