<!-- mobian-agent-page publisher="dailydev" canonical="https://daily.dev/posts/probabilistic-data-structures-in-go-part-2-fo0jw59v9" -->

---
title: Probabilistic data structures in Go, part 2 | daily.dev
description: This post covers four probabilistic data structures implemented in the Go package 'unsure': binary fuse filter, UltraLogLog, log-linear histogram, and MinHash....
canonical: https://daily.dev/posts/probabilistic-data-structures-in-go-part-2-fo0jw59v9
twitter:card: summary_large_image
twitter:site: @dailydotdev
og:type: website
og:site_name: daily.dev
og:title: Probabilistic data structures in Go, part 2 | daily.dev
og:description: This post covers four probabilistic data structures implemented in the Go package 'unsure': binary fuse filter, UltraLogLog, log-linear histogram, and MinHash....
og:url: https://daily.dev/posts/probabilistic-data-structures-in-go-part-2-fo0jw59v9
og:image: https://api.daily.dev/og/posts/FO0Jw59V9.png
og:image:alt: Probabilistic data structures in Go, part 2
og:image:width: 1200
og:image:height: 630
og:locale: en
---

> ## Documentation Index
> Fetch the complete documentation index at: https://daily.dev/llms.txt
> Use this file to discover all available pages before exploring further.

# Probabilistic data structures in Go, part 2

**[Anton Zhiyanov](https://daily.dev/sources/antonz)** · 22 min read · 14 upvotes · 0 comments

## Summary

This post covers four probabilistic data structures implemented in the Go package 'unsure': binary fuse filter, UltraLogLog, log-linear histogram, and MinHash. A binary fuse filter is a static, more memory-efficient alternative to a Bloom filter, using 1.13 MB for 1,000,000 items at a 0.39% false positive rate versus 1.51 MB for a Bloom filter. UltraLogLog cuts HyperLogLog's memory by about 43% for the same error, trading slower adds, counts, and merges. A log-linear histogram estimates percentiles within 0.39% using about 14 KB, far smaller than storing raw values, and beats t-digest on long-tailed data. MinHash compares set similarity using fixed-size signatures, with unsure adding items 6 to 70 times faster than the dgryski implementation while using half the memory.

## Full article

daily.dev links to this article rather than hosting it. Read it at the original source: <https://antonz.org/probabilistic-data-structures-2>

## Questions this post answers

### How much memory does a binary fuse filter use compared to a Bloom filter for the same false positive rate?

A binary fuse filter for 1,000,000 items with a 0.39% false positive rate takes 1.13 MB using 9 bits per item, while a Bloom filter with the same false positive rate takes 1.51 MB at 12 bits per item. Unlike a Bloom filter, a binary fuse filter is static and built once from all items, trading the ability to add items later for lower memory use and faster, equally reliable lookups.

_Comparing space-efficient filters like this is easier with daily.dev when picking a data structure for a Go project._

### How much memory does UltraLogLog save compared to HyperLogLog for counting unique items?

UltraLogLog needs about 43% less memory than HyperLogLog for the same error rate. For example, a HyperLogLog sketch with 0.81% standard error takes 16 KB, while an UltraLogLog sketch with 0.86% error takes just 8 KB. The tradeoff is that adding, counting, and merging operations are slower than with HyperLogLog, since UltraLogLog uses each register's bits more efficiently (Otmar Ertl, 2024).

_Weighing memory versus speed tradeoffs like this is simpler when tracking new data structure designs on daily.dev._

### Why is a log-linear histogram more accurate than a t-digest for estimating high percentiles of latency data?

A log-linear histogram limits error in the estimated value itself, while a t-digest limits error in rank, which causes much larger value errors in long-tailed distributions. For an 8.5 KB t-digest on a Pareto distribution, the error at the 99.9th percentile reaches 67%, versus below 0.78% for a similarly sized (8 KB) log-linear histogram across lognormal, Pareto, and uniform distributions.

_Choosing the right quantile structure for latency data gets easier by following comparisons like this on daily.dev._

## Similar posts on daily.dev

- [Bloom Filters: Theory, Engineering Trade‑offs, and Implementation in Go](https://daily.dev/posts/bloom-filters-theory-engineering-trade-offs-and-implementation-in-go-cp65iybjt) · InfoQ · 1 upvotes · 0 comments
- [Bloom Filters Explained: The Probabilistic Data Structure Powering Instagram, Google, and High-Scale Systems](https://daily.dev/posts/bloom-filters-explained-the-probabilistic-data-structure-powering-instagram-google-and-high-scale-9sh61vl6v) · freeCodeCamp · 2 upvotes · 0 comments
- [Two Bits Are Better Than One: making bloom filters 2x more accurate](https://daily.dev/posts/two-bits-are-better-than-one-making-bloom-filters-2x-more-accurate-afbqkwq5f) · Hacker News · 0 upvotes · 0 comments
- [How We Increased Shannon Entropy Throughput in Go by 41% Using a Lookup Table.](https://daily.dev/posts/how-we-increased-shannon-entropy-throughput-in-go-by-41-using-a-lookup-table--qu11tyrhk) · Awesome Go · 1 upvotes · 0 comments

---

Tags: [#golang](https://daily.dev/tags/golang), [#data-structures](https://daily.dev/tags/data-structures)

[View this post on daily.dev](https://daily.dev/posts/probabilistic-data-structures-in-go-part-2-fo0jw59v9)

```json
{"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://daily.dev/#organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180},"sameAs":["https://twitter.com/dailydotdev","https://github.com/dailydotdev","https://www.linkedin.com/company/daily-dev-ltd"]},{"@type":"WebSite","@id":"https://daily.dev/#website","url":"https://daily.dev","name":"daily.dev","publisher":{"@id":"https://daily.dev/#organization"},"potentialAction":{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https://daily.dev/search?q={search_term_string}"},"query-input":"required name=search_term_string"}}]}
{"@context":"https://schema.org","@type":"TechArticle","headline":"Probabilistic data structures in Go, part 2","url":"https://daily.dev/posts/probabilistic-data-structures-in-go-part-2-fo0jw59v9","mainEntityOfPage":{"@type":"WebPage","@id":"https://daily.dev/posts/probabilistic-data-structures-in-go-part-2-fo0jw59v9"},"datePublished":"2026-11-21T13:01:45.948Z","dateModified":"2026-11-21T13:02:17.697Z","description":"This post covers four probabilistic data structures implemented in the Go package 'unsure': binary fuse filter, UltraLogLog, log-linear histogram, and MinHash....","image":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/7549117af8dc6617a0b0bb14568a91e4?_a=AQAEuop","thumbnailUrl":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/7549117af8dc6617a0b0bb14568a91e4?_a=AQAEuop","isAccessibleForFree":true,"articleSection":"Anton Zhiyanov","inLanguage":"en","publisher":{"@type":"Organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180}},"author":{"@type":"Organization","name":"Anton Zhiyanov","logo":"https://media.daily.dev/image/upload/t_logo,f_auto/v1/logos/29aa129ca24545f1a698d8a206ccc372","url":"https://daily.dev/sources/antonz"},"commentCount":0,"discussionUrl":"https://daily.dev/posts/probabilistic-data-structures-in-go-part-2-fo0jw59v9","interactionStatistic":[{"@type":"InteractionCounter","interactionType":{"@type":"LikeAction"},"userInteractionCount":14},{"@type":"InteractionCounter","interactionType":{"@type":"CommentAction"},"userInteractionCount":0}],"keywords":"golang,data-structures","timeRequired":"PT22M"}
{"@context":"https://schema.org","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https://daily.dev"},{"@type":"ListItem","position":2,"name":"Anton Zhiyanov","item":"https://daily.dev/sources/antonz"},{"@type":"ListItem","position":3,"name":"Probabilistic data structures in Go, part 2"}]}
{"@context":"https://schema.org","@type":"FAQPage","@id":"https://daily.dev/posts/probabilistic-data-structures-in-go-part-2-fo0jw59v9#faq","mainEntity":[{"@type":"Question","name":"How much memory does a binary fuse filter use compared to a Bloom filter for the same false positive rate?","acceptedAnswer":{"@type":"Answer","text":"A binary fuse filter for 1,000,000 items with a 0.39% false positive rate takes 1.13 MB using 9 bits per item, while a Bloom filter with the same false positive rate takes 1.51 MB at 12 bits per item. Unlike a Bloom filter, a binary fuse filter is static and built once from all items, trading the ability to add items later for lower memory use and faster, equally reliable lookups. Comparing space-efficient filters like this is easier with daily.dev when picking a data structure for a Go project."}},{"@type":"Question","name":"How much memory does UltraLogLog save compared to HyperLogLog for counting unique items?","acceptedAnswer":{"@type":"Answer","text":"UltraLogLog needs about 43% less memory than HyperLogLog for the same error rate. For example, a HyperLogLog sketch with 0.81% standard error takes 16 KB, while an UltraLogLog sketch with 0.86% error takes just 8 KB. The tradeoff is that adding, counting, and merging operations are slower than with HyperLogLog, since UltraLogLog uses each register's bits more efficiently (Otmar Ertl, 2024). Weighing memory versus speed tradeoffs like this is simpler when tracking new data structure designs on daily.dev."}},{"@type":"Question","name":"Why is a log-linear histogram more accurate than a t-digest for estimating high percentiles of latency data?","acceptedAnswer":{"@type":"Answer","text":"A log-linear histogram limits error in the estimated value itself, while a t-digest limits error in rank, which causes much larger value errors in long-tailed distributions. For an 8.5 KB t-digest on a Pareto distribution, the error at the 99.9th percentile reaches 67%, versus below 0.78% for a similarly sized (8 KB) log-linear histogram across lognormal, Pareto, and uniform distributions. Choosing the right quantile structure for latency data gets easier by following comparisons like this on daily.dev."}}]}
```

