Data Streams

Data Stream

 

빅데이터의 상황 속에서, 우리는 사전에 전체 dataset을 아는 경우는 드물고 데이터들은 끊임없이 들어오며 그 데이터들을 저장하고 프로세싱하기 위한 메모리는 한정되어있다. 그래서 데이터를 Stream으로 여기고 관리하는데, Stream은 무한하고 분포가 들쭉날쭉(non-stationary)한 성질을 가지고 있다.

 

 

Data Stream의 특징

 

- infinite & non-stationary

- large volume

- online processing (실시간 처리는 가능하나, Batch processing 불가능!)

- Data is read once and discarded

 

 

The Stream Model

 

 

stream model의 특징

• input element들은 빠른 속도로 들어오며, 각각의 입력 속도는 모두 다르다.
• input element들은 여러 개의 입력 포트를 통해서 입력된다.
• 시스템은 전체 stream data를 저장할 수 없다.

→ 그렇다면 제한된 메모리 상에서 끊임없이 들어오는 stream data를 어떻게 처리할 것인가?

 

 

Problems on Data Streams

 

data stream에 대해 우리가 원하는 query의 타입은 다음과 같다. 

각 method들은 다음 포스팅에서 알아보도록 할 것이다.

 

 

(1) Sampling from a stream : 전체의 stream data를 볼 수 없으므로 샘플링 범위 내에서 estimation

• Fixed proportion sampling
• Fixed size sampling

 

(2) Queries over sliding windows : 지나가는 k개의 element 중에서 type X의 element의 수  

      → DGIM method

 

(3) Filtering a data stream : 필요한 속성 X를 가지고 있는 element만 남기고 필터링

      → Bloom Filter

 

(4) Counting distinct elements : 중복되지 않고 unique한 element는 몇 개 인가?

      → Flajolet-Martin

 

(5) Estimating moments : k개의 element 중 원소의 avg와 std를 estimate

      → AMS method

 

(6) Finding frequent elements : 가장 빈도수가 높은 hot element를 찾는 것

      → Exponentially decaying window

 

 

Sampling from a data Stream

 

우리는 data stream 전체를 저장할 수 없으므로 이를 해결할 수 있는 명백한 접근 방법 중 하나는 sampling이다. 샘플링은 (1) 샘플링의 비율을 고정시키는 방법 과 (2) 샘플의 크기를 고정하는 방법이 있다.

 

(1) Sampling fixed proportion

 

search engine query stream을 받는 example을 생각해보자. 데이터는 (user, query, time)의 3개의 asset으로 구성된 튜플이며  user가 하루에 똑같은 검색을 얼마나 자주 하는가? 에 대한 문제를 해결해야 한다.

 

Naive solution의 경우 들어오는 각 query에 랜덤한 정수 0~9를 생성하고(1/10의 고정된 확률) 0이 나오는 경우에만 메모리에 저장한다.

하지만 이처럼 한 유저의 모든 쿼리를 1/10씩 저장하는 방식은 유저의 중복적인 검색에 대한 쿼리에 잘못된 답을 제공하게 된다.따라서 유저의 쿼리를 샘플링하지 말고, 유저별로 샘플링해야한다. 이때 유저의 이름이나 ID를 균등하게 10개의 bucket으로 해쉬하여 샘플링하면 된다.

 

 

(2) Sampling fixed size

 

n의 시간에 n개의 element가 지나갔을 때, 샘플 s안에 각각의 element가 속할 확률은 s/n이다.

하지만 모든 샘플을 다 저장해둔 후 총 샘플의 개수를 알고 각각의 샘플을 1/(샘플의 총 개수)의 확률로 무작위 추출을 하려면 샘플의 개수만큼 많은 메모리가 필요하다. ( 우리는 stream data의 길이를 사전에 알 수 없고, 메모리는 제한적인 상태 )

 

그래서 하나의 샘플을 저장할 수 있는 메모리로 무작위 추출을 하는 Reservoir Sampling을 사용해야한다.

 

 

• 샘플 S에 k개의 element를 저장한다
• n-1 개의 element가 존재하는 상황에서, n번째 element가 들어온다고 가정한다
• k / n 확률로 n번쨰의 element를 저장하고, 그렇지 않으면 discard한다
• n번째의 element를 선택한 경우 무작위로 균일하게 추출된 샘플 S의 k번째 element 중 하나를 대체한다.  (확률 k/n으로 랜덤하게 뽑아서 버리고 새로운 element를 S에 넣음)