카운트-민 스케치 크기 계산기

폭 w = ⌈e/ε⌉, 깊이 d = ⌈ln(1/δ)⌉입니다. ε는 허용 오차계수, δ는 그 오차를 못 지킬 확률입니다. ε 0.1%·δ 1%면 폭 2,719 × 깊이 5 = 13,595칸이고, 카운터를 4바이트로 두면 53KB 남짓입니다. Cormode–Muthukrishnan(2005)의 원 논문 분석에서 나온 식입니다.

추정값 ≤ 진짜 빈도 + ε·N이며, N은 스트림 전체 개수입니다. 오차 한계가 그 항목의 빈도가 아니라 «전체»에 비례한다는 것이 핵심입니다. N이 1억이고 ε이 0.1%면 어떤 항목이든 최대 10만회까지 부풀 수 있어, 100만회 나온 항목에는 10% 오차지만 500회 나온 항목에는 200배 오차가 됩니다.

사실상 셀 수 없습니다. 오차 한계 ε·N이 그 항목의 빈도보다 크거나 비슷하면 추정값이 실제의 몇 배로 나오기 때문입니다. 그래서 카운트-민 스케치는 자주 나오는 항목(헤비 히터)을 찾는 데만 씁니다. 상대오차를 10% 안으로 두려면 빈도가 오차 한계의 열 배는 넘어야 합니다.

없습니다. 한 칸을 여러 항목이 나눠 쓰므로 남의 몫이 섞여 들어오기만 하고 빠져나가지는 않아, 모든 행의 값이 진짜 빈도 이상입니다. 그중 가장 작은 값을 답으로 삼기 때문에 과대평가만 하고 과소평가는 하지 않습니다. 추정값이 0이면 그 항목은 확실히 한 번도 나오지 않았습니다.

블룸 필터는 있는지 없는지만 답하고, 카운트-민 스케치는 몇 번 나왔는지를 답합니다. 대신 빈도에는 오차가 붙습니다. 두 자료구조 모두 한쪽으로만 틀린다는 성질을 공유합니다 — 블룸 필터는 없는 것을 있다고만 하고, 카운트-민 스케치는 실제보다 크게만 답합니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.