Streaming and Sketch Algorithms TODO

Algorithms · Day 7 / 100 · A. Advanced Algorithms & Data Structures (Day 1-19)

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.

Where it lands in Jayverse

• Verex: back the fill-latency p99 on gitboard with a t-digest or KLL sketch, not stored samples. Order flow is exactly the stream this page describes — too much to keep in full, and a mergeable sketch is what makes a live quantile on the dashboard cheap.
• Devnet: run a Count-Min Sketch over RPC method calls to find hot callers before capacity becomes a problem. Top-caller and top-gas-consumer tracking on the devnet node is the same heavy-hitters problem, solved without storing every request.

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/.

한국어

스트리밍/스케치 알고리즘 TODO

Algorithms · Day 7 / 100 · A. 고급 알고리즘·자료구조 (Day 1–19)

heavy hitters, 근사 분위수

개념

스트리밍 알고리즘은 데이터를 한 번(또는 몇 번) 순차적으로만 훑으면서, 입력 크기보다 훨씬 작은 공간으로 근사 답을 내는 알고리즘이다. 정확한 답을 내려면 서로 다른 원소 수에 비례하는 메모리가 필요하다는 하한이 있기 때문에, 대신 오차와 실패확률을 파라미터로 받아 확률적 보장을 주는 스케치 자료구조를 쓴다. heavy hitters(빈도 상위 원소 찾기)는 Misra-Gries처럼 카운터를 고정 개수만 유지하며 일괄 감소시키는 방식이나, Count-Min Sketch처럼 여러 해시 함수로 2차원 카운터 배열에 더하고 최솟값을 추정치로 쓰는 방식으로 푼다. 근사 분위수는 t-digest, KLL 같은 구조가 표본을 계층적으로 압축해 원하는 분위수를 오차 범위 안에서 답한다. 공통 성질은 스케치가 병합 가능(mergeable)해서 분산 환경에서 부분 스케치를 합칠 수 있다는 점이다.

로그·메트릭·주문 흐름처럼 전량 저장이 불가능한 데이터에서 상위 사용자, p99 지연 같은 값을 실시간으로 알아야 할 때 정확 집계는 메모리에서 먼저 무너진다.

코드 · 수식

# 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

연습

Count-Min Sketch를 직접 구현해 실제 로그 스트림에 돌리고, 정확 카운트와 비교해 폭(width)을 바꿔가며 과대추정 오차가 어떻게 줄어드는지 표로 만들어 보라.

실무 · Verex 연결

노드 운영에서 RPC 메서드별 호출 상위 클라이언트나 가스 소비 상위 컨트랙트를 상시 집계하거나, Verex의 주문 흐름에서 체결 지연 분위수를 저비용으로 모니터링하는 데 그대로 쓰인다.

Jayverse에서의 위치

• Verex: gitboard의 체결 지연 p99를 저장된 샘플이 아니라 t-digest나 KLL 스케치로 뒷받침한다. 주문 흐름은 정확히 이 페이지가 말하는 스트림이다 — 전부 저장하기엔 너무 많고, 병합 가능한 스케치가 대시보드의 실시간 분위수를 싸게 만든다.
• Devnet: RPC 메서드 호출에 Count-Min Sketch를 돌려 용량 문제가 되기 전에 많이 호출하는 대상을 찾는다. devnet 노드에서 상위 호출자와 상위 가스 소비 컨트랙트를 추적하는 것은 모든 요청을 저장하지 않고 푸는 동일한 heavy-hitters 문제다.

공부한 날 원본 커리큘럼(docs/knowledge/dev-100-curriculum.md)의 이 줄에 노트 링크와 ✅ 를 붙이면, 이 자리는 노트 본문으로 바로 이어집니다. 노트 없이 이 페이지에 바로 적어도 됩니다 — 다만 다시 생성하면 덮어쓰이므로, 남길 글은 docs/algorithms/ 의 마크다운으로 쓰는 편이 안전합니다.