Go 语言中的概率数据结构

概率数据结构会针对其处理的数据所涉及的问题给出近似答案。集合是否包含某个条目？集合中有多少个不重复条目？哪些条目出现得最频繁？与集合和频率表这类确定性结构不同，这些答案可能并不精确，但作为回报，你可以大幅减少内存占用。

在这篇文章中，我们将讨论什么是概率数据结构、它们如何工作，以及它们提供哪些类型的保证。我还会介绍 unsure —— 一个在 Go 中实现这些结构的包。它很简单（每个数据结构的核心逻辑为 100–300 LOC），很快（通常比其他实现快数倍），并且除了标准库外没有依赖。

布隆过滤器 • Count-min sketch • HyperLogLog • T-digest • Top-k

# 布隆过滤器

布隆过滤器是一种用确定性换取空间的集合。它可以告诉你某个条目肯定不在集合中，或者很可能在集合中（这可能是假阳性）。过滤器实际上不存储条目，因此比常规集合紧凑得多。

例如，一个包含 1,000,000 个不同的 8 字节字符串的常规集合大约占用 64 MB。对于相同的字符串，假阳性率为 1% 的布隆过滤器只使用 1.24 MB（每个条目约 10 位）——小了 50 倍。过滤器的大小不取决于条目大小，因此字符串越长，差异会更大。

布隆过滤器通常驻留在内存中，有助于尽量减少昂贵的 I/O 操作，例如磁盘读取或网络调用。你检查某个条目是否在过滤器中，如果答案为“否”，就跳过昂贵的查找。如果答案为“是”，你仍然必须执行查找，因为这可能是假阳性。

        // A filter for 1000 items with a 1% false positive rate.
filter := bloom.New(1000, 0.01)

filter.Add([]byte("alice"))
filter.Add([]byte("bob"))

filter.Contains([]byte("alice")) // true
filter.Contains([]byte("carol")) // false (or, rarely, true)
      

过滤器按给定条目数和给定假阳性率确定大小。你可以添加更多条目，但假阳性率会上升。

你可以向布隆过滤器添加条目并检查条目是否在过滤器中，但不能删除条目、统计条目数量，或遍历它们。

工作原理

Bloom filter1 是一个由 m 个位组成的大数组，最初全部置零。要添加一个条目，你为它计算 k 个哈希值，并将这些位置上的 k 个位设置为 1：

        ┌──────┐                       ┌───────┐
item ──►│ hash │──► h1, h2, ..., hk ──►│ mod m │──► i1, i2, ..., ik
        └──────┘                       └───────┘

i1          i2                  ik
┌───┬───┬─▼─┬───┬───┬─▼─┬───┬───┬───┬───┬─▼─┬───┐
│ 0 │ 0 │ 1 │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │ 1 │ 0 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
  0   1   2                                  m-1
      

要检查某个条目是否在过滤器中，你计算相同的 k 个哈希值，并检查这 k 个位是否都已置位：

• 如果其中任一位未置位，则该条目肯定从未被添加过。

• 如果所有位都已置位，则该条目很可能被添加过，但并不保证（这些位可能由其他条目置位）。

        i1          i2                  ik
┌───┬───┬─▼─┬───┬───┬─▼─┬───┬───┬───┬───┬─▼─┬───┐
│ 1 │ 0 │ 1 │ 0 │ 0 │ 1 │ 1 │ 0 │ 1 │ 0

Unsure 使用分块 Bloom filter2。位数组被划分为 512 位的块，每个块与一条 CPU 缓存行的大小相匹配。添加或检查一个元素时，它只被哈希一次：哈希的一部分用于选择块，其余部分用于选择该块内的 k 个位。每次添加或检查只访问一条缓存行，因此即使过滤器非常大，它也能保持很快。

      

┌──────┐ ┌──► high 32 bits ──► block item ──►│ hash │──► h ───┤ ┌─────────┐ └──────┘ └──► low 32 bits ──►│ × salts │──► i1, i2, ..., ik └─────────┘

block ┌───────┬───▼───┬───────┬───────┬───────┬───────┐ │ 0 │ 1 │ 2 │ 3

sketch.Count([]byte("alice")) // 3（或极少数情况下更高） sketch.Count([]byte("bob")) // 1（或极少数情况下更高） sketch.Count([]byte("carol")) // 0（或极少数情况下更高） sketch.Total() // 4

        
该 sketch 使用两个设置：epsilon ε 和 delta δ。如果某个给定项的实际计数为 X，而所有计数的总和为 N，那么该项的估计计数通常介于 X 与 X+ε·N 之间。但极少数情况下（概率为 δ），估计值可能更高。

例如，若 ε 为 0.001，δ 为 0.01，N 为 100 万，那么估计值偏差最多可达 1,000（ε·N），概率至少为 99%（1−δ）；偏差超过 1,000 的概率至多为 1%（δ）。

sketch 中的计数误差取决于所有计数的总和，而非每个单独项。因此，频繁出现的项相对于其计数而言估计得较为准确，而稀有项则不然——对它们来说绝对误差过高。

你可以增加 sketch 中各项的计数器，并获得某项的估计计数，但无法减少计数器或遍历各项。

## 工作原理

Count-min sketch8 是一张计数器表，有 d 行 w 列，全部从零开始。每一行使用自己的哈希函数，将项映射到 w 个计数器之一。要添加一项，就在每一行中递增其对应的计数器：

      

┌──────┐ ┌───────┐ item ──►│ hash │──► h1, h2, ..., hd ──►│ mod w │──► i1, i2, ..., id └──────┘ └───────┘

┌───┬───┬─▼─┬───┬───┬───┬───┬───┬───┬───┐ row 1 │ 0 │ 2 │ 4 │ 0 │ 1 │ 0 │ 0 │ 3 │ 0 │ 1 │ 4 → 5 ├───┼───┼───┼───┼───┼───┼─▼─┼───┼───┼───┤ row 2 │ 1 │ 0 │ 0 │ 0 │ 2 │ 0 │ 3 │ 0 │ 1 │ 0 │ 3 → 4 ├───┼───┼───┼───┼───┼───┼───┼───┼─▼─┼───┤ row d │ 0 │ 1 │ 0 │ 2 │ 0 │ 0 │ 1 │ 0 │ 5 │ 0 │ 5 → 6 └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘ i1 i2 id

        
要估计某项的计数，就取其 d 个计数器中的最小值：

- 其他项可能哈希到同一个计数器，因此每个计数器值 ≥ 真实计数。

- 最小的计数器是碰撞最少的那个，因此它是最佳估计。

      

┌───┬───┬─▼─┬───┬───┬───┬───┬───┬───┬───┐ row 1 │ 0 │ 2 │ 4 │ 0 │ 1 │ 0 │ 0 │ 3 │ 0 │ 1 │ 4 ├───┼───┼───┼───┼───┼───┼─▼─┼───┼───┼───┤ row 2 │ 1 │ 0 │ 0 │ 0 │ 2 │ 0 │ 3 │ 0 │ 1 │ 0 │ 3 ├───┼───┼───┼───┼───┼───┼───┼───┼─▼─┼───┤ row d │ 0 │ 1 │ 0 │ 2 │ 0 │ 0 │ 1 │ 0 │ 5 │ 0 │ 5 min = 3 └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

        
当 w = e/ε 列时，每个计数器的误差最多为 ε·N，概率至少为 1 − 1/e。若使用 d = ln(1/δ) 行，则该项的 d 个计数器全部超出其真实计数 ε·N 以上的概率 ≤ δ。

Unsure 使用保守更新。当你向某项添加 n 时，它首先找到当前估计值 E（最小的计数器），然后只增加那些低于 E+n 的计数器，较大的保持不变。这保持了相同的精度保证，但实际误差约降低 2 倍。代价是计数无法减少。

      

┌───┬───┬─▼─┬───┬───┬───┬───┬───┬───┬───┐ row 1 │ 0 │ 2 │ 4 │ 0 │ 1 │ 0 │ 0 │ 3 │ 0 │ 1 │ 4 → 4 ├───┼───┼───┼───┼───┼───┼─▼─┼───┼───┼───┤ row 2 │ 1 │ 0 │ 0 │ 0 │ 2 │ 0 │ 3 │ 0 │ 1 │ 0 │ 3 → 4 ├───┼───┼───┼───┼───┼───┼───┼───┼─▼─┼───┤ row d │ 0 │ 1 │ 0 │ 2 │ 0 │ 0 │ 1 │ 0 │ 5 │ 0 │ 5 → 5 └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

        
计数器为 32 位，而非通常的 64 位，因此该 sketch 使用的内存减少 2 倍。项只哈希一次，每一行通过加盐（乘以每行一个随机常量）从该哈希中获得自己的位置。

      

┌──────┐ ┌─────────┐ item ──►│ hash │──► h ──►│ × salts │──► i1, i2, ..., id └──────┘ └─────────┘

该 sketch 使用 wyhash 进行哈希。

基准测试

以下是完整基准测试9的摘录，将 unsure 与 BoomFilters10（一个带有 64 位计数器的经典 count-min sketch）进行比较（ns/op，越低越好）：

在 ε=0.0001、对 1M 个不同项进行 10M 次添加时的准确性，平均高估量（越低越好）：

Unsure 在添加操作上约快 1.5×，在计数操作上约快 4×，使用的内存少 2×，误差低 2–2.7×。

# HyperLogLog

HyperLogLog 是一种用准确性换取空间的唯一项计数器。它能告诉你它大约见过多少个不同项，无论每个项出现了多少次。HyperLogLog（下文也称 sketch）并不实际存储这些项，因此比常规集合紧凑得多。

例如，一个包含 1,000,000 个不同 8 字节字符串的常规集合大约占用 64 MB。一个 HyperLogLog sketch 以约 0.8% 的误差统计同样的字符串，仅使用 16 KB——几乎小了 4,000 倍。sketch 的大小不取决于项的数量或大小，只取决于你选择的准确性。一个 16 KB 的 sketch 统计十亿项与统计一千项一样准确。

当你需要在大规模流中统计唯一事物时，HyperLogLog 很有用：网站的独立访客、每天的独立搜索查询，或数据库某一列中的不同值。

// Standard error about 0.8% of the true count. sketch := hll.New()

sketch.Add([]byte("alice")) sketch.Add([]byte("bob")) sketch.Add([]byte("alice")) sketch.Add([]byte("carol"))

sketch.Count() // 3 (approximately)

        
你可以合并 sketch，以汇总来自多台机器或分片（比如按小时、页面或地区）的数据。当你合并两个 sketch 时，你会得到两者唯一项的总数，而不会重复计算共享项。

      

home := hll.New() // visitors to the home page docs := hll.New() // visitors to the docs // ... home.Merge(docs) home.Count() // visitors to either page

计数是通过将所有寄存器合在一起、使用 2^register 的调和平均来估计的。标准误差约为 1.04/√m。合并两个 sketch 只是取每对寄存器中的最大值。

原始估计器在处理小计数（最多为 m 的几倍）时是有偏的，因此在这些情况下它使用一个不同的公式，称为线性计数。这种切换会造成误差的突然变化，一些实现（如 HyperLogLog++12）通过使用基于真实数据的大型偏差校正表来解决这个问题。

Unsure 使用 Otmar Ertl13 改进的估计器。它不采用寄存器的调和平均，而是基于直方图工作：有多少个寄存器的值为 0、值为 1，等等。对直方图应用一个公式，就能对从零到数十亿的任意数量的元素给出准确估计，因此不需要为小计数单独使用公式，也不需要校正表。

每当寄存器发生变化时，该 sketch 就会更新直方图。大多数添加操作不会改变任何寄存器，因此这几乎没有开销。无论 sketch 有多大，计数总是花费相同的时间。其他实现会在每次计数时扫描所有寄存器，这需要从微秒到毫秒的时间。

每个寄存器为一个字节，直方图有 64 个四字节计数器（256 字节）。元素使用 wyhash 哈希一次，64 位哈希被拆分为寄存器索引和 rank。

基准测试

以下是完整基准测试14的摘录，将 unsure 与 axiom15（使用 LogLog-Beta 估计器和稀疏模式的 HyperLogLog）进行比较（ns/op，越低越好）：

p=14 时的准确度（标准误差 0.81%），100 个 sketch 上的相对 RMSE（越低越好）：

添加给定数量的不同项后，p=14 时的内存（越低越好）：

unsure 的添加速度与 axiom 大致相同，计数速度快 270–83,000 倍，合并速度快 2.3–2.9 倍，并且在计数高于寄存器数量时具有相同的准确度和内存占用。当元素数量少于寄存器数量时，axiom 的稀疏模式使其更准确、更紧凑。

# T-digest

t-digest 是对数字流的摘要，以准确度换取空间。它可以给出数据的近似中位数、第 99 百分位数或任何其他分位数。它还可以估计低于某个值的数字所占比例（CDF）。该 digest 实际上并不存储这些数字，因此它比排序列表紧凑得多。

例如，要找到 1,000,000 个数字的精确第 99 百分位数，你必须保留所有数字。使用 64 位浮点数，这需要 8 MB。t-digest 仅使用 8 KB 就能将同一分位数估计到秩的约 0.03% 以内（在第 98.97 百分位数和第 99.03 百分位数之间）——小 1,000 倍。digest 的大小不取决于值的数量，只取决于你选择的准确度。8 KB 的 digest 概括十亿个值和概括一百万个值一样好。

当你需要在大规模流上计算分位数时，t-digest 很有用：服务的延迟百分位数、请求大小或价格的分布，或传感器数据中的离群值阈值。

        // Response times in milliseconds.
digest := tdigest.New()

digest.Add(12.5)
digest.Add(8.1)
digest.Add(130.0)
// ...

digest.Quantile(0.5)  // median
digest.Quantile(0.99) // 99th percentile
digest.CDF(100)       // fraction of responses faster than 100 ms
      

文章标题：Go 中的概率数据结构

正文： 你可以合并 digest，从多台机器或分段（比如按小时、按端点、按区域）中汇总数据。合并后的 digest 会估计所有值的百分位数，但精度不如各个单独的 digest。

        east := tdigest.New() // 一台服务器上的延迟
west := tdigest.New() // 另一台服务器上的延迟
// ...
east.Merge(west)
east.Quantile(0.99) // 两台服务器合起来的 99 分位数
      

digest 只有一个设置：压缩参数 δ，它把 centroid（见下文“工作原理”）的数量限制在 δ+2。常见的默认值是 δ=100，占用 8 KB。增大 δ 会占用更多内存，但能降低估计误差。

误差以秩来衡量：在分位数 q=0.99 处的秩误差为 0.03%，意味着 Quantile(0.99) 返回的值落在实际值的第 98.97 到 99.03 百分位之间的某处。尾部估计，例如 q=0.99 或 q=0.999，比中位数（q=0.5）更准确。

你可以向 digest 添加数字、估计分位数和 CDF，以及合并 digest。你不能删除数字或列出数字。

工作原理

T-digest16 把数字汇总成一个有序的 centroid 列表。每个 centroid 有一个均值和权重——权重表示它代表的值的个数。要估计分位数，digest 会找到请求的秩附近的 centroid，并在它们的均值之间插值。

诀窍在于允许 centroid 增长到多大。缩放函数 k(q) 把分位数 q 映射到 -δ/4 到 δ/4 之间的一个数，每个 centroid 只能跨越 1 个单位的 k：如果一个 centroid 覆盖从 q₁ 到 q₂ 的分位数，那么 k(q₂) − k(q₁) ≤ 1。

反正弦缩放函数 k(q) = δ/(2π)·asin(2q-1) 在 q=0 和 q=1 附近陡峭，在中位数附近平缓。这意味着它产生的 centroid 在中间更大、在两端更小：

        weight
  │                ┌──┐
  │             ┌──┤  ├──┐
  │          ┌──┤  │  │  ├──┐
  │       ┌──┤  │  │  │  │  ├──┐
  │  ┌─┬──┤  │  │  │  │  │  │  ├──┬─┐
  └──┴─┴──┴──┴──┴──┴──┴──┴──┴──┴──┴─┴──► value
    min      q=0.25   median  q=0.75     max
      

在 1M 个值和 δ=100 的情况下，中位数附近的 centroid 每个大约容纳 27,000 个值，第 99 百分位附近的每个大约 5,000 个，最外侧的每个大约 500 个。这使得尾部附近的误差保持较小。

Unsure 是 Dunning 和 Ertl 论文中的可合并 t-digest。新值进入一个容量为 5·δ 个数字的缓冲区。当缓冲区满时，digest 对其排序，并在一次遍历中把它与（已经有序的）centroid 合并，只要每个新 centroid 落在其 k 的跨度内，就从左到右构建新的 centroid。每隔一次遍历改为从右到左，这样两侧尾部都不会得到更满的 centroid。Quantile、CDF 和 Merge 会先清空缓冲区。

centroid 保存在两个固定数组中，每个数组有 δ+2 个条目（当前列表和正在构建的下一个列表），另外还保存累积权重，供 Quantile 和 CDF 中的二分查找使用。在 δ=100 时，centroid 占用 16·102·2 + 8·103 字节，缓冲区占用 8·500 字节，总共约 8 KB。

权重为 1 的 centroid 被当作精确值处理，而不是围绕其均值展开，并且两端使用精确的最小值和最大值。因此，值很少的 digest 会给出精确结果，且 Quantile(0) 和 Quantile(1) 总是精确的。

基准测试

以下是完整基准测试17 的摘录，将 unsure 与 influxdata18（使用相同缩放函数的可合并 t-digest）进行比较（ns/op，越低越好）：

δ=100 时的准确度，1M 个正态值上的平均秩误差（越低越好）：

在 δ=100 时的内存（越低越好）：unsure 8.5 KB，influxdata 14.4 KB。

Unsure 添加值的速度约为 influxdata 的 1.8×，查询速度相同，合并速度快 7–9×，并在准确率大致相同的情况下少用 40% 内存。

# Top-k 草图

Top-k 草图用于找出流中出现频率最高的 k 个项（“高频项”），并给出它们的近似计数。它只根据 k 使用固定数量的内存，无论流中有多少不同的项。

要找出精确的顶部项，就必须统计每个唯一项，例如用一个逐项计数映射。面对数百万个不同项，这会占用几十或几百 MB。针对前 1000 个项的 Top-k 草图大约占用 360 KB，而且通常能全部找到。

当你想要识别“最热”的数据时，Top-k 草图很有用：请求最多的 URL、最活跃的用户，或最常见的搜索查询。与 count-min 草图不同，它会保留实际项，因此可以把它们列出来。

        // Track the 2 most frequent items.
sketch := topk.New(2)

sketch.Add([]byte("alice"))
sketch.Add([]byte("bob"))
sketch.Add([]byte("carol"))
sketch.AddN([]byte("alice"), 4)
sketch.AddN([]byte("carol"), 2)

sketch.Top()                  // [{alice 5} {carol 3}]
sketch.Count([]byte("alice")) // 5
sketch.Count([]byte("bob"))   // 0 (not in the top 2)
sketch.Total()                // 9
      

Top 最多返回 k 个项，从出现最频繁到最不频繁。计数是估计值：对于最频繁的项，它们通常精确；但对于不太常见的项，可能略低于实际计数。

当流是偏斜的，即少数项出现的频率远高于其他项时，该草图效果最好。这在现实情况中很常见。如果所有项的频率大致相同，就没有明确的前 k 个，结果会变得不那么准确。

你可以向草图添加项，并获取顶部项及其计数，但不能减少计数，也不能检查不在前 k 个中的项。

工作原理

HeavyKeeper19 是一个用于估计项计数的桶表。它有 d 行和 w 列，每个项在每一行映射到一个桶。每个桶保存该项的一个指纹和一个计数。要添加项，需要更新它在每一行中的桶：

• 如果桶为空或归该项所有，则增加其计数。

• 如果桶归另一个项所有，则对其进行衰减：以 b^count 的概率将其计数减 1（b < 1）。当计数达到 0 时，新项接管该桶，计数为 1。

        ┌──────┐
add x ──► │ hash │──► h ──► high 32 bits ──► fingerprint = 7
          └──────┘    │
                      │ map to buckets
                   ┌──┴────────────┐
       ┌───────┬───▼───┬───────┬───│───┬───────┐
row 1  │       │ fp=7  │ fp=3  │   │   │ fp=5  │  column 2 is owned by x:
       │       │  41   │   2   │   │   │  980  │  41 → 42
       ├───────┼───────┼───────┼───▼───┼───────┤
row 2  │ fp=9  │       │       │ fp=2  │ fp=4  │  column 4 is owned by another:
       │  17   │       │       │   3   │   1   │  3 → 2 with probability b^3
       └───────┴───────┴───────┴───────┴───────┘
         col 1   col 2   col 3   col 4   col 5
      

该项的估计计数是它的各个桶中最大的计数。频繁项会很快达到使衰减几乎不可能发生的计数，因此它们会保住自己的桶。稀有项会不断互相替换，而不影响频繁项。一个在流中较晚才变得频繁的项，仍然可能超过一个不那么频繁的拥有者，并接管其桶。

在表旁边，sketch 维护一个最小堆，保存到目前为止估计值最大的 k 个项。某项的桶更新后，如果它的估计值大于堆中最小的计数，就把该项加入堆，并移除最小的项。如果该项已在堆中，则增加它的计数。

        ┌───────────┐
add x (15) ───────►│ bob    12 │  the root has the smallest count
                   └─────┬─────┘
              ┌──────────┴────────┐
        ┌─────┴─────┐       ┌─────┴─────┐
        │ alice  30 │       │ dave   14 │  15 > 12: x replaces bob at the root
        └─────┬─────┘       └───────────┘  15 > 14: x moves down, dave moves up
      ┌───────┴──────┐
┌─────┴─────┐  ┌─────┴─────┐
│ eve   980 │  │ fay    41 │
└───────────┘  └───────────┘
      

Unsure 使用 d = 2 行、每行 max(16k, 256) 个桶，衰减基数 b = 0.8。概率 b^count 预计算为 64 位阈值，因此衰减开销很低：如果随机数低于第 c 个阈值，计数 c 就减一。

原始 HeavyKeeper 使用 b = 1.08⁻¹ ≈ 0.93，并且行数更多。较小的 b 能让频繁项更快锁定它们的桶，从而使 sketch 在平坦流上更精确。然而，如果 b 太小（比如 0.5），最先占据桶的项会永久保留它们，因此后来才变得频繁的项永远不会被计数，即使它们最终是最频繁的。使用 b = 0.8 保留了大部分精度，同时仍能捕获大多数后来出现的频繁项。至于行数，两行足以保护频繁项免受单行内碰撞的影响，增加更多行只会让 sketch 变慢。

项只哈希一次。哈希通过加盐（乘以每行一个随机常数）映射到每一行中的一个位置。指纹是哈希的高 32 位。堆使用 64 位哈希来标识项，因此不比较实际的项字节。

每个桶为 8 字节（一个 32 位指纹和一个 32 位计数），因此表占用 256·k 字节。堆每个项约占 100 字节，再加上项本身。

该 sketch 使用 wyhash 进行哈希，使用 wyrand 生成随机数。

基准测试

以下是完整基准测试20 的摘录，比较 unsure 与 keiler21（HeavyKeeper，b = 0.9 且 d = ln k）和 dgryski22（Filtered Space-Saving23）在 Zipf s=0.8 流上的表现（time/op，越低越好）：

精度是报告的前 k 个中位于真实前 k 个的比例（越高越好）：

计数误差是对报告项取 |估计值 − 真实值| / 真实值的均值（越低越好）：

Unsure 在 Add 上比其他实现快 2–4×，在 Top 上快 1.8–4×。在平坦流（s=0.6）上，它以 90–97% 的精度找到真实前 k 个，而 keiler 的精度降到 38–70%，计数误差为 62–94%，dgryski 则降到 19–52%，计数高出 18× 或更多。在偏斜流（s=1.0）上，三者的准确度大致相同。

# 总结

Go 中的概率数据结构

作为工程师，我们通常希望从数据中得到精确的答案。但有时，允许一点点不确定性，就能把内存占用降低十倍、百倍甚至千倍。概率数据结构正是为此而生：

• Bloom filter 用来检查某个元素是否可能存在于一个集合中。

• Count-min sketch 用来估计每个元素出现了多少次。

• HyperLogLog 用来估计不同元素的数量。

• T-digest 用来估计一串数字的分位数。

• Top-k sketch 用来找出数据流中出现最频繁的元素。

要在 Go 中使用它们，可以试试 nalgeon/unsure 包：

        go get github.com/nalgeon/unsure
      

• 《Space/time trade-offs in hash coding with allowable errors》，Burton H. Bloom，1970 年。 ↩︎

• 《Cache-, hash-, and space-efficient Bloom filters》，Felix Putze 等，2009 年。 ↩︎

• wyhash 参考实现，作者 Wang Yi。 ↩︎

• xxHash 参考实现，作者 Yann Collet。 ↩︎

• Bloom filter 基准测试。 ↩︎

• bits-and-blooms/bloom，作者 Daniel Lemire。 ↩︎

• jcalabro/gloom，作者 Jim Calabro。 ↩︎

• 《An improved data stream summary: the count-min sketch and its applications》，Graham Cormode 与 S. Muthikrishnan，2005 年。 ↩︎

• Count-min sketch 基准测试。 ↩︎

• tylertreat/BoomFilters，作者 Tyler Treat。 ↩︎

• 《HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm》，Philippe Flajolet 等，2007 年。 ↩︎

• 《HyperLogLog in practice》，Stefan Heuleet 等，2013 年。 ↩︎

• 《New cardinality estimation algorithms for HyperLogLog sketches》，Otmar Ertl，2017 年。 ↩︎

• HyperLogLog 基准测试。 ↩︎

• axiomhq/hyperloglog，作者 Axiom。 ↩︎

• 《Computing extremely accurate quantiles using t-digests》，Ted Dunning 与 Otmar Ertl，2019 年。 ↩︎

• T-digest 基准测试。 ↩︎

• influxdata/tdigest，作者 InfluxData。 ↩︎

• 《HeavyKeeper: An Accurate Algorithm for Finding Top-k Elephant Flows》，Junzhi Gong 等，2018 年。 ↩︎

• Top-k 基准测试。 ↩︎

• keilerkonzept/topk，作者 KEILERKONZEPT。 ↩︎

• dgryski/go-topk，作者 Damian Gryski。 ↩︎

• 《Efficient Computation of Frequent and Top-k Elements in Data Streams》，Ahmed Metwally 等，2005 年。 ↩︎

★ 订阅以跟进新文章。