Probabilistic Data Structure

Probabilistic Data Structure

Objective

• 확률적 데이터 구조를 이용한 근삿값을 연산함으로써, 메모리 사용량 낮추고, 실시간 데이터 처리하되, 약간의 오차를 허용한 결과값을 얻는 방식.
• (random 함수가 아니라) 주로 hash 함수를 이용하여, 데이터 유일성 판단에 대해 확률적으로 접근함
• 예를 들어, 
• Memebership Query: 주어진 element가 특정 set의 member 여부에 대한 판단.
• Cardinality: 주어진 set 내의 유일한 element 개수를 연산.
• (Top-K/Range) Frequency: 중복을 포함하는 set에서 특정 element가 몇개나 포함되어 있는 지 판단.
• 연관된 개념: 
• Universal approximation theorem
• artificial neural network의 수학적 이론에 의하면, finite number of neurons을 포함하는 single hidden layer를 가진 feed forward network은 continuous function으로 approximate 될 수 있음을 의미함; 즉, 단순해 보이는 NN이지만 appropriate paramter에 의해 다양한 함수를 표현 가능하다는 의미임.  

(Approximate) Membership Query

• Wiki: 주어진 element가 특정 set의 member인지를 테스트하기 위한 필터. 
• 데이터베이스에 해당 key가 존재하는 지 확인(lookup)하기 위한 proxy로 주로 사용됨.
• 응용 설명
• Bloom Filter
• (Bloom, 1970)에 의해 제안된, AMQ에 관한 space-efficient 확률적 데이터 구조.
• False negative 발생하지 않는 것을 보장하지만, False positive는 발생 가능.
• 예를 들어, 데이터베이스에 존재하지 않는 데이터에 대한 disk lookup을 reduce하거나, 웹브라우저에서 malicious URL을 식별한다거나, 비트코인 wallet synchronization에 이용됨.
• 0으로 채워진 m개의 bit array에 대해, k개의(이 때, k<m) 서로 다른 hash function을 이용하여, element의 hash 값을 uniform random 분포를 통해 array 위치마다 1로 설정; 만약, 주어진 element에 대한 k개의 hash 값을 살펴보았을 때, 
• 1) 필터값이 어느하나라도 0인 경우가 존재한다면, 해당 element가 set에 속하지 않는다고 판단할 수 있음. 
• 2) 필터값이 모두 1인 경우, set에 포함된다고 판단 가능
• simple Bloom Filter는 false negative를 허용하지 않기 때문에, 원소 삭제(element removal)가 기본적으로 불가능함; 집합 내의 원소 개수가 늘어날 수록, false positive 발생 확률도 증가함.
• 관련 개념: 
• Feature hashing (=hashing trick): 기계학습에서, feature를 vector(또는 matrix)로 변환(vectorizing)하는 빠르고 공간 효율적인 방안; Bag of Words(BOW)이나, Term-Document Matrix를 표현함에 있어, hash 함수를 이용한 indices 도출.
• MinHash (=min-wise independent permutations locality sensitive hashing scheme): (Broder, 1997). 중복 웹 페이지 조회 결과를 제거하기 위한 방안. Association Rule Learning 등에 이용됨.
• Skip list: ordered linked list를 이용해서, fast search를 하기 위한 자료 구조.
• Counting (Bloom) Filters
• (Fan, 2000)에 의해 제안됨; Bloom Filter의 delete operation 구현 방안 제공.
• 필터를 재생성하지 않고도 원소의 삭제가 가능하도록, array내 각 bucket의 크기를 1비트에서 n비트로 확장하여, counter로 사용. (즉, Bloom Filter는 array bucket size가 1비트인 Counting Filter로 간주할 수 있음.)
• element가 추가될 때마다, bucket의 값을 1씩 증가시키고, 삭제될 때마다 1씩 감소시킴
• bucket의 overflow를 방지하기 위해서, 충분히 큰 data type 및 최댓값 설정이 필요.
• 그러나 기존 정적 Bloom Filter에 비해, n배 더 많은 메모리 공간을 사용하게 됨; 또한 테이블의 크기가 여전히 고정되어야 하므로, 수용 범위를 넘어선 element가 추가되기 시작하면, false positive 확률이 증가하게 됨. 
• Quotient Filter
• (Bender, 2011)에 의해 제안된, AMQ에 관한 space-efficient 확률적 데이터 구조.
• 주어진 element가 특정 set에 절대로 포함되지 않는 지, 또는 해당 set에 probably 포함될 지에 대해서 질의 수행 가능.
• False negative 발생하지 않으나, False positive는 확률적으로 발생 가능.

Cardinality

• HyperLogLog
• (Flajolet, 2007)에 의해 제안됨.
• 매우 적은 메모리로 집합의 원소 개수(Cardinality)를 추정할 수 있는 방법; 

Frequency

• Count–min sketch
• (G. Cormode, S. Muthukrishnan, 2003) 제안; frequency 추정을 위한 확률적 데이터 구조.
• 정확한 빈도값을 계산하려면, HashMap을 이용해야 하지만(이 때, 원소 개수에 비례하는 메모리 공간 필요), 더 적은 메모리 공간(sublinear space)을 이용하여 근삿값에 의하여 빈도수를 계산함
• 전체 원소 중에 극히 일부만 빈도 값이 큰 분포를 다루기에 적합.
• Counting Filter와 본질적으로 동일한 자료 구조이지만, 다른 방식으로 활용된다고도 해석됨.