확률적 자료구조 종류 및 관련 링크

소개

확률적 자료구조인 Bloom filter를 공부하다가, 다른 확률적 자료구조는 어떠한 것이 있는지 궁금했기에 검색을 해봤더니 위키피디아에서 'Probabilistic data structures' 카테고리 페이지를 찾을 수 있었습니다. [링크]

확률적 자료구조 리스트

그 중, 한글 자료가 있는 자료구조를 추려 리스트로 만들고 링크를 걸어보았습니다.

Bloom filter

• 확률적 자료구조를 이용한 추정 - 원소 포함 여부 판단(Membership Query)과 Bloom Filter, 송기선님의 포스트 [링크]

Count-min sketch

• 확률적 자료구조를 이용한 추정 - 빈도(Frequency) 추정을 위한 Count-Min Sketch, 송기선님의 포스트 [링크]

HyperLogLog

• 확률적 자료구조를 이용한 추정 - 유일한 원소 개수(Cardinality) 추정과 HyperLogLog, 송기선님의 포스트 [링크]

Locality-sensitive hashing

• Random Projection and Locality Sensitive Hashing - lovit님의 포스트 [링크]

MinHash

• MinHash란?, wan2land님의 포스트 [링크]

SimHash

• Near Duplicate Documents Detection SimHash 계산 방법, aragorn님의 포스트 [링크]

Skip List

• Skip List, 김종욱님의 포스트 [링크]

Treap

• Treap, namnamseo님의 포스트 [링크]

그 외 자료

그 이외에도 이러한 자료들을 찾을 수 있었습니다.

• 실시간 추천엔진 머신한대에 구겨넣기, 하용호님 포스트 [링크]
• 게임 서비스 플랫폼을 지탱하는 알고리즘, 전이삭님 포스트 [링크]

전이삭님의 유튜브 발표 영상도 있어 같이 링크합니다. [링크]

정리

1. 평균적인 성능(시간복잡도)을 보장할 때 쓰입니다.
2. 정확한 값이 아닌 작은 오차를 가진 근사값이여도 상관이 없을 때 쓰입니다. 대신 저장 공간이나 속도 측면에서 많은 이득을 볼 수 있습니다.