Probabilistic Data Structures in Go

mfrw 41 points 5 comments November 14, 2026
antonz.org · View on Hacker News

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.

Semantic search powered by Rivestack pgvector
12,728 stories · 120,417 chunks indexed