NHacker Next
  • new
  • past
  • show
  • ask
  • show
  • jobs
  • submit
▲Probabilistic Data Structures in Go (antonz.org)
mfrw 2 hours ago [-]
A related CppCon talk: Fantastic Algorithms and Where To Find Them & the related GitHub Repo:

- https://youtu.be/YA-nB2wjVcI

- https://github.com/CppCon/CppCon2017

ncruces 11 hours ago [-]
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 8 hours ago [-]
I'm kind of sad there's no mention of Cuckoo filters. I've generally found them preferable to Bloom filters
kristianp 6 hours ago [-]
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.

jpitz 13 hours ago [-]
My introduction to probabilistic data structures was Pugh's skip list, which is probabilistic in structure and performance, but precise with answers.
aarjaneiro 12 hours ago [-]
Note a lot of the diagrams seem broken
Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact
Rendered at 11:05:44 GMT+0000 (Coordinated Universal Time) with Vercel.