---
id: cs-probabilistic-data-structures
title: Probabilistic Data Structures — HLL / Count-min / t-digest
category: Coding
status: draft
source_trust_level: B
verification_status: conceptual
created_at: 2026-05-09
updated_at: 2026-05-09
tags: [cs, probabilistic, vibe-coding]
tech_stack: { language: "TS / Redis / SQL", applicable_to: ["Backend"] }
applied_in: []
aliases: [HyperLogLog, count-min sketch, t-digest, top-k, TimeSeries quantile]
---

# Probabilistic Data Structures

> 정확히 vs 작은 메모리 trade. **HyperLogLog (cardinality), Count-min (frequency), t-digest (quantile), Top-K**. Postgres / Redis / ClickHouse 가 내장.

## 📖 핵심 개념
- 정확 vs 근사 + 메모리 + 속도.
- 일반적으로 0.5-2% 오차.
- 매우 작은 메모리 (12KB-수MB).

## 💻 코드 패턴

### HyperLogLog — unique count
```ts
// Redis
await redis.pfadd('uniq:visitors:2026-05-09', userId);
const dau = await redis.pfcount('uniq:visitors:2026-05-09');

// Merge (여러 day → week)
await redis.pfmerge('uniq:visitors:week', 
  'uniq:visitors:2026-05-03',
  'uniq:visitors:2026-05-04',
  // ...
);
```

```sql
-- Postgres
CREATE EXTENSION hll;

CREATE TABLE daily_uniq (
  day DATE PRIMARY KEY,
  visitors hll
);

INSERT INTO daily_uniq VALUES (CURRENT_DATE, hll_empty())
ON CONFLICT (day) DO UPDATE
SET visitors = hll_add(daily_uniq.visitors, hll_hash_text($user));

SELECT day, hll_cardinality(visitors) FROM daily_uniq;
SELECT hll_cardinality(hll_union_agg(visitors)) FROM daily_uniq WHERE day >= NOW() - INTERVAL '7 days';
```

→ 12KB 로 수억 unique 추정. 1.625% 오차.

### Count-min sketch — frequency
```ts
class CountMin {
  private table: number[][];
  
  constructor(private d: number, private w: number) {
    this.table = Array.from({ length: d }, () => new Array(w).fill(0));
  }
  
  add(item: string, count = 1) {
    for (let i = 0; i < this.d; i++) {
      const idx = hash(item, i) % this.w;
      this.table[i][idx] += count;
    }
  }
  
  estimate(item: string): number {
    let min = Infinity;
    for (let i = 0; i < this.d; i++) {
      const idx = hash(item, i) % this.w;
      min = Math.min(min, this.table[i][idx]);
    }
    return min;
  }
}

const cms = new CountMin(5, 1024);
for (const ev of events) cms.add(ev.userId);
cms.estimate('u42');  // 빈도 추정 (over-estimate)
```

→ 큰 stream 의 빈도 추정. heavy hitter 검출.

### Redis Count-min sketch
```bash
CMS.INITBYDIM cms 10000 5     # width 10000, depth 5
CMS.INCRBY cms user-42 1
CMS.QUERY cms user-42         # estimate
```

### Top-K (heavy hitters)
```bash
TOPK.RESERVE topk 10 1000 5 0.9
TOPK.ADD topk user-42 user-99 user-42
TOPK.LIST topk    # top 10 사용자
TOPK.QUERY topk user-42  # included?
```

→ 가장 자주 등장하는 N개. Twitter 트렌드 같은 use case.

### t-digest — quantile (p50, p95, p99)
```bash
TDIGEST.CREATE td 100
TDIGEST.ADD td 12.5 3.4 8.9 ...
TDIGEST.QUANTILE td 0.95 0.99
```

```ts
import { TDigest } from 'tdigest';

const td = new TDigest();
for (const latency of latencies) td.push(latency);
td.percentile(0.95); // p95
td.percentile(0.99); // p99
```

→ 작은 메모리 (KB) + 매우 정확. 메트릭 시스템 표준.

```sql
-- Postgres TimescaleDB
SELECT
  time_bucket('1 minute', ts) AS bucket,
  approx_percentile(0.95, percentile_agg(latency_ms)) AS p95
FROM events
GROUP BY bucket;
```

### Top-K query 흔히
```sql
-- ClickHouse
SELECT topK(10)(user_id) FROM events;
```

### Bloom (위 문서)
- Set 멤버십.

### Cuckoo
- Bloom + delete.

### MinHash — similarity
```
2 set 의 Jaccard similarity 추정.
검색 / 중복 detection.
```

### 사용 예
```
DAU/MAU:           HLL
Trending hashtag:  Top-K
Latency p95/p99:   t-digest
Frequency cap:     Count-min
Spam URL:          Bloom
URL dedup:         Bloom / Cuckoo
```

### 정확도 vs 메모리 trade
```
HLL:        12KB → 1.6% 오차 / 1MB → 0.4% 오차
Count-min:  16KB → small error
t-digest:   ~1KB → <1% quantile 오차
```

### 분산 merge
대부분 mergeable — 여러 노드 쪼갠 후 합칠 수 있음.

## 🤔 의사결정 기준
| 작업 | 도구 |
|---|---|
| DAU / 고유 사용자 | HLL |
| 빈도 추정 | Count-min |
| Top-K trending | TopK |
| Latency percentile | t-digest |
| Set membership | Bloom / Cuckoo |
| Similarity | MinHash |
| 정확 (작은 데이터) | 일반 array / set |

## ❌ 안티패턴
- **정확한 데이터 가정**: 항상 추정. 정확 필요시 다른 도구.
- **메모리 너무 작게**: 정확도 훼손.
- **합치기 incompatible 알고리즘**: 같은 알고리즘 + 같은 파라미터.
- **t-digest 결과를 그대로 비교**: 추정값이라 작은 차이 의미 X.
- **Distributed 환경 + 한 알고리즘 인스턴스**: contention. 분산 후 merge.
- **Top-K 결과 = exact 가정**: top 10 거의 정확, 11-20 fuzzy.

## 🤖 LLM 활용 힌트
- 메모리 한정 / 큰 stream = probabilistic.
- Redis Stack / Postgres extension 이 가벼운 시작.
- 정확 검증 필요 시 sample + 다시 측정.

## 🔗 관련 문서
- [[CS_Bloom_Filter]]
- [[DB_Time_Series_Patterns]]
- [[DB_ClickHouse_OLAP]]
