Q001. 구글 계정을 만들 때, 이미 있는 아이디인지 어떻게 빠르게 알 수 있을까?

노션의 내용을 옮겨오면서 내용이 많이 깨져있습니다.

PDF 파일로 보면 더 잘 읽힙니다.

 

Probability_Data_Structure.pdf

1.57MB

---

관련 내용은 모두의 연구소 effective python을 진행하면서 정리했던 내용입니다.

 

 

Q. 구글은 그 엄청나게 많은 유저 아이디 데이터에서 이미 있는 아이디인지 어떻게 그렇게 순식간에 알 수 있는 것일까?
A. Probability Data Structure

 

---

 

# Probability Data Structure의 정의

Acceptably Inaccurate.

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

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

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

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

메모리, 공간복잡도는 (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 (확실히 없다) 두 경우를 통해 이전에 본 값인지 아닌지 추정해볼 수 있다.

아래 그림은 본 적이 없는 값이면 두 개의 hash 함수를 통과한 결과 각각에 1을 입력해서 중복이 발생하지 않게 한다. x의 hash 결과는 2번 11번을 가르키는데 둘 다 이미 1이 입력되어 있다. 그런데 이 1은 x 이전에 입력된 값 때문에 우연히 입력되있는 것일 수 있다. 또는 정말 x 값이 이전에 들어와서 1이 입력된 것일 수도 있다. 즉, 봤을 수도 안 봤을 수도 있다(possibily in set)이다. 반면 w는 0이 있기 때문에 확실히 w 값이 들어온 적이 없다는 것을 알 수 있다. x, y, z가 이전에 본 적 없는 값인데 우연히 모두 1이 표시된 경우라면 오류이다. 그러나 이런 경우는 input이 커지면서 작아진다.

 

 

[ 예시 ]

아래는 블룸필터를 적용시켜 key-value 알고리즘의 속도와 안정성을 향상시킨 그림이다.

 

 

블룸필터를 사용하는 경우:

시간복잡도:

O(k)*O(k) : filter 결과를 체크하고 storage에 대한 값반환

설명:

key1: hash 결과 0이 나와서 filter가 No라는 응답을 보낸다.

key2: hash 가 모두 1이 나와 본 적 있다는 Yes 응답을 보낸다. storage에서 key2에 대한 값을 받는다.

key3: hash가 모두 1이 나와 본 적 있다는 Yes 응답을 보낸다. storage에 값이 없다(본적없는 false positive)

false positive로 불필요하게 disk에 접근하는 경우가 생기지만(key3) 없다고 판단되는 경우 disk에 접근하지 않으므로 안정성도 높아질 수 있다.

블룸필터를 사용하지 않는 경우:

시간복잡도:

O(N)*O(1): 테이블을 전체 탐색하고 storage에 대한 값반환

설명:

key 1,2,3 각각에 대해 hash결과와 일치하는 값을 찾기 위해 hash 테이블을 처음부터 끝까지 탐색한다. → 있다면 storage에서 값을 가져온다.

 

 

[ 최적의 hash 함수 갯수 ]

최적의 hash 함수 갯수를 알기 위해서는 다음과 같은 생각의 흐름에 따라 input 크기, hash table 크기, 오차범위 세 가지를 결정해야한다.

1. m개의 hash table에서 1이 있을 확률(오류확률): 1/m , 정답확률 1- 1/m

1. 이걸 k개의 함수에 적용시킨다면 독립시행이므로 각각을 곱할 수 있다

1. 테이블이 충분히 크다면 자연상수 e로 치환할 수 있다

1. n개의 input에 대해 0이 나올 확률은 다음과 같아진다

1. 반대로 1이 나올 확률은 다음과 같아진다.

1. k개 hash function에 대한 false positive 확률은 다음과 같아진다.

1. 이를 k에 대한 식으로 바꾸면 다음과 같은 식이 나온다.(ln2는 약 0.7)

(출처: https://en.wikipedia.org/wiki/Bloom_filter)

 

아래 그래프는 p: false positive가 발생하는 확률

n: 인풋의 갯수

m: 필터사이즈(hash 결과 나올 수 있는 수의 범위)

를 나타낸 그래프이다.

예를 들어 n=100일 때 m=2^12, p(오차범위)는 1e-10로 매우 작다. 생각해보면 100 개의 글자를 테스트하는데 사용할 수 있는 hash table이 4096bit(0.512KB)이므로 충분할 것 같다. 이 세 가지 조건에서 최적의 hash 함수 갯수는 약 ln(2^(m/n)) =약 0.7^(m/n)이므로 40개 정도 필요하다는 것을 알 수 있다.

 

 

https://en.wikipedia.org/wiki/Bloom_filter

오차검증: 카이제곱과 avanlanch 함수를 이용

 

 

참고

[BaSE Seminar] 20-16차 세미나: Bloom Filter (장민오) : https://www.youtube.com/watch?v=aM6MI7WVgSc

(2) Count-Min Sketch

어떤 요소가 set에 들어있는 지 확인하는 filter (bloom 필터랑 유사)

계속 추가만 할 수 있는 Bloom Filter에 비해 Delete 할 수 있다.

Cardinality한 값에 대해 빈도(frequency)를 알 수 있다. 쉬운 예로 지역 별로 고유한 번호가 정해져있을 때, 그 번호가 몇번 방문했는지 확인할 수 있다.

 

 

https://www.researchgate.net/figure/Frequency-Estimation-Count-Min-Sketch_fig4_336946001

참고:

[Naver D2: 확률적 자료구조를 이용한 추정 - 빈도(Frequency) 추정을 위한 Count-Min Sketch] https://d2.naver.com/helloworld/799782

(3) Count-Quotient Filter

요소가 set에 있는 지 확인하는 알고리즘

Kmer를 hash화 한다 0101110

이 hash value의 일정 부분(5자리)는 버킷의 locatiuon을 나타내고 나머지는 값을 나타낸다

똑같은 Kmer가 들어오면 11버킷에 2 값이 있을 것이고 다른 값이 들어오면 location이 11이라도 다른 hash value remainder이기 때문에 본 적 없는 값이라는 것을 알 수 있다.

 

 

https://shokrof.github.io/cqf_assessment/

Counting Quotient Filters https://www.youtube.com/watch?v=oMFHkuVoF70

(4) LogLog HyperLogLog

시간복잡도: O(1), 공간복잡도: O(log(log(n))

loglog

어떤 값을 hashing해 연속한 0이 몇 개 나오는 지 확인해 그 만큼의 데이터가 있다고 추정. 예를 들어 연속한 0이 4개 나오는 경우 16개의 distict한 데이터가 있을 것이라고 생각할 수있다.

 

 

https://towardsdatascience.com/big-data-with-sketchy-structures-part-2-hyperloglog-and-bloom-filters-73b1c4a2e6ad?gi=807410264098

hyperloglog

• loglog 위의 예시에서 가장 첫값으로 0000(eric)이 나온다고 하면 1개인데 16개라고 하는 오차가 생길 수 있다. 아래의 예시를 설명하면 앞의 3개를 잘라서 bucket 번호로 쓰고 그 뒤부터 연속 0의 갯수를 사용해서 이태까지 나온 연속 0중 가장 큰 수를 업데이트하고 이 값을 조화평균한다.
• hashing을 더 잘하기 위해 hash함수로 murmur3을 이용한다
• REDIS에서 unique한 data를 찾고싶을 때 사용하는 알고리즘
• arithmatic mean: outlier를 제외할 수 없음 harmonic mean: outpier를 제외할 수 있음(심판 시스템)https://blog.devartis.com/hyperloglogs-a-probabilistic-way-of-obtaining-a-sets-cardinality-3b5e6a982a12
•  

 

(5) Cuckoo Filter

hash 충돌이 날 때 앞의 값을 밀어내는 알고리즘 hash한 결과를 테이블1에 먼저 넣고 hash 충돌이 일어나면 기존에 있던 값을 다른 옮긴다. 모든 값이 insert 될 때까지 이를 반복하는데 loop이 일어나는 경우 rehash를 한다.

search할 경우 찾는 val을 첫번째 table부터 시작해서 원하는 값이 나올 때까지 알고리즘을 따라간다. 이 때의 시간복잡도는 O(1) rehashing의 시간복잡도는 O(1)(→이해가 잘 안됨)

어떤 요소가 set에 들어있는 지 확인하는 filter로 아주 작은 메모리를 기반으로 hash할 때 사용.

기존에 있는 요소를 삭제할 수 있다

현상님 자료

참고: 뻐꾸기 해싱 : 시각화 + 설명 https://www.youtube.com/watch?v=OBuGqu2d4v4

 

(6) MinHash

두 집합이 얼마나 유사한지 빠르게 추정하는 기술.

---

개념1: LSH (locality Sensitive Hashing): 값이 유사하면 유사한 해싱을 리턴하는 해싱 ( 기존에는 비슷한 값을 가지더라도 랜덤한 hash값을 리턴)

 

 

개념2: 자카드 유사도: 두 집단이 얼마나 유사한가? 교집합/합집합. 수치가 높을 수록 교집합의 수가 많다는 것이므로 두 집단이 비슷하다는 것을 의미한다.

 

 

https://en.wikipedia.org/wiki/Jaccard_index

---

1. Document:

문장을 n개 단위로 묶어 n-gram 처리한다. 처리한 단어가 document 각각에서 나오는 지 체크한 matrix를 만든다

1. Minhashing:

• hash 함수를 통해 row에 고유 번호를 새로 만든다. 아래 예시에서는 h1 h2를 통해 row의 0,1,2,3,4,5를 각각 1,2,3,4,5,6 과 5,1,4,0,3,6으로 바꾼다.
• 바뀐 순서 중 가장 작은 것부터 시작해 document 에 1이 나오는 지 확인한다. 0이라면 다음 큰 수를 찾고 1이라면 그 때의 hash 값을 signiture value로 입력한다. 예를 들어 h1은 1이 가장 작은 값이므로 1(row로는 0)부터 시작해 A,B,C,D 에서 1이 나오면 hash value인 1을 넣고 아니라면 그 다음 큰 수인 2로 넘어간다.현상님 자료
• 

1. locality sensitive hashing:

A 와 B를 비교하면 서로 다르지만 A와 C를 비교하면 서로 같다는 것을 알 수 있다. A와 C의 문서는 서로 다른데 2개의 hash 함수인 h1 h2를 통해 보면 같다. hash 함수가 늘어나면 서로 다른 문서를 구분하는 정확도가 높아진다. hash 함수의 갯수가 문서의 갯수만큼 있다면 모든 문서를 정확하게 구분해낼 수 있다. 이 알고리즘의 목표는 최적의 함수로 오차범위 내에서 유사도를 구해내는 것이다. LSH는 A와 C 처럼 비슷한 값은 유사하게 hashing한다.

 

현상님 자료

아래의 그림에서 초록 파랑 빨강 선은 각 document에 대한 hash value 라고 할 수 있다. 여러개의 함수를 통과하면서 같은 minhash를 가진다면 유사한 값이라고(함수들의 교집합에 들어가는 값) 판단한다.

 

 

→ 비슷한 애들끼리 묶어서 minhashing을 하면 성능이 더 올라간다

참고 https://towardsdatascience.com/understanding-locality-sensitive-hashing-49f6d1f6134

Learn in 5 Minutes: Finding Nearest Neighbor using MinHash https://www.youtube.com/watch?v=GRHsg0d5X8Y

(7) SimHash

두 집합이 얼마나 유사한지 빠르게 추정하는 기술

minhash에 비해 빠르지만 정확도가 떨어진다. 메모리 효율이 더 좋다.

embedding 된 단어에 TF-IDF(문서에서 단어의 중요도를 수치화한 값)값을 반영해 문서간 유사도를 계산하는 방법.

 

 

계산방법:

각 단어를 b-bit hash화 하고 0은 -1로 바꾸고 단어의 weight를 계산, 모든 컬럼을 더해서 이 값이 음수면 0 양수면 1을 넣는다. 이 결과 문서 전체에 대해 8자리 이진수 값을 구할 수 있다.

https://www.youtube.com/watch?v=gnraT4N43qo

# Implementation Library: pyprobables

pypropables https://github.com/barrust/pyprobables

# bloomfilter

from probables import (BloomFilter)
blm = BloomFilter(est_elements=1000, false_positive_rate=0.05)
blm.add('google.com')
print(blm.check('facebook.com'))  # should return False
print(blm.check('google.com'))  # should return True

# count-min-sketch

from probables import (CountMinSketch)
cms = CountMinSketch(width=1000, depth=5)
print(cms.add('google.com'))  # should return 1
print(cms.add('facebook.com', 25))  # insert 25 at once; should return 25

# cuckoo filter

from probables import (CuckooFilter)
cko = CuckooFilter(capacity=100, max_swaps=10)
cko.add('google.com')
print(cko.check('facebook.com'))  # should return False
print(cko.check('google.com'))  # should return True

# Defining hashing function using the provided decorators 해쉬함수 지정

import mmh3  # murmur hash 3 implementation (pip install mmh3)
import pyprobables
from pyprobables.hashes import (hash_with_depth_bytes)
from pyprobables import (BloomFilter)

@hash_with_depth_bytes
def my_hash(key):
    return mmh3.hash_bytes(key)

blm = BloomFilter(est_elements=1000, false_positive_rate=0.05, hash_function=my_hash)

blm.add('google.com')
print(blm.check('facebook.com'))  # should return False
print(blm.check('google.com'))  # should return True