D033

Sampling Stream

검색엔진에서 스트림 데이터 중 1/10 만 저장할 수 있는 상황을 가정해 봅시다.
스트림은 (사용자,쿼리,시간) 으로 구성되어 있고,
지난달 동안 반복된 쿼리의 비율을 찾고자 합니다.
지난달 한 사용자는 s개의 쿼리들을 한번 검색했고, d개의 쿼리들을 두번 검색했습니다. (그외에는 없다고 가정합니다.)

전체 스트림에서 1/10 의 무작위 샘플을 구하게 되면,
한번 나온 쿼리는 s/10 개가 나올 것으로 기대할 수 있고,
두번 나온 쿼리는 d/100 개가 나올 것으로 기대가 됩니다.
확률이 d/100 인 이유는, 두번 나온 쿼리 하나가 동시에 1/10 의 샘플에 나올 확률은 $1/10\times1/10 = 1/100$ 이기 때문입니다.
그리고 두번 나온 쿼리가, 두개 중 한개만 샘플에 들어가는 확률은 $2 \times 1/10 \times 9/10 = 18/100$ 이고, 샘플에서 18d/100 의 기대값을 갖습니다.

2번 검색된 쿼리의 비율은 실제로 d/(s+d) 가 나와야합니다.
그러나 샘플에서 얻은 비율은 d/(10s+19d) 가 됩니다. (d/100, s/10 , d/100+18d/100)

이렇게 샘플이 잘못된 상황이 발생한 원인은
샘플링을 할 때, 스트림 요소의 value 를 고려하지 않았기 때문입니다.

이 문제에서 찾고자 하는 것은
같은 값이 나온 쿼리의 비율입니다.
쿼리의 값을 기반으로 샘플을 수집해야합니다.

이 상황에서 적절한 샘플을 찾기 위해서는 hash 를 사용합니다.
스트림의 쿼리에 대해 hash 를 수행하고,
그 결과는 0 부터 9 까지 숫자의 버킷에 들어가게 됩니다.
전체 중 1/10 개를 사용하므로
10개의 버킷 중 아무것이나 하나 선택하여 샘플로 사용하면 됩니다.

만약 스트림이 많아서 1/10의 크기가 다 수용되지 않는다면
hash 의 버킷을 더 많이 만들어서 사용하면 됩니다.

100개의 버킷을 만들어서
0부터 9번까지의 버킷에 해당하는 샘플을 사용하고
샘플이 커지는 경우 9번 버킷, 8번 버킷 등
크기에 맞춰 사용하는 버킷을 줄여가면 됩니다.

다른 예시를 들어보겠습니다.

한 부서에서의 월급의 평균적인 범위를 알고자합니다.
데이터는 (고용자, 부서, 월급) 으로 구성된 튜플의 스트림입니다.

여기에서 key 는 ‘부서’ 이고 value 는 (고용자, 월급)
‘부서’ 의 값을 해시하고, 특정 버킷을 선택하여
그 샘플을 가지고 계산을 수행합니다.
이 샘플에는 몇 부서가 선택되고, 그 부서 월급의 범위를 파악할 수 있습니다.

이렇게 문제의 특성에 맞춰 샘플링을 수행할 수 있습니다.