[웹정보] ch06 Association Rules2

Hash-based Filtering: 

문제 상황

길이가 10인 문자열로 이루어진 1billion(10^9)개의 문자열 집합 S가 있음.
F를 스캔하여 S 안에 있는 문자열을 출력하고 싶음.
메인메모리는 1GB -> 10^8byte
S를 메인메모리에 다 올리지 못함

 

Solution

• 8billion 비트로 이루어진 비트 배열을 만들고, 모두 0으로 설정.
• 범위가 [0, 8*10^9)인 해시함수 h를 선택.
• S의 각 문자열을 해싱에 하나의 비트로 매핑하고, 해당 비트를 1로 설정.
• File의 문자열에 해당하는 해시 값이 1인 경우에만 출력

• 문자열 집합 S에는 1billion개의 문자열이 있음.
• bit array는 8billion 길이임.
• 비트 배열의 최대 1/8이 "1"임.
• false positive가 있을 수 있음. -> 통과하면 안되는데 통과한 애들.
• 다른 해시함수를 사용해서 false positive를 8배 더 잡아낼 수 있음.
  • 실제로는 1/(1-e^(-1/8)) ~= 1/8 (아래에서 나옴)
• 나중에는 여러번 해싱을 통해 살아 남은 애들만 가지고 체크!

 

Throwing Darts: 

해시 테이블로 가는 것은 다트 던지기와 같다!

만약 n개의 동등한 확률을 가진 타겟에 k번 다트를 던졌을 때 어떤 타겟이 적어도 하나의 다트를 받을 확률은?

타겟을 bits, 다트를 해시값이라고 해보자.

처음에 그냥 1/8로 구했을 때와 true value값이 얼마 차이 안 남.

 

 

 

Bloom Filters

A-Priori algorithm: 

pair를 

 

Park-Chen-Yu Algorithm

A-Priori algorithm: 

pair를 

 

Multistage Algorithm

A-Priori algorithm: 

pair를 

 

Approcimate Algorithm

A-Priori algorithm: 

pair를 

 

Compacting Results

A-Priori algorithm: 

pair를