[CS246] Sampling from a Data Stream

Fixed-proportion, Fixed-size, Reservoir Sampling

Introduction

data stream은 전체 데이터를 저장할 수 없기 때문에, 샘플링을 이용한다.

크게 2가지 방법이 있는데, fixed proportion 방법과 random sample of fixed size이다.

 

Sampling a Fixed Proportion

data stream의 일정 비율(예를 들어 10% 등)만큼 샘플링하는 것이다. stream이 커질수록 sample 역시 커진다.

 

Problem with Naive Approach

stream data가 (user, query, time)이라는 tuple의 형태로 들어온다고 할 때, unique query의 비율을 추정해보자. 이때 당연히 중복되는 query역시 고려해야한다.

문제를 간단히 하기 위해, 각 user마다 1번만 입력한 query는 $x$개, 2번만 입력한 query는 $d$개라 하자. 그러면 전체 query의 개수는 $x+2d$이므로 unique query 비율은 $d/(x+d)$이다. (이것이 실제 값)

 

그렇다면 실제 10%만큼 샘플링했을때 unique query의 비율은 어떻게 얻을까? sampling된 query는 $(x+2d)/10$이고 중복되는 query는 $(1/10)(1/10)(d)=d/100$이므로 unique query의 비율은 $(x+2d)/10 - (d/100)=(10x+19d)/100$이다. 따라서 sample-based answer는 $\cfrac{d/100}{(10x+19d)/100}=\cfrac{d}{10x+19d}$ 이다. true 값이 $\cfrac{d}{x+d}$인 것에 비하면 상당히 underestimated한 값을 추정하고 있어 적절한 방법이 아니다.

 

Solution: Sample users, not queries

hash function을 이용하여 user를 sampling하여 해결한다. 해싱되는 값은 보통 tuple의 key를 사용한다. application에 따라 key를 고를 수 있다.

만약 $a/b$의 비율을 sampling하고 싶다면? $b$개의 bucket을 만들고, 앞에서부터 $a$개의 bucket($0, 1, \dots, a-1$)에 들어오는 tuple만 smapling하면 된다. 예를 들어 30%만큼 sampling하고 싶다면, $0, 1, 2$번째 bucket에 들어오는 tuple을 sample로 사용한다.

 

Reservoir Sampling: Maintaining a fixed-size sample

random sample의 집합을 $S$라 하고 원소(tuple)의 개수를 $s=|S|$라 하자. main memory는 한정되어있고, data stream의 길이는 알 수 없기 때문에 fixed-size sample set $S$를 구하는 방법을 알아보자. 시간 $n$까지 $n$개의 item을 보았다고 하자. 그러면 각 ite이 $S$에 있을 확률은 모두 $s/n$이다.

 

예를 들어, stream: [a, x, c, y, z, k, c, d, e, g, ...]이고 $s=2$라 하자.

$n=5$이고 가능한 $S$중에는 $S = \{ a, c \}$가 있다. 이때 각 item의 확률은 2/5이다.

$n=7$이면, 이전에 stream인 [a, x, c, y, z]의 확률은 $2/7$로 줄어들어야 한다. 그리고 추가로 들어온 [k, c]의 확률도 $2/7$이 되어야한다.

 

Solution: Reservoir Sampling

처음 $s$개의 원소들을 $S$에 모두 저장한다.
$n-1$개의 원소는 이미 봤고, 이제 $n$번째 원소가 stream에서 도착했다고 하자. ($n>s$)
$s/n$의 확률로, $n$번째 원소를 고른다. (1-$s/n$)의 확률로 버린다.
만약 $n$번째 원소를 골랐으면, $S$ 중에서 임의로(uniformly random) 하나의 원소를 고르고 교체한다. 

 

Claim: $n$개의 데이터를 본 수에, 지금까지 본 원소가 $S$에 있을 확률은 $s/n$이다. ($s=|S|$)

Proof by induction

• Base case: $n=s$이면, $S$는 claim을 만족한다. ($s/s=1$)
• Inductive hypothesis: $n$개의 원소를 본 수에는 위의 claim을 만족한다.
• Inductive step:
  • 새로운 $n+1$번째 원소가 도착하면, $S$의 확률은 $s/(n+1)$이 된다.
  • $S$의 원소가 $S$에 그대로 남아있을 확률은 $\left(1 - \cfrac{s}{n+1} \right)+ \left( \cfrac{s}{n+1} \right) \left( \cfrac{s-1}{s} \right)=\cfrac{n}{n+1}$ 이 된다.
  • time이 $n$일때 tuple이 $S$에 있을 확률은 $s/n$이므로, tuple이 $n+1$에서도 $S$에 남아있을 확률은 $\cfrac{s}{n} \cfrac{n}{n+1} =\cfrac{s}{n+1}$이다.

Proof by induction (Stanford CS246)