hn.today

Probabilistic Data Structures in Go

antonz.org62 points7 comments
Screenshot of Probabilistic Data Structures in Go

Probabilistic data structures answer questions about large collections approximately, trading exactness for substantial memory savings. The Go package UNSURE implements several such structures, including Bloom filters, count-min sketches, HyperLogLog, T-digest, and Top-k, using compact implementations and only the standard library. A Bloom filter checks whether an item is probably present: a negative answer is certain, while a positive can be a false alarm. It cannot delete items or reveal their contents. For one million distinct 8-byte strings, a filter with a 1% false-positive rate uses about 1.24 MB rather than roughly 64 MB. UNSURE’s blocked design keeps each lookup within one CPU cache line, improving speed at the cost of modest extra memory.

A count-min sketch estimates item frequencies without storing the items. Its estimates never fall below actual counts, and their likely error is bounded by a chosen fraction of the stream’s total count; this makes it more useful for frequent items than rare ones. It suits tasks such as request rate-limiting, alerting, and cache decisions, but cannot decrement counts or list tracked items. UNSURE uses conservative updates to reduce practical error, 32-bit counters to halve memory versus 64-bit designs, and a single hash with per-row salts. Benchmarks report Bloom-filter operations about four times faster than bits-and-blooms and twice as fast as gloom, with small memory tradeoffs. The sketch also outperforms BoomFilters in the cited add and count comparisons.

Read on antonz.org7 comments on Hacker News

Summary generated by AI from the linked article. hn.today is not affiliated with Hacker News or Y Combinator.

More in Programming

Aristotle Expands into Rust

Aristotle Expands into Rust

Aristotle has expanded its formal verification platform to Rust, allowing developers to prove code meets specifications and contains no undefined behavior, including in unsafe blocks. It can also verify that Rust rewrites behave like their original C code, targeting critical software such as smart contracts and infrastructure. (harmonic.fun)

The daily digest

Today's best Hacker News stories, summarized and screenshotted, one email a day.