> For the complete documentation index, see [llms.txt](https://riverallzero.gitbook.io/summary/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://riverallzero.gitbook.io/summary/data-mining/mining-data-streams.md). # 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: 비트 배열 크기 (타겟 개수) 2. 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$$으로 낮춤