스트리밍 알고리즘 (Streaming Algorithm)

스트리밍 알고리즘 (Streaming Algorithm)

데이터를 한 번만 순차적으로 읽으면서(단일 패스) 제한된 메모리(서브리니어 공간)로 근사적 통계나 패턴을 계산하는 알고리즘

특징: 단일 패스(One-pass), 서브리니어 메모리(O(log n) 또는 O(√n)), 근사 결과(ε-δ 보장), 대규모 데이터 스트림 처리

대표 알고리즘

• •Reservoir Sampling: 스트림에서 균일 랜덤 k개 샘플 추출, O(k) 메모리
• •Misra-Gries: 빈도 상위(Heavy Hitter) 원소 탐지, 카운터 기반
• •Count-Min Sketch: 해시 기반 빈도 추정, 과대추정만 발생
• •HyperLogLog: 고유 원소 수(Cardinality) 추정, O(log log n) 메모리

적용사례: 네트워크 트래픽 분석, 실시간 로그 집계, 검색엔진 쿼리 통계, IoT 센서 데이터

비교: 스트리밍(단일 패스/제한 메모리/근사) vs 배치(다중 패스/전체 메모리/정확)

연관: 빅데이터, 근사 알고리즘, 확률적 자료구조, 해시, 실시간 처리