이더리움 - 블룸 필터(Bloom filter)

원소가 집합에 속하는지 여부를 검사하는데 사용되는 확률적 자료 구조

 

 

 

 

[동작] add(), isExist()

 

추가하는 add(), 하나는 존재하는지에 대한 isExist()

add() 할 때, key를 hash 알고리즘을 이용해서 여러 개의 hash 값을 나누고, 버킷이라는 저장장소에 저장한다. 그래서 isExist할때 그 버킷를 활용해서 있는지를 확인

 

http://knight76.tistory.com/entry/%EC%B9%B4%EC%82%B0%EB%93%9C%EB%9D%BCcassandra%EC%9D%98-%EB%B8%94%EB%A3%B8%ED%95%84%ED%84%B0-bloom-filter

카산드라(cassandra)의 블룸필터 (bloom filter)

 

[특징]

원소가 집합에 속한다고 판단된 경우 실제로는 원소가 집합에 속하지 않는 긍정 오류가 발생하는 것이 가능

원소가 집합에 속하지 않는 것으로 판단되었는데 실제로는 원소가 집합에 속하는 부정 오류는 절대로 발생하지 않는다

 

집합 내 원소의 숫자가 증가할수록 긍정 오류 발생 확률도 증가

 

집합에 원소를 추가하는 것은 가능하나,

집합에서 원소를 삭제하는 것은 불가능

 

 

[활용]

1) 검색 가능 암호화

- Secure Index:고정크기 데이터 구조(Bloom filter) 저장

 

2) NoSQL 기술 (HBase)

- 저장시 실시간 쿼리를 위한 Block 캐시와 Bloom filter

 

3) 구글의 데이터 차원 축소 기술

- 새로운 피쳐가 기존 모델에 추가되는 것을 최소화

 

4) 이더리움 

- P2P 네트워크 상에서 유용한 트랜잭션만 식별하기 위해 사용

 

5) Oracle

- Slave 간의 communication 데이터 량은 물론 Join 에 의한 부하를 효과적으로 줄여 성능을 개선

 

https://www.kdata.or.kr/info/info_04_view.html?field=&keyword=&type=techreport&page=16&dbnum=183978&mode=detail&type=techreport

데이터 기술 동향 < 정보마당 - 한국데이터산업진흥원

 

 

 

https://medium.com/@joonmo.yang/invertible-bloom-lookup-table-37600927cfbe