Streaming and Sketch Algorithms TODO
Concept
Streaming algorithms scan the data just once (or a few times) sequentially and produce an approximate answer using far less space than the input size. Since getting an exact answer requires memory proportional to the number of distinct elements — a proven lower bound — streaming algorithms instead use sketch data structures that take error and failure-probability parameters and give a probabilistic guarantee. Heavy-hitters detection (finding the most frequent elements) is solved either Misra-Gries style, keeping a fixed number of counters and decrementing them all in batches, or Count-Min Sketch style, adding into a 2D grid of counters via several hash functions and using the minimum as the estimate. Approximate quantiles are answered by structures like t-digest or KLL, which hierarchically compress the samples and answer a requested quantile within an error bound. What all of these share is mergeability — partial sketches computed on different machines can be combined, which is what makes them usable in a distributed setting.
When you need real-time answers — top users, p99 latency — over data like logs, metrics, or order flow that you can't afford to store in full, exact aggregation is the first thing to run out of memory.
Code & Formula
# Day 7: 스트리밍/스케치 알고리즘 — Misra-Gries로 heavy hitter 근사 탐지
# 고정 개수 카운터만 유지하며 스트림을 한 번 훑어 빈도 상위 원소를 근사한다.
import random
from collections import Counter
def misra_gries(stream, k):
counters = {}
for item in stream:
if item in counters:
counters[item] += 1
elif len(counters) < k - 1:
counters[item] = 1
else:
for key in list(counters):
counters[key] -= 1
if counters[key] == 0:
del counters[key]
return counters
random.seed(0)
heavy = ["A", "B", "C"]
stream = []
for _ in range(3000):
if random.random() < 0.6:
stream.append(random.choice(heavy)) # 60%는 소수의 heavy hitter
else:
stream.append(f"noise-{random.randint(0, 500)}")
exact = Counter(stream)
approx = misra_gries(stream, k=10)
print("정확 카운트 상위 5개 :", exact.most_common(5))
print("Misra-Gries 근사 결과(카운터 <=9개) :", approx)
print("실제 heavy hitter(A,B,C)가 근사 결과에 모두 포함:", all(h in approx for h in heavy))
docs/code/algorithms/algorithms-7.py
Exercise
Implement a Count-Min Sketch, run it over a real log stream, and tabulate how the overestimation error shrinks as you vary the width, compared against the exact count.
Practical Connection
This applies directly to running continuous aggregation for a node operator — top callers per RPC method, top gas-consuming contracts — or to cheaply monitoring the fill-latency quantiles of Verex's order flow.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.