확률적 자료구조가 쓰이는 두가지 경우확률적 자료구조는..확률적 자료구조의 Operation다양한 확률적 자료구조Bloom filter Scalable Bloom FilterStable Bloom FilterCounting Bloom Filteropposite bloom filterIBF (Inverse Bloom Filter)Direct-mapped cacheLRU CacheFast Topic MatchingMinHashLSH(Locality sensitive hash)HyperLogLogCount-Min Sketch
확률적 자료구조가 쓰이는 두가지 경우
- 평균적인 성능(시간복잡도)을 보장할 때
- Skip List와 Treap
- 두 자료구조 모두 최악의 경우에는 시간복잡도가 O(N)이지만 그럴 경우가 사실상 없음
- 정확한 값이 아닌 작은 오차를 가진 근사값이여도 상관이 없을 때
- 위의 자료구조를 제외한 거의 모든 확률적 자료구조
- 대신 저장 공간이나 속도 측면에서 많은 이득을 보기위해 사용한다.
확률적 자료구조는..
- 랜덤함수 또는 해시함수를 사용함
- 실시간 처리(in-stream data processing)에 활용할 수 있는 확률적 자료구조에는 Bloom filter, HyperLogLog, Count-min Sketch가 있음
- 정확성을 위해 공간과 성능을 교환. CAP 정리와 마찬가지로 일관성 (정확성)과 가용성 (온라인) 중 하나를 선택해야함
- CAP 정리는 분산 컴퓨터 시스템에서 다음의 세 가지 조건을 모두 만족하는 것이 불가능하다는 것을 증명한 정리
- Consistency: 일관성
- Availability: 가용성
- Partition Tolerance: 파티션 내성
- P는 희생할 수 없음
확률적 자료구조의 Operation
- Membership query: 특정 요소가 집합에 포함되는지 판단
- Cardinality: 요소의 중복을 허용하지 않는 집합에서 해당 집합의 요소 개수를 반환
- Frequency: 중복을 포함하는 집합에서 특정 요소가 해당 집합에 몇 개나 포함되어 있는지 판단
다양한 확률적 자료구조
Bloom filter
NAVER D2- 확률적자료구조와 블룸필터
bloom filter의 false positive rate 를 줄이기 위해서는 bloom filter의 크기가 커야하고 검색할 원소의 수가 적어야하므로 단독 사용에는 한계가 있다
확률에 상관하지 않고 무조건 true positive라 가정한다면, 작은 크기의 블룸필터를 사용하는게 좋다. (저장공간이나 속도면에서의 개선을 위한 것이므로)
https://stackoverflow.com/questions/13263220/is-there-any-probabilistic-data-structure-that-gives-false-negatives-but-not-fal
(검색할 원소의 개수는 우리가 조절불가)
insert도 query도 o(n)? n:원소의 개수
Scalable Bloom Filter
Stable Bloom Filter
- 데이터 세트의 크기를 미리 알 수없고 메모리가 제한되어있는 상황에 적합
Counting Bloom Filter
opposite bloom filter
IBF (Inverse Bloom Filter)
- false negative
- IBF 는 충돌을 처리하지 않는 m 버킷 의 고정크기의 해시 맵과 비슷한 방식으로 작동 하지만 lock없이 동시성을 제공
Direct-mapped cache
LRU Cache
LRUcache의 크기는,,?
LRU 구현하기(hashmap과 double linked list를 사용하는게 가장 효율적, o(1))
LRUCache or 손실해시테이블(lossy hash table), lossy dictionary 는 데이터구조가 빠른 o(1)조회로 false negative 가 있음.
따라서 맞았다는 결과는 신뢰할 수 있음
inverse bloom filer(IBF)도 false negative만 있음
LRU cache 자체에는 lock이 없으나
동시성 확보를 위해서는 lock이 필요함(멀티스레드)
허나, lock을 사용할경우 성능 문제가 발생(느림)
https://github.com/facebook/rocksdb/blob/master/cache/lru_cache.h 을 통해서는 lock을 사용하고도 성능 문제를 개선함
single thread 에서는 doubly linked list로 구현 하는것이 좋다. head에 아이템을 추가하고 tail의 아이템을 삭제,
각 항목의 나이를 타임스탬프로 표시하면 lock 필요없어 삽입, 읽기가 빠르나 삭제는 느림(정렬이 일반적으로 O(N*logN))
Fast Topic Matching
MinHash
- 두 세트 간의 유사성을 신속하게 추정
- 중복 된 본문 검색 및 문서 클러스터링 비교 등
LSH(Locality sensitive hash)
HyperLogLog
- 메모리를 매우 적게 사용하여 집합의 원소의 개수를 추정
Count-Min Sketch
- 특정 요소의 빈도를 추정