블룸필터

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

블룸필터(Bloom Filter)

개요

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

활용

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

같이보기

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

단체 : 공공기관, 대학교, 협회, 법무법인, 블록체인 지원기관 □■⊕ 연구소 • 학회 451리서치 • MIT 디지털화폐 이니셔티브 • 경희대학교 블록체인학회 • 고려대학교 블록체인연구소 • 고려대학교 블록체인학회 • 고려대학교 암호화폐연구센터 • 광동챈하이핀테크연구원 • 국가블록체인경제과제연구팀 • 국립전자암호연구소 • 국회 4차산업혁명포럼 • 글로벌 칼리지 블록체인 얼라이언스 • 다빈치연구소 • 단국대학교 자율형 블록체인 융합연구소 • 독일 공학한림원 • 동국대학교 블록체인연구센터 • 디사이퍼(서울대학교 블록체인학회) • 딜로이트 블록체인 연구소 • ㈜링스톤 • 매사추세츠 공과대학교 미디어랩 • 메이든 • 미국경제연구소 • 시큐리티토큰연합 • 버클리 블록체인 엑셀러레이터 • 블록데이터 • 블록엔 • 블록체인 기후연구소 • 블록체인 리서치 인스티튜트 • 블록체인법학회 • 블록체인앳버클리 • 블록체인 앳 연세 • 서울대학교 전력연구소 • 성균관대학교 블록체인학회(스콘) • 소프트웨어정책연구소 • 싸이디블록체인연구원 • 씨씨이지(CCEG) • 아이비이포럼(IBE포럼) • 아시아블록체인산업연구원 • 아시아블록체인연구원 • 아시아 자본시장연구소 • 암호자산 연구소 • 와이즈만 연구소 • 오스트리아 블록체인 센터 • 오픈머니 이니셔티브 • 와이스 레이팅스 • 인민대학 핀테크연구소 • 인텔리콘연구소 • 인티콜롬비아 리서치 그룹 • 응용과학기술연구원 • 중국과학원 소프트웨어연구소 • 중국공정원 • 중국모바일연구원 • 중국블록체인연구센터 • 중국블록체인응용연구센터 • 중국전자정보산업발전연구원(CCID) • 중국정보통신연구원 • 중국컴퓨터학회 • 중국전자기술표준화연구원 • 중앙대학교 블록체인서비스 연구센터 • 중차오블록체인기술연구원 • 지구라트 글로벌기술연구소 • 차세대융합기술연구원 • 칭화대학 인터넷산업연구원 • 키프로스 블록체인 테크놀로지스 • 탭스콧그룹 • 플래닛비 • 한국금융ICT융합학회 • 한국디지털화폐연구원(KDC) • 한국블록체인산업학회 • 한국블록체인학회 • 한국정보통신산업연구원 • 한국정보통신설비학회 • 한국통신학회 • 한국핀테크학회 • 한양대학교 블록체인 연구교육그룹 • 후룬연구소 • 홍콩 혁신과학기술부 교육기관 2019년 블록체인 캠퍼스 • 고려대학교 블록체인 전략 전문경영자과정 • 고려대학교 제4기 블록체인 전략 전문경영자과정 • 대시타일랜드 • 두바이 블록체인 센터 • 룬사테크놀로지 • 룬사학원 • 마이애미 블록체인 센터 • 마이애미 비트코인 센터 • 마켓 리벨리온 • 멀티캠퍼스 • 바이낸스아카데미 • 블로코아카데미 • 블록샬라 • 블록체인아이에스티 • 블록체인아카데미 • 비즈럽트 • 비캐피탈리스트 • 비티원랩 • 빅데이터 얼라이언스 • 슈퍼제로 블록체인 비즈니스 스쿨 • 엠아이티 홍콩 혁신노드 • 즈미대학(크립토 칼리지) • 진써스쿨 • 체인스아카데미 • 칭화엑스랩 • 컨스트럭션 블록체인 컨소시엄 • 포스텍 블록체인 최고경영자 과정 • 프랑크푸르트스쿨 블록체인센터 • 프리코드캠프 • 플루럴사이트 • 한국블록체인연구교육원(월튼체인연구교육원) • 홍콩대학 평생교육원 • 후오비대학 지원기관 MIT 프레스 • 광둥 파이낸셜 하이테크단지 블록체인+핀테크산업 인큐베이팅센터 • 국가국제금융문제사무국 • 국제노동기구 • 글로벌 디지털 파이낸스 • 글로벌핀테크산업진흥센터 • 기술협력센터 • 나카모토 하우스 • 노스캐롤라이나 블록체인 이니셔티브 • 뉴아메리카 • 뉴캐슬헬릭스 • 대전창조경제혁신센터 • 독일스타트업그룹 • 디스트리뷰티드 벤처스 • 디아이지아이 • 디지다오 • 라디앤파트너 • 레벨39 • 로이드인증원 • 마네투 • 맥케슨 • 모덱스 • 미국보험서비스협회 • 미국인권재단 • 미국 통화감독청 • 부산 블록체인 특구 추진단 • 블록체인포임팩트 • 블록체인 애플리케이션 커뮤니티 • 블록체인 액셀러레이션 재단 • 비바리즈캐피탈 • 비에스아이그룹 • 비트트라이브 랩 • 서울블록체인지원센터 • 서울파이낸셜포럼 • 선전문화재산권거래소 • 세피어 • 슈아 • 슈타트비엔나 • 스리랑카핀테크협회 • 스티비츠 • 시카고 블록체인 센터 • 시타 • 싱가포르 정보통신 미디어 개발청 • 아이알유 • 아티팩츠 • 알원스페이스 • 어피니티 아이티 시큐리티 • 업비트투자자보호센터 • 윈윈솔루션 • 오에스디 • 오피리아 • 유엔유-이지오브이 • 유엔 무역 촉진 및 전자 비즈니스센터 • 이더리움 커뮤니티 재단 • 이아이파스 • 이오스노드원 • 자루나 • 정보기술연구소 • 중관촌빅데이터산업연합 • 중국금융인증센터 • 지지비에이 서부스위스투자 • 첸하이연합거래센터 • 충북블록체인진흥센터 • 카필렌도 • 컨퍼드 • 코어레저 • 토큰경제실천연맹 • 토큰경제협회 • 토킹데이터 • 트러스티드 블록체인 이니셔티브 • 패러다임글로벌 • 퐁짓 • 푸르덴셜파이낸셜 • 피피케이펍 • 핀테크 앤 이노베이션 그룹 • 한국 분산원장기술표준포럼 • 한국핀테크지원센터 • 헤이시블록체인랩스 • 헬레닉 블록체인허브 • 호들팩 자선단체 가비 • 기브크립토 • 디지털문예부흥재단 • 바이낸스 자선재단 • 완커재단 • 왓록스재단 • 위키미디어재단 • 정더자선재단 • 챈 저커버그 이니셔티브 공익단체 다음세대재단 • 에스이이 서남프로젝트센터 • 오이스트재단 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반