Probabilistic Data Structures in Go
mfrw
41 points
5 comments
November 14, 2026
Related Discussions
Found 5 related stories in 121.7ms across 12,728 title embeddings via pgvector HNSW
- Go Concurrency Distilled chmaynard · 139 pts · September 26, 2026 · 51% similar
- Generic Methods in Go 1.27 EspressoGPT · 62 pts · August 20, 2026 · 49% similar
- Prolly: A content-addressed ordered map built on prolly trees forhappy · 23 pts · August 17, 2026 · 49% similar
- Platform-independent SIMD in Go yurivish · 375 pts · September 25, 2026 · 48% similar
- Go 1.27 database64128 · 555 pts · August 19, 2026 · 45% similar
Discussion Highlights (5 comments)
jpitz
My introduction to probabilistic data structures was Pugh's skip list, which is probabilistic in structure and performance, but precise with answers.
aarjaneiro
Note a lot of the diagrams seem broken
ncruces
I'm in the process of adding a few of these to my Go SQLite driver. https://pkg.go.dev/github.com/ncruces/go-sqlite3/ext/approx They work as window functions, and they also support creating roll-up tables, e.g. you have a table storing a sketch of daily active users and can use that to get weekly and monthly active users. Same for quantiles (e.g. median and tail latencies) and next up top-K (e.g. most popular content, highest spenders, etc).
donatj
I'm kind of sad there's no mention of Cuckoo filters. I've generally found them preferable to Bloom filters
kristianp
Now I've learnt about blocked Bloom filters: > Unsure uses a blocked Bloom filter. The bit array is divided into 512-bit blocks, each matching the size of a CPU cache line. When you add or check an item, it is hashed once: part of the hash selects a block, and the rest selects k bits within that block. The article also has a good quality list of references.