Develop
2025. 5. 26.
Probabilistic data structures : Bloom Filter, Cuckoo Filter, Ribbon Filter
최근 시스템 설계 스터디를 하는중에 모르는 내용이 나와서 좀 찾아보게되었다.확률적 데이터구조 (probabilistic data structures)메모리와 성능을 절약하는 대신, 결과의 정확성에 약간의 오차를 허용하는 데이터 구조.이런 데이터 구조를 갖는 대표적은 data structures들은 bloom filter, count-min sketch 등등이 있는데 그동안 이걸 왜 몰랐나 싶을정도로 아쉬웠다. 관심있는거만 공부하니까 그랬겠지...Bloom Filter를 대표적으로 예를 들어보자. 우리가 프로그래밍적으로 Collection 안에 이 원소가 존재하는지(exist)를 확인하려면 보통 contains() 와 같은 메서드를 사용해서 결과를 가져오곤한다. 그런데 이 contains를 실행하기 위해서..