Mining Data Streams

Stream Processing Model

• Archival Storage(disk)

  • 백업과 같이 스트림이 아카이브됨

  • 해당 저장소에서 쿼리에 대한 답을 할 수 없음

• Limited Working Storage(disk or main memory)

  • 스트림 일부 혹은 요약본이 저장됨

  • 쿼리에 대한 답으로 사용됨

• Standing Queries

  • 특정 시간 조건에서 영구적으로 실행됨(cron)

  • e.g. 온도가 25도 이상이면 알람

• Ad-Hoc Queries

  • 현재 스트림 상태에 대해 물음

  • e.g. 지난달 페이지를 방문한 유저수

Data Stream Problems

• data sampling

• data filtering

• distinct elements counting

• moments(average, standard deviation etc.) estimating

• frequent elements finding

Sampling Solutions

stream: tuple(user, query, time)

1. 고정된 비율 샘플링

a. sample queries

• 데이터 스트림에서 고정된 비율로 샘플링을 수행하면, 데이터 스트림의 총량이 증가함에 따라 샘플링된 데이터의 양도 비례적으로 증가함

• 각 쿼리에 대해 0에서 9 사이의 정수를 무작위로 할당하고, 그 값이 0인 경우 해당 쿼리를 저장하도록 함(10%)

• e.g. x 쿼리는 1번, d 쿼리는 2번씩 들어오는 경우

  • 총 쿼리 개수 = $x+2d$
  • 전체)고유한 쿼리 중 중복되는 쿼리의 비율 = $\frac{d}{x+d}$
  • 10%의 쿼리를 저장한다면, 각 유저당 $\frac{x+2d}{10}$개의 쿼리가 저장됨
  • 중복되는 쿼리의 확률 =$\frac{1}{10}\times\frac{1}{10}=\frac{1}{100}\rightarrow \frac{d}{100}$
  • 샘플에 있는 고유한 쿼리 개수 = $\frac{x+2d}{10}-\frac{d}{100}=\frac{10x+19d}{100}$
  • 샘플)고유한 쿼리 중 중복되는 쿼리의 비율 = $\frac{\frac{d}{100}}{\frac{10x+19d}{100}}=\frac{d}{10x+19d}$
  • 샘플에 저장된 고유한 쿼리 중 중복된 쿼리의 비율은 전체 쿼리의 중복 비율과 일치하지 않음($\frac{d}{x+d} \neq \frac{d}{10x+19d}$)

b. sample users

• 쿼리 기반 샘플링으로 중복 비율이 일치하지 않는 문제를 해결하기 위해 유저 기반 샘플링을 함

• 전체 유저 중 10%를 샘플링하고, 샘플된 유저의 모든 쿼리를 저장

• 유저 중 10%를 샘플링하면, 저장되는 쿼리의 비율은 10%이므로 비율이 일치하게 됨

• 유저 ID를 해싱하여 10개의 버킷으로 분류한 후, 0번 버킷에 해당하는 유저를 샘플링

• 30%의 비율로 샘플링하려면 10개의 버킷 중 3개를 선택

• e.g. 유저가 n명, 쿼리가 m개인 경우

  • 저장되는 쿼리의 비율은 $\frac{n}{10}\times\frac{m}{n}=\frac{m}{10}$

2. 고정된 크기 샘플링

• |S|: 샘플링 크기 (Reservoir 크기), n: 현재까지 처리된 쿼리 개수 (시간을 의미), S: 샘플 집합

• n번째 쿼리가 샘플 S에 포함될 확률 = $\frac{|S|}{n}$

Reservoir Sampling

1. $n≤∣S∣$동안에는 데이터 스트림의 처음 $∣S∣$개의 항목을 순서대로 샘플 S에 추가
2. 데이터 스트림의 (n+1)번째 쿼리가 들어오면, 다음 단계를 수행

   1. 확률 $\frac{∣S∣}{n+1}$로 동전을 던져 앞면이 나오면, S에 해당 쿼리를 추가
   2. 쿼리를 추가하기 위해, 기존 샘플 S에 있는 항목 중 하나를 무작위로 제거

• 이전 시간에 포함되었던 쿼리가 계속 샘플에 남아 있을 확률 = $\frac{n}{n+1}$
• n+1번째 쿼리가 샘플에 포함될 확률 = $\frac{∣S∣}{n+1}=\frac{|s|}{n}\times\frac{n}{n+1}$

Filtering Solutions

1. Hash Table

• 용

  • F: 필터 키의 집합 (list)

  • B: 크기 n의 비트 배열, 모든 값을 0으로 초기화

  • Hash Function: h(k)는 키 k를 해싱하여 범위 [0,n)의 인덱스를 반환

1. 비트 배열 B를 n비트로 생성하고 모든 값을 0으로 초기화

2. 필터 F에 포함된 각 키 k를 해싱하고, B[h(k)] 값을 1로 설정

3. 데이터 스트림에서 아이템 a가 들어오면 h(a)를 계산하고 B[h(a)]==1이면 a를 반환

• 해싱 충돌로 인해 false positive가 발생

• false positive 확률=$1-e^{(\frac{-m}{n})}$

  • m: 저장된 키의 개수 (다트의 개수)

  • n: 비트 배열 크기 (타겟 개수)

1. Bloom Filter

• Hash Table의 false positive문제 줄이기 위함

1. 비트 배열 B를 n비트로 생성하고 모든 값을 0으로 초기화

2. k개의 독립적인 haash function 정의 -> $h_1, h_2, ... ,h_k$
3. 필터 F에 포함된 각 키 s에 대해 모든 해시 함수 계산 후 인덱스 설정 -> $B[h_1(s)]=B[h_2(s)]=...=B[h_i(s)]=1$

• 데이터 스트림에서 키 x가 도착하면, 해시($h_i(x)$)를 계산해 값 확인 -> $B[h_1(x)]\wedge B[h_2(x)]\wedge ...\wedge B[h_i(x)]==1$ 인 경우 x는 F에 포함된 것으로 간주
• false positive 확률 = $(1-e^{\frac{-km}{n}})^k$

  • k: 해시 함수의 개수

  • m: 저장된 키의 개수

  • n: 비트 배열 크기

• 최적의 k 값 = $\frac{n}{m}ln2$
• m: 1 billion, n: 8 billion 인 경우 Hash Table 이용시 false positive=$1-e^{(\frac{-1}{8})}=0.1175$, Bloom Filter 이용시 k=$\frac{8}{1}ln2\approx 6$, false positive=$(1-e^{\frac{-6\times1}{8}})^6=0.0216$으로 낮춤