mirror of
https://github.com/hanzoai/skills.git
synced 2026-11-19 00:47:36 +00:00
Every page now loads /webmcp.js, scripts/webmcp.ts with its types stripped (npm run webmcp). Where the browser has document.modelContext it registers two read-only tools: search_skills over the published skills index, and get_skill, which returns a skill's markdown checked against the index digest. The markdown alternate link moves from build.py to site.py, so CI holds every page to it. The API catalog gains the site itself (llms.txt and the skills index) and hanzo.ai/agents; the live discovery check now fetches every catalog link. tests/site.mjs drives the tools through a recording modelContext, and checks a browser without one loads clean.
493 lines
23 KiB
HTML
493 lines
23 KiB
HTML
<!doctype html>
|
|
<html lang="en"><head>
|
|
<meta charset="utf-8"><meta name="viewport" content="width=device-width,initial-scale=1">
|
|
<title>distributed-systems-probabilistic-data-structures</title>
|
|
<meta name="color-scheme" content="dark">
|
|
<style>
|
|
/* Committed to one visual world: a dark instrument panel. No light variant —
|
|
the dot field and the hairline rules only read on black, and a naive
|
|
inversion would wash both out. Every colour is painted explicitly so the page
|
|
never borrows a host background. */
|
|
@font-face{font-family:'Zen';src:url('/fonts/Zen-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
|
|
@font-face{font-family:'Zen';src:url('/fonts/Zen-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
|
|
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
|
|
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
|
|
@font-face{font-family:'Zen Pixel Square';src:url('/fonts/ZenPixel-Square.woff2') format('woff2');font-style:normal;font-display:swap}
|
|
|
|
:root{
|
|
--ink:#f4f4f2; --soft:#9c9c98; --faint:#6a6a66; --ground:#000; --panel:#0a0a0a;
|
|
--line:#232323; --line-hi:#3a3a3a; --accent:#f4f4f2;
|
|
--font-zen-sans:'Zen',-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif;
|
|
--font-zen-mono:'Zen Mono',ui-monospace,"SF Mono",SFMono-Regular,Menlo,Consolas,monospace;
|
|
--font-zen-pixel-square:'Zen Pixel Square',monospace;
|
|
--mono:var(--font-zen-mono);
|
|
--sans:var(--font-zen-sans);
|
|
/* Controls are pills and surfaces are soft, as on hanzo.ai. */
|
|
--r:999px; --r-soft:14px;
|
|
}
|
|
*{box-sizing:border-box}
|
|
html{-webkit-text-size-adjust:100%}
|
|
body{margin:0;background:var(--ground);color:var(--ink);font-family:var(--sans);
|
|
font-size:16px;line-height:1.65;-webkit-font-smoothing:antialiased}
|
|
.wrap{max-width:60rem;margin:0 auto;padding:0 1.75rem}
|
|
|
|
/* The dot field. A halftone made of one repeating radial-gradient, faded out
|
|
along the diagonal by a mask so it reads as a wave rather than wallpaper. */
|
|
/* No overflow clip here: the dot field is inset to the box already, and a clip
|
|
would cut off the copy-prompt menu. */
|
|
.hero{position:relative;border-bottom:1px solid var(--line)}
|
|
.hero::before{content:"";position:absolute;inset:0;
|
|
background-image:radial-gradient(var(--line-hi) 1px, transparent 1px);
|
|
background-size:7px 7px;
|
|
-webkit-mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
|
|
mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
|
|
pointer-events:none}
|
|
.hero .wrap{position:relative;padding-top:5.5rem;padding-bottom:4rem}
|
|
|
|
nav{border-bottom:1px solid var(--line)}
|
|
nav .in{max-width:60rem;margin:0 auto;padding:1.1rem 1.75rem;display:flex;
|
|
justify-content:space-between;align-items:center;gap:1rem}
|
|
.brand{font-family:var(--mono);font-size:.85rem;letter-spacing:.14em;
|
|
text-transform:uppercase;color:var(--ink);text-decoration:none;
|
|
display:inline-flex;align-items:center;gap:.6rem}
|
|
.brand i{font-style:normal;color:var(--faint)}
|
|
.mark{width:1.15em;height:1.15em;display:block;flex:0 0 auto}
|
|
nav a.up{font-family:var(--mono);font-size:.72rem;letter-spacing:.14em;
|
|
text-transform:uppercase;color:var(--soft);text-decoration:none}
|
|
nav a.up:hover{color:var(--ink)}
|
|
|
|
h1{font-family:var(--mono);font-size:clamp(2rem,5.4vw,3.4rem);line-height:1.12;
|
|
letter-spacing:-.02em;margin:0 0 1.1rem;font-weight:500;text-wrap:balance}
|
|
h1 em{font-style:normal;color:var(--faint)}
|
|
.lede{color:var(--soft);font-size:1.05rem;max-width:52ch;margin:0 0 2.25rem}
|
|
|
|
.btns{display:flex;flex-wrap:wrap;gap:.7rem;margin:0 0 .5rem;align-items:center}
|
|
.btn{display:inline-flex;align-items:center;gap:.5rem;font-family:var(--mono);
|
|
font-size:.72rem;letter-spacing:.14em;text-transform:uppercase;
|
|
padding:.8rem 1.4rem;border:1px solid var(--line-hi);border-radius:var(--r);
|
|
color:var(--ink);text-decoration:none;background:transparent;cursor:pointer;
|
|
line-height:1.2;font-weight:400}
|
|
.btn:hover{background:#141414;text-decoration:none;border-color:var(--soft)}
|
|
.btn.solid{background:var(--ink);color:#000;border-color:var(--ink)}
|
|
.btn.solid:hover{background:#d8d8d4}
|
|
.btn .chev{width:.7em;height:.7em;flex:0 0 auto;transition:transform .15s ease}
|
|
.btn[aria-expanded="true"] .chev{transform:rotate(180deg)}
|
|
|
|
/* Copy-prompt selector. Each row copies the prompt for its own target. */
|
|
.copy{position:relative;display:inline-flex}
|
|
.menu{position:absolute;top:calc(100% + .5rem);left:0;z-index:20;min-width:21rem;
|
|
background:var(--panel);border:1px solid var(--line-hi);border-radius:var(--r-soft);
|
|
padding:.4rem;display:flex;flex-direction:column;
|
|
box-shadow:0 12px 32px rgba(0,0,0,.75)}
|
|
.menu[hidden]{display:none}
|
|
.mi{display:flex;align-items:center;gap:.7rem;width:100%;text-align:left;
|
|
padding:.62rem .8rem;border:0;border-radius:calc(var(--r-soft) - .35rem);
|
|
background:transparent;color:var(--ink);font-family:var(--mono);font-size:.76rem;
|
|
letter-spacing:.04em;text-decoration:none;cursor:pointer;line-height:1.3;
|
|
white-space:nowrap}
|
|
.mi:hover,.mi:focus-visible{background:#181818;outline:none}
|
|
.mi .mark{width:1.05rem;height:1.05rem;color:var(--soft)}
|
|
.mi:hover .mark{color:var(--ink)}
|
|
.mi u{margin-left:auto;color:var(--faint);text-decoration:none;font-size:.68rem;
|
|
letter-spacing:.1em;text-transform:uppercase}
|
|
|
|
/* Works-with bar: one scrolling row, name and mark per agent. */
|
|
.strip{border-bottom:1px solid var(--line);background:var(--panel)}
|
|
.strip .in{max-width:60rem;margin:0 auto;padding:.9rem 1.75rem;display:flex;
|
|
align-items:center;gap:1.25rem;font-family:var(--mono);font-size:.72rem;
|
|
letter-spacing:.1em;text-transform:uppercase;color:var(--faint)}
|
|
.strip b{color:var(--soft);font-weight:400;flex:0 0 auto;
|
|
border-right:1px solid var(--line);padding-right:1.25rem;align-self:stretch;
|
|
display:flex;align-items:center}
|
|
.bar{display:flex;align-items:center;gap:.5rem;flex:1 1 auto;min-width:0;
|
|
overflow-x:auto;scrollbar-width:none;scroll-snap-type:x proximity;
|
|
-webkit-overflow-scrolling:touch;
|
|
-webkit-mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent);
|
|
mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent)}
|
|
.bar::-webkit-scrollbar{display:none}
|
|
.agent{display:inline-flex;align-items:center;gap:.45rem;flex:0 0 auto;
|
|
padding:.4rem .85rem;border:1px solid var(--line);border-radius:var(--r);
|
|
color:var(--soft);white-space:nowrap;scroll-snap-align:start;
|
|
text-decoration:none;background:var(--ground)}
|
|
.agent:hover{color:var(--ink);border-color:var(--line-hi);text-decoration:none}
|
|
.agent .mark{width:.95rem;height:.95rem}
|
|
|
|
h2{font-family:var(--mono);font-size:1.1rem;letter-spacing:-.01em;margin:2.75rem 0 .75rem;font-weight:500}
|
|
h3{font-size:1rem;margin:2rem 0 .5rem;font-weight:600}
|
|
h4,h5,h6{font-size:.94rem;margin:1.5rem 0 .5rem;font-weight:600}
|
|
p{margin:0 0 1rem;max-width:70ch}
|
|
ul,ol{margin:0 0 1rem;padding-left:1.35rem;max-width:70ch}
|
|
li{margin:.22rem 0}
|
|
a{color:var(--ink);text-decoration:underline;text-underline-offset:3px;
|
|
text-decoration-color:var(--line-hi)}
|
|
a:hover{text-decoration-color:var(--ink)}
|
|
a:focus-visible{outline:1px solid var(--ink);outline-offset:3px}
|
|
code{font-family:var(--mono);font-size:.85em;background:var(--panel);
|
|
border:1px solid var(--line);border-radius:5px;padding:.1em .36em}
|
|
pre{background:var(--panel);border:1px solid var(--line);padding:1rem 1.1rem;
|
|
border-radius:var(--r-soft);overflow-x:auto;margin:0 0 1.25rem}
|
|
pre code{background:none;border:0;padding:0;font-size:.82rem;line-height:1.7}
|
|
blockquote{margin:0 0 1rem;padding-left:1rem;border-left:1px solid var(--line-hi);color:var(--soft)}
|
|
hr{border:0;border-top:1px solid var(--line);margin:2.5rem 0}
|
|
table{border-collapse:collapse;width:100%;margin:0 0 1.25rem;font-size:.92rem;
|
|
display:block;overflow-x:auto}
|
|
th,td{border:1px solid var(--line);padding:.5rem .7rem;text-align:left}
|
|
|
|
.curl{display:block;background:var(--panel);border:1px solid var(--line);
|
|
border-radius:var(--r-soft);padding:.95rem 1.1rem;font-family:var(--mono);
|
|
font-size:.8rem;color:var(--soft);overflow-x:auto;margin:0 0 2.5rem;
|
|
white-space:pre;line-height:1.9}
|
|
.curl b{color:var(--ink);font-weight:400}
|
|
.curl i{font-style:normal;color:var(--faint)}
|
|
|
|
/* index */
|
|
#q{width:100%;padding:.85rem 1.2rem;font-family:var(--mono);font-size:.85rem;color:var(--ink);
|
|
background:var(--panel);border:1px solid var(--line);border-radius:var(--r);margin:0 0 .6rem}
|
|
#q::placeholder{color:var(--faint);text-transform:uppercase;letter-spacing:.1em;font-size:.72rem}
|
|
#q:focus{outline:none;border-color:var(--soft)}
|
|
#count{color:var(--faint);font-family:var(--mono);font-size:.72rem;letter-spacing:.1em;
|
|
text-transform:uppercase;margin:0 0 2rem}
|
|
.cat{margin:2.5rem 0 .5rem;font-family:var(--mono);font-size:.7rem;letter-spacing:.16em;
|
|
text-transform:uppercase;color:var(--faint);border-bottom:1px solid var(--line);
|
|
padding-bottom:.45rem}
|
|
.row{display:block;padding:.6rem .9rem;margin:0 -.9rem;border-bottom:1px solid var(--line);
|
|
border-radius:var(--r-soft);text-decoration:none}
|
|
.row:hover{background:#0a0a0a}
|
|
.nm{font-family:var(--mono);font-size:.84rem;color:var(--ink);display:block}
|
|
.ds{color:var(--soft);font-size:.9rem;display:block;margin-top:.12rem}
|
|
footer{margin-top:4rem;padding:2rem 0 4rem;border-top:1px solid var(--line);
|
|
color:var(--faint);font-size:.85rem}
|
|
footer a{color:var(--soft)}
|
|
.fmap{display:grid;gap:1.75rem;grid-template-columns:repeat(auto-fit,minmax(11rem,1fr));
|
|
margin:0 0 2rem;font-size:.85rem}
|
|
.fmap b{display:block;font-family:var(--mono);font-size:.68rem;letter-spacing:.16em;
|
|
text-transform:uppercase;color:var(--faint);font-weight:400;margin:0 0 .6rem;
|
|
border-bottom:1px solid var(--line);padding-bottom:.4rem}
|
|
.fmap a{display:inline-block;color:var(--ink);text-decoration:none;margin:.3rem .35rem 0 0}
|
|
.fmap a:hover{text-decoration:underline}
|
|
.fmap div{color:var(--faint);line-height:1.5}
|
|
.fend{border-top:1px solid var(--line);padding-top:1.25rem;font-size:.82rem}
|
|
|
|
@media (max-width:640px){
|
|
.hero .wrap{padding-top:3.25rem;padding-bottom:2.75rem}
|
|
.btns{gap:.5rem}
|
|
.btn{padding:.75rem 1.15rem;font-size:.68rem}
|
|
.copy,.copy .btn{width:100%;justify-content:center}
|
|
.menu{left:0;right:0;min-width:0}
|
|
.strip .in{flex-direction:column;align-items:flex-start;gap:.6rem;padding:.9rem 1.75rem}
|
|
.strip b{border-right:0;padding-right:0}
|
|
.bar{width:100%}
|
|
}
|
|
</style>
|
|
<link rel="icon" href="/favicon.svg">
|
|
<link rel="canonical" href="https://hanzoskills.com/distributed-systems-probabilistic-data-structures">
|
|
<link rel="alternate" type="text/markdown" href="/distributed-systems-probabilistic-data-structures.md">
|
|
<script type="module" src="/webmcp.js"></script>
|
|
</head>
|
|
<!-- Reading this with a machine? Every page here is also plain markdown.
|
|
This one: https://hanzoskills.com/distributed-systems-probabilistic-data-structures.md
|
|
Index: https://hanzoskills.com/llms.txt
|
|
Corpus: https://hanzoskills.com/all.md
|
|
Append .md to any path for the markdown twin. -->
|
|
<body>
|
|
<nav><div class="in">
|
|
<a class="brand" href="/"><svg class="mark" viewBox="0 0 67 67" fill="currentColor" aria-hidden="true"><path d="M22.21 67V44.6369H0V67H22.21Z"/><path d="M66.7038 22.3184H22.2534L0.0878906 44.6367H44.4634L66.7038 22.3184Z"/><path d="M22.21 0H0V22.3184H22.21V0Z"/><path d="M66.7198 0H44.5098V22.3184H66.7198V0Z"/><path d="M66.7198 67V44.6369H44.5098V67H66.7198Z"/></svg> HANZO<i>SKILLS</i></a>
|
|
<a class="up" href="/">All skills</a>
|
|
</div></nav>
|
|
|
|
<div class="wrap">
|
|
<h1>distributed-systems-probabilistic-data-structures</h1><p class="lede">Probabilistic data structures including Bloom filters, HyperLogLog, Count-Min Sketch for space-efficient approximations</p><h1>Probabilistic Data Structures</h1>
|
|
<p><strong>Scope</strong>: Bloom filters, HyperLogLog, Count-Min Sketch, space-efficient algorithms <strong>Lines</strong>: ~240 <strong>Last Updated</strong>: 2025-10-27 <strong>Format Version</strong>: 1.0 (Atomic)</p>
|
|
<hr>
|
|
<h2>When to Use This Skill</h2>
|
|
<p>Activate this skill when:</p>
|
|
<ul><li>Space constraints critical</li><li>Approximate answers acceptable</li><li>Working with large-scale data</li><li>Implementing caching layers</li><li>Building distributed databases</li><li>Deduplication at scale</li><li>Cardinality estimation</li><li>Frequency estimation</li></ul>
|
|
<h2>Core Concepts</h2>
|
|
<h3>Trade-off: Space vs Accuracy</h3>
|
|
<pre><code>Traditional data structures: Exact answers, more space
|
|
Probabilistic structures: Approximate answers, less space
|
|
|
|
Example: Set membership
|
|
- Hash set: O(n) space, exact
|
|
- Bloom filter: O(1) space per element, small false positive rate</code></pre>
|
|
<hr>
|
|
<h2>Bloom Filter</h2>
|
|
<h3>Overview</h3>
|
|
<p><strong>Purpose</strong>: Test set membership with false positives (but no false negatives)</p>
|
|
<pre><code>Bloom filter says:
|
|
- "Definitely not in set" → 100% accurate
|
|
- "Probably in set" → May have false positives</code></pre>
|
|
<h3>Implementation</h3>
|
|
<pre><code class="lang-python">import hashlib
|
|
|
|
class BloomFilter:
|
|
"""Space-efficient probabilistic set"""
|
|
|
|
def __init__(self, size=1000, num_hashes=3):
|
|
self.size = size
|
|
self.num_hashes = num_hashes
|
|
self.bits = [False] * size
|
|
|
|
def _hashes(self, item):
|
|
"""Generate k hash values"""
|
|
hashes = []
|
|
for i in range(self.num_hashes):
|
|
# Use different seeds for each hash
|
|
hash_input = f"{item}:{i}".encode()
|
|
hash_val = int(hashlib.md5(hash_input).hexdigest(), 16)
|
|
hashes.append(hash_val % self.size)
|
|
return hashes
|
|
|
|
def add(self, item):
|
|
"""Add item to set"""
|
|
for hash_val in self._hashes(item):
|
|
self.bits[hash_val] = True
|
|
|
|
def contains(self, item):
|
|
"""Check if item might be in set"""
|
|
return all(self.bits[h] for h in self._hashes(item))
|
|
|
|
# Usage
|
|
bf = BloomFilter(size=1000, num_hashes=3)
|
|
|
|
bf.add('apple')
|
|
bf.add('banana')
|
|
|
|
print(bf.contains('apple')) # True (definitely added)
|
|
print(bf.contains('cherry')) # False (definitely not added)
|
|
print(bf.contains('xyz')) # Maybe False (could be false positive)
|
|
|
|
# False positive rate depends on size, num_hashes, num_items</code></pre>
|
|
<h3>Applications</h3>
|
|
<pre><code>✅ Cache filtering (check before expensive lookup)
|
|
✅ Deduplication (seen this data before?)
|
|
✅ Spell checking (is this a valid word?)
|
|
✅ Network routers (packet filtering)</code></pre>
|
|
<p><strong>Example: Cache Filter</strong></p>
|
|
<pre><code class="lang-python">class CachedStore:
|
|
def __init__(self):
|
|
self.cache = {}
|
|
self.bloom = BloomFilter(size=10000)
|
|
|
|
def get(self, key):
|
|
# Quick check with Bloom filter
|
|
if not self.bloom.contains(key):
|
|
# Definitely not in cache
|
|
return self.fetch_from_db(key)
|
|
|
|
# Maybe in cache - check actual cache
|
|
if key in self.cache:
|
|
return self.cache[key]
|
|
else:
|
|
# False positive
|
|
return self.fetch_from_db(key)
|
|
|
|
def put(self, key, value):
|
|
self.cache[key] = value
|
|
self.bloom.add(key)</code></pre>
|
|
<hr>
|
|
<h2>HyperLogLog</h2>
|
|
<h3>Overview</h3>
|
|
<p><strong>Purpose</strong>: Estimate cardinality (count distinct elements) with small memory</p>
|
|
<pre><code>Traditional: Store all elements → O(n) space
|
|
HyperLogLog: Fixed memory (few KB) → estimates count within 2% error</code></pre>
|
|
<h3>Implementation (Simplified)</h3>
|
|
<pre><code class="lang-python">import hashlib
|
|
import math
|
|
|
|
class HyperLogLog:
|
|
"""Cardinality estimation"""
|
|
|
|
def __init__(self, precision=14):
|
|
self.precision = precision
|
|
self.m = 1 << precision # 2^precision buckets
|
|
self.registers = [0] * self.m
|
|
|
|
def _hash(self, item):
|
|
"""Hash item to 64-bit value"""
|
|
return int(hashlib.md5(str(item).encode()).hexdigest(), 16) & ((1 << 64) - 1)
|
|
|
|
def add(self, item):
|
|
"""Add item"""
|
|
h = self._hash(item)
|
|
|
|
# Use first p bits for bucket index
|
|
bucket = h & (self.m - 1)
|
|
|
|
# Count leading zeros in remaining bits
|
|
remaining = h >> self.precision
|
|
leading_zeros = self._count_leading_zeros(remaining, 64 - self.precision)
|
|
|
|
# Update register with maximum
|
|
self.registers[bucket] = max(self.registers[bucket], leading_zeros + 1)
|
|
|
|
def cardinality(self):
|
|
"""Estimate cardinality"""
|
|
# Harmonic mean of 2^register values
|
|
raw_estimate = self._alpha() * (self.m ** 2) / sum(2 ** (-reg) for reg in self.registers)
|
|
|
|
# Bias correction for small/large cardinalities
|
|
if raw_estimate <= 2.5 * self.m:
|
|
# Small range correction
|
|
zeros = self.registers.count(0)
|
|
if zeros != 0:
|
|
return self.m * math.log(self.m / zeros)
|
|
|
|
return int(raw_estimate)
|
|
|
|
def _alpha(self):
|
|
"""Bias correction constant"""
|
|
if self.m >= 128:
|
|
return 0.7213 / (1 + 1.079 / self.m)
|
|
elif self.m >= 64:
|
|
return 0.709
|
|
elif self.m >= 32:
|
|
return 0.697
|
|
else:
|
|
return 0.673
|
|
|
|
def _count_leading_zeros(self, value, max_width):
|
|
"""Count leading zeros"""
|
|
if value == 0:
|
|
return max_width
|
|
return max_width - value.bit_length()
|
|
|
|
def merge(self, other):
|
|
"""Merge with another HyperLogLog"""
|
|
for i in range(self.m):
|
|
self.registers[i] = max(self.registers[i], other.registers[i])
|
|
|
|
# Usage
|
|
hll = HyperLogLog()
|
|
|
|
# Add millions of items
|
|
for i in range(1000000):
|
|
hll.add(f"user_{i}")
|
|
|
|
print(f"Estimated unique users: {hll.cardinality()}") # ~1,000,000
|
|
# Uses only ~16KB memory!</code></pre>
|
|
<h3>Applications</h3>
|
|
<pre><code>✅ Unique visitors counting (web analytics)
|
|
✅ Distinct IP addresses
|
|
✅ Database query optimization (cardinality estimates)
|
|
✅ Stream processing (count unique events)</code></pre>
|
|
<hr>
|
|
<h2>Count-Min Sketch</h2>
|
|
<h3>Overview</h3>
|
|
<p><strong>Purpose</strong>: Estimate frequency of elements with bounded error</p>
|
|
<pre><code>Traditional: Hash map → O(n) space, exact counts
|
|
Count-Min Sketch: Fixed memory → approximate counts with error bound</code></pre>
|
|
<h3>Implementation</h3>
|
|
<pre><code class="lang-python">import hashlib
|
|
|
|
class CountMinSketch:
|
|
"""Frequency estimation"""
|
|
|
|
def __init__(self, width=1000, depth=7):
|
|
self.width = width
|
|
self.depth = depth
|
|
self.table = [[0] * width for _ in range(depth)]
|
|
|
|
def _hashes(self, item):
|
|
"""Generate d hash values"""
|
|
hashes = []
|
|
for i in range(self.depth):
|
|
hash_input = f"{item}:{i}".encode()
|
|
hash_val = int(hashlib.md5(hash_input).hexdigest(), 16)
|
|
hashes.append(hash_val % self.width)
|
|
return hashes
|
|
|
|
def add(self, item, count=1):
|
|
"""Increment count for item"""
|
|
for i, h in enumerate(self._hashes(item)):
|
|
self.table[i][h] += count
|
|
|
|
def estimate(self, item):
|
|
"""Estimate count (returns minimum across rows)"""
|
|
return min(self.table[i][h] for i, h in enumerate(self._hashes(item)))
|
|
|
|
# Usage
|
|
cms = CountMinSketch(width=1000, depth=7)
|
|
|
|
# Count events
|
|
for event in event_stream:
|
|
cms.add(event)
|
|
|
|
# Estimate frequency
|
|
print(f"Event X count: {cms.estimate('event_x')}") # Approximate count
|
|
# Never underestimates, may overestimate due to collisions</code></pre>
|
|
<h3>Applications</h3>
|
|
<pre><code>✅ Heavy hitters detection (top-k frequent items)
|
|
✅ Network traffic analysis
|
|
✅ Query frequency estimation
|
|
✅ Rate limiting (count requests per user)</code></pre>
|
|
<hr>
|
|
<h2>Comparison</h2>
|
|
<p>| Structure | Purpose | Space | Accuracy | False Positives | |-----------|---------|-------|----------|-----------------| | <strong>Bloom Filter</strong> | Membership | O(1) per item | High | Yes (tunable) | | <strong>HyperLogLog</strong> | Cardinality | Fixed (~KB) | ~2% error | N/A | | <strong>Count-Min Sketch</strong> | Frequency | Fixed | Bounded error | Overestimates | | <strong>Hash Set</strong> | Membership | O(n) | 100% | No | | <strong>Hash Map</strong> | Frequency | O(n) | 100% | No |</p>
|
|
<hr>
|
|
<h2>Choosing the Right Structure</h2>
|
|
<h3>Use Bloom Filter When:</h3>
|
|
<pre><code class="lang-python"># Large set, only need membership test
|
|
user_blacklist = BloomFilter(size=1000000)
|
|
|
|
if user_blacklist.contains(user_id):
|
|
# Might be blacklisted - check database
|
|
if database.is_blacklisted(user_id):
|
|
reject()</code></pre>
|
|
<h3>Use HyperLogLog When:</h3>
|
|
<pre><code class="lang-python"># Count unique items in stream
|
|
unique_visitors = HyperLogLog()
|
|
|
|
for request in request_stream:
|
|
unique_visitors.add(request.user_id)
|
|
|
|
print(f"DAU: {unique_visitors.cardinality()}")</code></pre>
|
|
<h3>Use Count-Min Sketch When:</h3>
|
|
<pre><code class="lang-python"># Track frequency, find heavy hitters
|
|
request_counts = CountMinSketch()
|
|
|
|
for request in request_stream:
|
|
request_counts.add(request.endpoint)
|
|
|
|
# Find most frequent endpoints
|
|
top_endpoints = [(e, request_counts.estimate(e)) for e in endpoints]
|
|
top_endpoints.sort(key=lambda x: x[1], reverse=True)</code></pre>
|
|
<hr>
|
|
<h2>Real-World Examples</h2>
|
|
<h3>Redis</h3>
|
|
<pre><code class="lang-bash"># HyperLogLog for unique counting
|
|
PFADD unique_visitors user:123
|
|
PFCOUNT unique_visitors # Approximate count
|
|
|
|
# Bloom filter (via RedisBloom module)
|
|
BF.ADD bloom_filter "item"
|
|
BF.EXISTS bloom_filter "item"</code></pre>
|
|
<h3>Cassandra</h3>
|
|
<pre><code>Uses Bloom filters for:
|
|
- SSTable filtering (avoid disk reads)
|
|
- Reduce false positive rate with multiple hash functions</code></pre>
|
|
<hr>
|
|
<h2>Related Skills</h2>
|
|
<ul><li><code>distributed-systems-eventual-consistency</code> - Consistency trade-offs</li><li><code>distributed-systems-partitioning-sharding</code> - Data distribution</li><li><code>distributed-systems-gossip-protocols</code> - Epidemic algorithms</li></ul>
|
|
<hr>
|
|
<p><strong>Last Updated</strong>: 2025-10-27</p>
|
|
<footer>
|
|
<div class="fmap">
|
|
<div><b>Build</b>
|
|
<a href="https://hanzo.app">hanzo.app</a> app builder
|
|
<a href="https://hanzo.codes">hanzo.codes</a> code with an agent
|
|
<a href="https://hanzoskills.com">hanzoskills.com</a> what an agent reads</div>
|
|
<div><b>Run</b>
|
|
<a href="https://console.hanzo.ai">console.hanzo.ai</a> cloud console
|
|
<a href="https://api.hanzo.ai">api.hanzo.ai</a> the API</div>
|
|
<div><b>Account</b>
|
|
<a href="https://hanzo.id">hanzo.id</a> sign in
|
|
<a href="https://pay.hanzo.ai">pay.hanzo.ai</a> top up
|
|
<a href="https://billing.hanzo.ai">billing.hanzo.ai</a> invoices and usage</div>
|
|
<div><b>Company</b>
|
|
<a href="https://hanzo.ai">hanzo.ai</a> canonical
|
|
<a href="https://hanzo.ventures">hanzo.ventures</a> ventures</div>
|
|
</div>
|
|
<div class="fend"><a href="/distributed-systems-probabilistic-data-structures.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
|
|
</footer>
|
|
</div></body></html> |