데이터 스트리밍 알고리즘

오늘 YouTube에서 특정 영상을 시청한 고유 사용자 수를 구해야 한다고 상상해보자.
사용자 ID를 하나씩 집합에 넣고 마지막에 크기를 세면 되지만, 10억 명 기준으로 ID 하나에 8바이트면 8GB다. 영상이 수백만 개라면? 정확한 값을 위해 수 TB의 메모리를 쓸 수는 없다.

그렇다면 "정확하지 않아도 괜찮다"는 조건을 허용하면 어떻게 될까?
이것이 스트리밍 알고리즘의 출발점이다.

---

대규모 데이터의 세 가지 문제

큰 데이터를 다룰 때 부딪히는 장벽은 세 가지다.

문제	접근
데이터 전체를 읽을 시간도 없다	Sub-linear time algorithm
데이터를 전부 저장할 메모리가 없다	Streaming algorithm
프로세서 하나로는 처리가 안 된다	Map-Reduce

이 글은 두 번째 문제, 즉 메모리 제약 하에서 단일 패스로 대답을 구하는 스트리밍 알고리즘을 다룬다.

---

스트리밍 모델

정의

스트리밍 모델의 전제는 다음과 같다.

• 데이터셋이 메인 메모리에 다 들어오지 않는다
• 데이터는 순서대로만(sequential) 한 번 (one pass) 또는 몇 번 읽을 수 있다
• 메모리는 입력 크기에 대해 sublinear하게 써야 한다
• 결과는 근사(approximate)로 허용한다

성능 파라미터

스트리밍 알고리즘을 평가할 때 보는 지표다.

1. 메모리 사용량 — 핵심 제약
2. 패스 횟수 — 몇 번 데이터를 읽는가
3. 근사 인자(approximation factor) — 정답에 얼마나 가까운가
4. 쿼리/업데이트 시간 (상황에 따라)

트레이드오프

정확성을 포기하는 대신 두 가지 여유를 가진다.

• Approximation — (1+ε) 인자 내 근사값 허용
• Randomization — 확률 (1−δ)로 정답 보장

이 두 파라미터(ε, δ)를 조절하면 메모리와 정확도 사이의 균형을 맞출 수 있다.

---

확률 분석 도구: 집중 부등식

랜덤 알고리즘을 분석하려면 확률 변수가 기댓값 근처에 얼마나 집중되는지 알아야 한다.
세 가지 부등식을 알면 대부분의 스트리밍 알고리즘 분석을 따라갈 수 있다.

Markov 부등식

비음수 확률 변수 𝑋에 대해, 𝐏(𝑋 ≥ 𝑎) ≤ 𝐄[𝑋] / 𝑎

"도시 평균 연봉이 5천만 원이면, 1억 원 이상 버는 사람은 절반을 넘을 수 없다."
가장 약하지만, 기댓값만 알면 쓸 수 있다.

Chebyshev 부등식

𝐏(|𝑋 − μ| ≥ 𝑡) ≤ Var(𝑋) / 𝑡²

분산 정보를 추가해 더 강한 경계를 얻는다. 추정량의 분산을 구한 후에 이 부등식으로 "대부분의 경우 기댓값 근처에 있다"는 것을 보인다.

Chernoff / Hoeffding 경계

독립 확률 변수들의 합 𝑆에 대해, 𝐏(|𝑆 − 𝐄[𝑆]| ≥ 𝑡) ≤ 2·exp(−2𝑡²/𝑛)

독립성이 있으면 오류 확률이 지수적으로 감소한다. Chebyshev는 1/𝑘² 감소지만, Chernoff는 exp(−Ω(𝑘²)) 감소다.
결과적으로, 알고리즘을 𝑂(log 1/δ)번만 반복해도 실패 확률을 δ 이하로 줄일 수 있다.

부등식	요구 조건	경계
Markov	비음수, 유한 기댓값	1/𝑎
Chebyshev	유한 분산, 쌍별 독립	1/𝑘²
Chernoff	유계, 완전 독립	exp(−Ω(𝑘²))

실전 전략: Chebyshev로 추정량 하나의 분산을 잡고, Chernoff로 median-of-means 반복 전략의 실패 확률을 지수적으로 줄인다.

---

예제: Distinct Element Problem

문제 정의

크기 𝑚의 전체 집합에서 𝑛개의 원소가 스트림으로 들어올 때, 고유한 원소의 수 DE를 구하라.

실사용 예: 특정 IP를 목표로 한 고유 출발지 IP 수 → DDoS 조기 탐지.

단순한 해법과 한계

방법 1: 𝑚개 원소 각각의 등장 여부를 비트로 기록 → 공간 𝑚 bits
방법 2: 스트림의 원소를 전부 저장 → 공간 𝑛 log 𝑚 bits

최선은 min(𝑚, 𝑛 log 𝑚). 𝑚 = 10⁹ (전체 IP 수)라면 128MB, 실시간 라우터에서는 감당 불가다.

조건 완화: 근사 + 랜덤

정확한 DE 대신:

• Approximate: 정답의 (1+ε) 이내
• Randomized: 확률 (1−δ)로 보장

이 두 조건을 받아들이면 훨씬 작은 메모리로 해결 가능하다.

핵심 아이디어: 1/𝐷 샘플링

직관: DE가 𝐷라면, 각 원소를 확률 1/𝐷로 샘플링했을 때 샘플에 남는 고유 원소 수의 기댓값은 1이다.
샘플이 비어있으면 DE ≪ 𝐷, 샘플이 가득 차 있으면 DE ≫ 𝐷.

이를 결정 문제로 단순화한다:

• YES case: DE ≥ 𝐷(1 + ε)
• NO case: DE < 𝐷(1 − ε)

구체적 알고리즘:

1. 해시 함수 ℎ: 원소 → [0, 1]로 각 원소에 랜덤값 부여
2. 원소 𝑥를 ℎ(𝑥) ≤ 1/𝐷이면 집합 𝑆에 추가
3. 패스가 끝나면 |𝑆| ≥ 1이면 YES, |𝑆| = 0이면 NO

전체 알고리즘: 이진 탐색으로 DE 추정

𝐷를 모르니, 임계값을 로그 단계로 나눠서 결정 문제를 반복한다.

D_i = (1+ε)^i    (i = 0, 1, 2, ...)

각 D_i에 대해 YES/NO 결정 실행
YES → NO로 바뀌는 첫 D_i = DE의 근사값

총 임계값 개수는 𝑂(ε⁻¹ log 𝑛)개이고, 각 임계값마다 𝑂(ε⁻²)의 공간이 필요하다.
전체 공간: 𝑂(ε⁻² log 𝑛) — 입력 크기에 대해 sublinear.

---

결론: Flajolet-Martin에서 HyperLogLog까지

위 아이디어를 해시 함수의 비트 패턴으로 구현한 것이 **Flajolet-Martin 알고리즘(1984)**이다.

• 해시값의 trailing zero (뒤에서 연속된 0 비트) 개수 𝑅(𝑥)를 추적
• ℎ(𝑥) 뒤에 𝑘개의 0이 나올 확률은 1/2^𝑘 — 자연스러운 1/𝐷 샘플링
• 최대값 𝑅_max 를 기록하면 DE ≈ 2^𝑅_max / 0.77351

이를 발전시킨 **HyperLogLog(2007)**는:

• 2^14 = 16,384개의 레지스터로 데이터를 분산
• 12KB 메모리로 수십억 개 원소를 0.81% 오차로 추정
• Redis (PFADD/PFCOUNT), Amazon Redshift, Google BigQuery의 APPROX_COUNT_DISTINCT에서 실사용 중

처음의 질문으로 돌아가면: YouTube의 영상 고유 시청자 수를 세기 위해 HyperLogLog를 쓰면 수십억 명의 데이터를 12KB 하나로 처리할 수 있다. 8GB에서 12KB — 이것이 "정확하지 않아도 괜찮다"는 조건이 가져다주는 결과다.