데이터 분석

확률적 기반 자료구조

블룸 필터
- 어떤 원소가 집합에 속해 있는지를 판단하는 확률기반 자료구조
- 데이터가 없는지 100%로 확인 가능, 하지만 데이터가 있는지는 정확히 알 수 없음
- 어떤 원소가 집합에 속한다고 판단된 경우, 실제로는 원소가 집합에 속하지 않는 긍정 오류가 발생할수 있다.
- 하지만 반대로 원소가 집합에 속하지 않는 것으로 판단되었는데, 실제로 원소가 집합에 속하는 부정 오류는 절대로 발생하지 않는 특성이 있다.
- 집합에 원소를 추가하는 것은 가능하나, 집합에서 원소를 삭제하는 것은 불가능하다. 집합 내 원소의 숫자가 증가할수록 긍정 오류 발생 확률도 증가한다.
하이퍼로그로그
- 적은 메모리로 집합의 원소 개수를 추정할 수 있는 방법
- 하나의 메모리에 모두 담을 수 없을 정도로 원소의 개수가 많을 때, 정확하지 않지만 최대한 정확한 값을 상대적으로 적은 메모리만 사용해 얻고 싶을 때 사용할 수 있는 방법