search

Mining Data Streams

hashtag
Stream Processing Model

  • Archival Storage(disk)

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

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

  • Limited Working Storage(disk or main memory)

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

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

  • Standing Queries

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

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

  • Ad-Hoc Queries

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

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

hashtag
Data Stream Problems

  • data sampling

  • data filtering

  • distinct elements counting

  • moments(average, standard deviation etc.) estimating

  • frequent elements finding

hashtag
Sampling Solutions

stream: tuple(user, query, time)

hashtag
1. 고정된 비율 샘플링

a. sample queries

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

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

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

    • 총 쿼리 개수 = x+2dx+2d

    • 전체)고유한 쿼리 중 중복되는 쿼리의 비율 = dx+d\frac{d}{x+d}

    • 10%의 쿼리를 저장한다면, 각 유저당 x+2d10\frac{x+2d}{10}개의 쿼리가 저장됨

    • 중복되는 쿼리의 확률 =110×110=1100→d100\frac{1}{10}\times\frac{1}{10}=\frac{1}{100}\rightarrow \frac{d}{100}

    • 샘플에 있는 고유한 쿼리 개수 = x+2d10−d100=10x+19d100\frac{x+2d}{10}-\frac{d}{100}=\frac{10x+19d}{100}

    • 샘플)고유한 쿼리 중 중복되는 쿼리의 비율 = d10010x+19d100=d10x+19d\frac{\frac{d}{100}}{\frac{10x+19d}{100}}=\frac{d}{10x+19d}

    • 샘플에 저장된 고유한 쿼리 중 중복된 쿼리의 비율은 전체 쿼리의 중복 비율과 일치하지 않음(dx+d≠d10x+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개인 경우

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

hashtag
2. 고정된 크기 샘플링

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

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

Reservoir Sampling

  1. n≤∣S∣n≤∣S∣동안에는 데이터 스트림의 처음 ∣S∣∣S∣개의 항목을 순서대로 샘플 S에 추가

  2. 데이터 스트림의 (n+1)번째 쿼리가 들어오면, 다음 단계를 수행

    1. 확률 ∣S∣n+1\frac{∣S∣}{n+1}로 동전을 던져 앞면이 나오면, S에 해당 쿼리를 추가

    2. 쿼리를 추가하기 위해, 기존 샘플 S에 있는 항목 중 하나를 무작위로 제거

  • 이전 시간에 포함되었던 쿼리가 계속 샘플에 남아 있을 확률 = nn+1\frac{n}{n+1}

  • n+1번째 쿼리가 샘플에 포함될 확률 = ∣S∣n+1=∣s∣n×nn+1\frac{∣S∣}{n+1}=\frac{|s|}{n}\times\frac{n}{n+1}

hashtag
Filtering Solutions

hashtag
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(−mn)1-e^{(\frac{-m}{n})}

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

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

  1. Bloom Filter

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

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

  2. k개의 독립적인 haash function 정의 -> h1,h2,...,hkh_1, h_2, ... ,h_k

  3. 필터 F에 포함된 각 키 s에 대해 모든 해시 함수 계산 후 인덱스 설정 -> B[h1(s)]=B[h2(s)]=...=B[hi(s)]=1B[h_1(s)]=B[h_2(s)]=...=B[h_i(s)]=1

  • 데이터 스트림에서 키 x가 도착하면, 해시(hi(x)h_i(x))를 계산해 값 확인 -> B[h1(x)]∧B[h2(x)]∧...∧B[hi(x)]==1B[h_1(x)]\wedge B[h_2(x)]\wedge ...\wedge B[h_i(x)]==1 인 경우 x는 F에 포함된 것으로 간주

  • false positive 확률 = (1−e−kmn)k(1-e^{\frac{-km}{n}})^k

    • k: 해시 함수의 개수

    • m: 저장된 키의 개수

    • n: 비트 배열 크기

  • 최적의 k 값 = nmln2\frac{n}{m}ln2

  • m: 1 billion, n: 8 billion 인 경우 Hash Table 이용시 false positive=1−e(−18)=0.11751-e^{(\frac{-1}{8})}=0.1175, Bloom Filter 이용시 k=81ln2≈6\frac{8}{1}ln2\approx 6, false positive=(1−e−6×18)6=0.0216(1-e^{\frac{-6\times1}{8}})^6=0.0216으로 낮춤

PreviousRecommender SystemNextMapReduce and Spark

Last updated