The Power of Data Sketches: A Comprehensive Guide

Author: luminousmen | Source: luminousmen.com | Published: 2026-03-30

한 줄 요약

확률적 데이터 구조(Data Sketches)의 핵심 원리, 주요 패밀리(카디널리티/분위수/빈도/샘플링), 트레이드오프를 체계적으로 정리한 종합 가이드.

핵심 원리: 모든 것을 해시하고, 작은 부분집합을 유지하며, 필요 시 추정 — 핵심 속성은 병합 가능성(파티션 간 union/intersect/difference)
카디널리티 스케치: Theta(집합 연산 가능), HyperLogLog(더 작지만 intersect 불가), CPC(최고 정확도/바이트), Tuple(페이로드 포함)
분위수 스케치(KLL, REQ), 빈도 아이템(heavy hitters), 샘플링(병합 가능 reservoir sampling) 등 다양한 패밀리 소개
트레이드오프: 이해관계자 저항, 중첩 집합 연산 시 오차 누적, 스케치 생성 시점에 그래뉼래리티 고정(되돌릴 수 없음), 저장소 폭증 가능성
금융/컴플라이언스 용도에는 부적합하며, Spark(approx_count_distinct), BigQuery, Druid, Pinot에 이미 내장