# Probability Data Structure의 정의

Acceptably Inaccurate.

Probability Data Structure는 빅데이터 같이 아주 큰 데이터에 대해 정확하지 않지만 수용 가능한 오차 범위 안의 근사값을 알려주는 추정 방법이다.

예를 들면 새로운 구글 계정을 만들 때, 이미 있는 아이디인지 어떻게 빠르게 알 수 있을까? 맞춤법 검사를 하는 프로그램이라면 어떻게 수 억 개의 사전에 있는 단어들을 단 몇 초 만에 살펴볼 수 있을까?

# 빅데이터 처리와 관련된 세가지 지표

큰 데이터를 처리하기 위해서 세 가지를 고려한다: time complexity, memory size, approximation. 시간 복잡도(time complexity)는 데이터의 양이 증가할 때 얼마나 빠르게 처리해야하는 양이 늘어나는 지에 관한 지표이다. 아래 표를 보면 데이터 input이 증가하면서 CPU 작업량이 증가하는 속도가 서로 다른 것을 알 수 있다. N! 이 가장 빠르게 증가하고 상수(1)는 input 에 상관없이 항상 같은 처리량을 가진다.

Group 14 (1).png

메모리, 공간복잡도는 (memory size) 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양이다. 근사값(approximation)은 큰 데이터에 대한 값을 원하는 오차범위 내로 구하는 것이다. Probability Data Structure의 알고리즘은 정확도가 낮아지는 대신 시간복잡도와 메모리를 줄일 수 있다.

# Probability Data Structure 가 사용되는 분야

아주 큰 값에 대해서

Cardinality(distict)한 값을 찾을 때
Membership Query: 가입된 member인지 확인할 때
Frequency 빈도: 특정 값이 얼마나 자주 나오는 지 확인할 때

# Probability Data Structure 알고리즘

(1) Bloom Filter

possibily in set(아마도 있다) + definitly not in set (확실히 없다) 두 경우를 통해 이전에 본 값인지 아닌지 추정해볼 수 있다.