Newshot

Go 语言中的概率数据结构,第二部分

Translation(model translation, not the source's own text)

文章标题:Go 中的概率数据结构,第 2 部分

正文: 概率数据结构让你能针对其处理的数据给出近似答案。集合是否包含某个元素?集合中有多少个不重复元素?一串数字中的第 99 百分位数是多少?两个集合有多相似?与确定性结构不同,这些答案可能不精确,但作为交换,你可以节省大量内存。

之前,我们回顾了以下数据结构:Bloom filter(用于检查元素是否在集合中)、Count-min sketch(用于计数元素)、HyperLogLog(用于统计不重复元素数量)、T-digest(用于求分位数)以及 Top-k(用于找出最频繁的元素)。

在本篇文章中,我们将讨论其他概率结构,并将它们与我们已经介绍过的结构进行比较。我们会了解它们的工作原理以及它们提供何种保证。

所有示例都使用 unsure —— 一个在 Go 中实现这些结构的包。

Binary fuse filter • UltraLogLog • Log-linear histogram • MinHash

Binary fuse filter

binary fuse filter 是一种用确定性换取空间的集合,就像 Bloom filter1 一样。它可以告诉你某个元素肯定不在集合中,或者可能在集合中(这可能是误报)。该 filter 不存储元素本身,因此比常规集合紧凑得多。

与 Bloom filter 不同,binary fuse filter 是静态的:你从所有元素一次性构建它,之后无法再添加。作为交换,在相同误报率下,它比 Bloom filter 使用更少的内存。例如,一个针对 1,000,000 个元素、误报率为 0.39% 的 fuse filter 占用 1.13 MB(每个元素 9 位),而 Bloom filter 占用 1.51 MB(每个元素 12 位)。

这使得 binary fuse filter 非常适合一次写入、多次读取的数据,例如数据库中不可变文件的键集合(用于跳过不包含该键的文件),或者已知不良元素的列表,例如泄露的密码或恶意 URL。


        items := [][]byte{[]byte("alice"), []byte("bob")}

// An 8-bit filter: 0.39% false positive rate.
filter := fuse.New[uint8](slices.Values(items), len(items))

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

指纹类型(New[T] 中的 T)决定了误报率和内存使用:

类型误报率每个元素的位数
uint80.39%9
uint160.0015%18
uint322.3e-1036

构造函数接受一个待添加到 filter 的元素迭代器以及预期元素数量(未知时为 0)。该数字仅用于预分配内存,因此良好的估计能让构建更快。

你可以检查某个元素是否在 filter 中,但不能添加或删除元素、统计元素数量或遍历它们。

工作原理

该 filter2 是一个由 b 位指纹组成的数组(例如,对于 uint8,b = 8)。每个元素被哈希为一个 64 位值 h,由此得到该元素的指纹 f(由 h 计算出的 b 位)以及数组中的三个位置(单元)。数组的填充使得对于每个元素,其各单元的 XOR 等于 f。


        ┌──────┐               ┌──► f  (b bits)
item ──►│ hash │──► h ─────────┤
        └──────┘               └──► i0, i1, i2

i0          i1          i2
┌───┬───┬──▼──┬───┬───┬──▼──┬───┬──▼──┬───┐
│   │   │ F0  │   │   │ F1  │   │ F2  │   │   F0 ^ F1 ^ F2 == f
└───┴───┴─────┴───┴───┴─────┴───┴─────┴───┘
      

要检查某个元素,你计算 h,查找它的三个单元,并将它们的 XOR 与 f 比较。对于集合中的元素,它们总是匹配。对于任何其他元素,XOR 是一个随机的 b 位值,以 2^-b 的概率与 f 匹配。

每次检查读取三个单元,因此对于大型 filter 来说,就是三次缓存未命中,而分块 Bloom filter 只有一次。不过,由于这些读取相互独立,CPU 可以并发执行它们,因此检查速度与 Bloom filter 大致相当。

文章标题:Go 中的概率数据结构,第 2 部分

正文: 该过滤器使用本地 wyhash3 实现进行哈希。它的性能与 xxh34 大致相同,但实现要简单得多,没有 SIMD 或汇编。

基准测试

以下摘自完整基准测试5,比较 unsure 与 xorfilter6(论文作者的 binary fuse 实现)以及 bloom(unsure 自带的 Bloom 过滤器),均使用 8 位指纹(ns/op,越低越好):

操作元素数unsurexorfilterbloom
构建(每元素)10K232513
1M303112
查询10K6.28.09.3
1M7.09.310.2
50M394240

内存,每元素位数(越低越好):

元素数指纹unsurexorfilterbloom
100K8-bit9.509.5012.45
10M8-bit9.029.0212.10
10M16-bit18.0418.0427.99

Unsure 与 xorfilter 大小相同(布局相同),查询速度最多快 25%。与 Bloom 过滤器相比,它最多节省 36% 的内存,查询速度相当或更快,但构建速度最多慢 2.5 倍。

  • Bloom 过滤器概述及其工作原理。 ↩︎
  • Thomas Mueller Graf 和 Daniel Lemire 的 Binary Fuse Filters 论文,2022 年。 ↩︎
  • Wang Yi 的 wyhash 参考实现。 ↩︎
  • Yann Collet 的 xxHash 参考实现。 ↩︎
  • Binary fuse 过滤器基准测试。 ↩︎
  • Daniel Lemire 的 FastFilter/xorfilter。 ↩︎

UltraLogLog

UltraLogLog 是一种用精度换空间的唯一元素计数器,类似 HyperLogLog7。它告诉你它见过大约多少个不同元素,无论每个元素出现了多少次。UltraLogLog 不存储元素,因此比普通集合紧凑得多。

UltraLogLog 是一种较新的设计(Otmar Ertl,2024 年),更高效地利用空间:在相同误差下,它所需内存比 HyperLogLog 少约 43%。例如,标准误差为 0.81% 的 HyperLogLog sketch 占用 16 KB,而误差为 0.86% 的 UltraLogLog sketch 占用 8 KB。不过,添加、计数和合并比 HyperLogLog 慢。

UltraLogLog 的适用场景与 HyperLogLog 相同:统计唯一访客、唯一搜索查询,或数据库列中的不同值,可能跨多台机器或多个分段。


        // 标准误差约为真实计数的 0.9%。
sketch := ull.New()

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

sketch.Count() // 3(近似值)
      

你可以合并 sketch 以获得所有 sketch 中唯一元素的总数,而不会重复计算共享元素。


        home := ull.New() // 首页访客
docs := ull.New() // 文档页访客
// ...
home.Merge(docs)
home.Count() // 任一页面的访客
      

该 sketch 有一个设置:精度 p,其相对标准误差为 0.782/√(2^p)。默认值为 p=13,误差 0.86%,占用 8 KB,接近常见的 HyperLogLog 默认值(0.81%,16 KB)。

你可以向 sketch 添加元素、获取估算计数,以及合并 sketch。你无法检查某个特定元素是否已添加、删除元素或列出元素。

工作原理

HyperLogLog 对每个元素做哈希,用哈希的前 p 位从 m = 2^p 个寄存器中选择一个。它计算 rank(哈希剩余部分的前导零个数加一),并将寄存器中见过的最大 rank 保留下来。看到 rank 为 k 意味着该寄存器中大约有 2^k 个元素。计数由所有寄存器共同估算得出。


        p 位
        ┌──────┐   ┌──────────┬────────────────────────┐
元素 ──►│ hash │──►│ 01101001 │ 0001101...             │
        └──────┘   └────┬─────┴───────────┬────────────┘
                        │ 寄存器 i         └ rank = 3 个零 + 1 = 4
          ┌───┬───┬───┬─▼─┬───┬───┬───┬───┬───┬───┐
寄存器    │ 3 │ 0 │ 5 │ 2 │ 1 │ 0 │ 4 │ 2 │ 0 │ 1 │  2 → 4
          └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
      

文章标题:Go 中的概率数据结构,第 2 部分

正文: HyperLogLog 的寄存器会丢失一些信息:它只记录最高值,而不记录是否出现过略低的值。这些较低值出现的频率至少与最高值一样高,因此它们能提供大量关于计数的信息。

UltraLogLog8 更高效地利用寄存器。每个寄存器仍然是一个字节,但它将最高秩 k 存储在高 6 位中,并将是否见过 k−1 和 k−2 存储在低 2 位中:


        k = 5        k-1 k-2
          ┌───────────────┬───┬───┐
register  │ 0 0 0 1 0 1   │ 1 │ 0 │  saw 5 and 4, but not 3
          └───────────────┴───┴───┘
          ┌───────────────┬───┬───┐
add k=6:  │ 0 0 0 1 1 0   │ 1 │ 1 │  saw 6, 5, 4
          └───────────────┴───┴───┘
      

计数估计使用 UltraLogLog 论文中的 FGRA 估计器。每个寄存器根据其值添加一个权重,计数被计算为权重之和的幂。几乎为空和几乎填满的草图会得到特殊处理,因此估计值从零到数十亿个项目都能保持准确,无需偏差表或针对小计数的单独公式。

Unsure 维护一个寄存器值的直方图(256 个四字节计数器,1 KB),并随寄存器变化而更新。这样,Count 读取直方图而不是扫描所有寄存器。Merge 每次检查 8 个寄存器,使用几个按位操作找出另一个草图会改变哪些寄存器,并且只更新那些。

项目使用 wyhash 哈希一次,64 位哈希被拆分为寄存器索引和秩。

基准测试

以下是完整基准测试9 的摘录,比较 UltraLogLog 与 unsure 自有的 HyperLogLog 和 axiom10(带有 LogLog-Beta 估计器和稀疏模式的 HyperLogLog)(ns/op,越低越好):

操作p大小ullhllaxiom
Add101 KB8.15.57.6
1416 KB8.05.77.7
18256 KB9.48.38.0
Count101 KB1656817,700
1416 KB16163348,000
18256 KB173574,650,000
Merge101 KB2,9007201,740
1416 KB51,20020,20058,500
18256 KB818,000341,000955,000

准确性和内存,1,000 个草图的相对 RMSE(越低越好):

不同项目数ull p=13hll p=14axiom p=14
1,0000.66%0.54%0.01%
40,0000.73%0.68%0.69%
1,000,0000.86%0.79%0.82%
内存9.1 KB16.3 KB16.1 KB

UltraLogLog 提供与 HyperLogLog 相同的准确性,但内存几乎只有一半。然而,添加、计数和合并明显更慢。

  • HyperLogLog 概述及其工作原理。↩︎
  • Otmar Ertl 的 UltraLogLog 论文,2024 年。↩︎
  • UltraLogLog 基准测试。↩︎
  • Axiom 的 axiomhq/hyperloglog。↩︎

对数线性直方图

对数线性直方图是数字流的一种摘要,以准确性换取空间。它可以给出近似中位数、99 百分位数或数据的任何其他分位数。它还可以估计低于某个值的数字比例(CDF)。直方图不存储数字本身,因此比排序列表紧凑得多。

例如,要找到 1,000,000 个响应时间的精确 99 百分位数,你必须保留所有响应时间。使用 64 位浮点数,这需要 8 MB。对数线性直方图使用约 14 KB 就能将同一百分位数估计在真实值的 0.39% 以内——少了近 600 倍。

误差相对于值本身:如果真实 99 百分位数为 200 ms,直方图返回的值在 199.2 到 200.8 ms 之间。这一保证适用于从最小值到最极端离群值的每个分位数。直方图的大小不取决于值的数量,只取决于你选择的准确性和值的范围宽度。

当你需要覆盖广泛范围的正值(如延迟、文件大小或价格)的百分位数时,对数线性直方图很有用。

文章标题:Go 中的概率数据结构,第 2 部分

正文:


        // Response times in milliseconds.
hist := loghist.New()

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

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

你可以合并直方图,以汇总来自多台机器或不同切分(比如按小时、按端点或按区域)的数据。合并是精确的:合并后的直方图与直接接收所有值的结果相同。


        east := loghist.New() // latencies on one server
west := loghist.New() // latencies on another
// ...
east.Merge(west)
east.Quantile(0.99) // 99th percentile across both servers
      

直方图有两个设置:相对误差和值范围。默认情况下,误差为 0.0039(0.39%),范围从 1e-9 到 1e18。降低误差或增大范围会占用更多内存。

你可以向直方图添加数字、估算分位数和 CDF,以及合并直方图。你不能删除数字或列出它们。

工作原理

直方图将值的范围划分为若干个桶,并统计每个桶中有多少个值。要估算分位数,它从最低的桶开始累加计数,直到达到所请求的排名,然后返回该桶中的一个值。估算的准确度取决于桶的宽度。

对于宽度相等的桶,比如 0–10、10–20 等等,每个估算值在桶中点附近的绝对误差都是 ±5。因此,对于较小的值,相对误差非常大;而对于较大的值,相对误差又小得没有必要:


        0       10      20      30     970     980     990     1000
├───────┼───────┼───────┼─ ··· ─┼───────┼───────┼───────┤
    └ 5 ± 5: ±100%                   995 ± 5: ±0.5% ┘
      

对数直方图通过让每个桶的宽度与其值成比例来解决这个问题。例如,如果桶的边界是 1.02 的幂(1、1.02、1.0404……),那么每个桶的末端比起点大 2%,因此桶中的任何值都在桶中点约 1% 的范围内。DDSketch11 使用了这种方法。缺点是,要为某个值找到正确的桶,就必须计算对数,而这相对较慢。

对数线性直方图用更廉价的数学运算得到几乎相同的结果。首先,它将值划分到 2 的幂之间的区间:1–2、2–4、4–8 等等(这些被称为 octave)。然后,它将每个 octave 划分为相同数量的等宽桶。例如,下面是三个 octave,每个有 4 个桶:


        1       2               4                               8
├─┬─┬─┬─┼───┬───┬───┬───┼───────┬───────┬───────┬───────┤
4 buckets   4 buckets               4 buckets
      

每个 octave 的长度是前一个的两倍,因此它的桶宽度也是前一个的两倍,桶宽度随值增长,就像在对数直方图中一样。找到正确的桶只需要几次位运算,而不需要计算对数。

HdrHistogram12 是最著名的对数线性直方图。它记录整数:一个数字最高位 1 的位置决定了它的 octave,接下来的几位决定了 octave 内的桶。

Unsure 适用于 float64 数字,并以类似于 HdrHistogram 的方式找到桶。

IEEE 754 双精度格式

Go(以及大多数其他语言)中的 float64 由三部分组成:

  • 一个 11 位的指数 e(存储为 1023 + e 以避免负值),
  • 以及一个 52 位的尾数 f。

该数字的值为 1.f × 2^e,其中 1.f 是介于 1 和 2 之间的二进制小数。

指数决定了 octave,从 2^e 到 2^(e+1)。尾数的前 m 位决定了 octave 内 2^m 个等宽桶中的一个。

例如,下面是数字 5.25,取 m=3(每个 octave 8 个桶)。用二进制表示,5.25 = 1.0101₂ × 2²,因此指数为 2(存储为 1025),尾数以 0101 开头:


        5.25 = 1.0101₂ × 2²

文章标题:Go 中的概率数据结构,第 2 部分

正文:
sign   exponent     top m   rest of the mantissa
┌───┬─────────────┬─────┬─────────────────────────┐
│ 0 │ 10000000001 │ 010 │ 1000000000 ... 00000000 │
└───┴──────┬──────┴──┬──┴──┬──────────────────────┘
           │         │     └── 被忽略
           │         └── 8 个桶中的第 2 个桶
           └── 1025 = 2 + 1023:阶 [4, 8)

4                               8
├───┬───┬───┬───┬───┬───┬───┬───┤
  0   1   2   3   4   5   6   7
          └ 5.25 落入第 2 个桶:[5, 5.5)
      

Add 会为给定的数字找到对应的桶并增加计数。Merge 会逐桶相加计数。Quantile 会从较近的一端(q ≤ 0.5 时从最左边的桶,否则从最右边的桶)开始累加计数,直到达到所需的排名。

尾数位数 m 由所要求的误差决定:构造函数会选择使最大误差不超过所要求误差的最小 m。默认值为 m=7:每个阶有 128 个桶,误差为 0.39%。

对数线性直方图 vs. t-digest

t-digest13 也能估计分位数,但它限制的是排名上的误差:Quantile(0.99) 返回的值,其排名接近 99%。对数线性直方图限制的是数值上的误差:Quantile(0.99) 返回的值接近真实的第 99 百分位数。

在数据的中部,两者相当相似。但在长尾中,相邻排名的数值可能差异很大,因此即使排名上的误差很小,也可能导致数值上的巨大差异。以下是 8.5 KB 的 t-digest(δ=100)在来自三种分布的 1M 个值上的平均相对误差:对数正态分布(与基准测试中相同)、α=1.5 的帕累托分布(尾部更长),以及 1,000,000 到 2,000,000 之间的均匀分布(无尾部):

分位数对数正态帕累托均匀
0.50.12%0.09%0.009%
0.991.7%5.6%0.015%
0.9998.7%67%0.009%
0.999983%868%0.004%

大小相近(1% 误差,8 KB)的对数线性直方图在所有这些情况下的误差都低于 0.78%。

因此,对于延迟、大小以及其他具有长尾的正值测量,对数线性直方图更合适。当你需要无论数值如何都保持固定大小,或者数值可能任意接近于零时,t-digest 更合适。

基准测试

以下是完整基准测试14 的摘录,比较了 unsure 与 hdr15(对数线性,仅整数,固定范围)和 dd16(DDSketch,对数桶),使用对数正态分布(ns/op,越低越好):

操作误差unsurehdrdd
Add1%4419
0.4%4419
0.1%4419
Quantile1%482831,750
0.4%901,7083,100
0.1%3371,71211,967
Merge1%33416,369302
0.4%657115,052808
0.1%3,249115,0182,862

在要求的 0.1% 误差下,对 1M 个值的平均相对误差(越低越好):

分位数unsurehdrdd
0.50.033%0.033%0.050%
0.990.038%0.037%0.048%
0.9990.027%0.019%0.039%
0.99990.016%0.002%0.025%

添加 1M 个值后的内存(越低越好):

误差unsurehdrdd
1%8 KB40 KB6 KB
0.4%14 KB264 KB13 KB
0.1%56 KB264 KB40 KB

Unsure 添加值的速度与 hdr 一样快,比 dd 快 5 倍;查询速度比 hdr 快 5–19 倍,比 dd 快约 35 倍;合并速度与 dd 差不多,比 hdr 快 35–175 倍。它比 hdr 略微不准确(内存用量少 5 倍),但比 dd 更准确(内存用量多 1.4 倍)。

  • Charles Masson 等人的 DDSketch 论文,2019 年。↩︎
  • Gil Tene 的 HdrHistogram。↩︎
  • T-digest 概述及工作原理。↩︎
  • 对数线性直方图基准测试。↩︎
  • Coda Hale 的 HdrHistogram/hdrhistogram-go。↩︎
  • Datadog 的 DataDog/sketches-go。↩︎

MinHash

文章标题:Go 中的概率数据结构,第 2 部分

正文: MinHash 用于估计两个集合的相似程度。它用一个短的固定大小的签名(例如 256 个数字)来概括每个集合。比较两个签名即可得到集合的近似 Jaccard 相似度:|A∩B| / |A∪B|,即两个集合共有的唯一元素所占的比例。

签名的大小不依赖于集合的大小,因此你可以仅通过比较 256 对数字来比较两个各含一百万个元素的集合,而不必逐一检查每个元素。此外,每个集合的签名只需计算一次,因此将大量集合相互比较的成本相对较低。

MinHash 可用于查找近似重复的文档,例如网页或文章(表示为词或 3 词短语的集合)。它也可用于查找相似的用户画像(表示为喜欢的物品的集合)或存在重叠的数据集(表示为键的集合)。


        // Two documents as sets of words.
strA := "the quick brown fox jumps over the lazy dog"
docA := minhash.New(256)
for w := range strings.FieldsSeq(strA) {
    docA.Add([]byte(w))
}

strB := "the quick brown cat jumps over the lazy dog"
docB := minhash.New(256)
for w := range strings.FieldsSeq(strB) {
    docB.Add([]byte(w))
}

sigA, sigB := docA.Signature(), docB.Signature()
sigA.Similarity(sigB) // 0.75 (true value 7/9 = 0.78)
      

MinHash 草图只有一个设置:签名大小 k,对于真实相似度 J,其标准误为 √(J(1−J)/k)。例如,当 k=256 且 J=0.5 时:

  • 68% 的估计值在 J 的 ±3.1 个百分点以内(0.47–0.53),
  • 95% 在 ±6.2 个百分点以内(2·stdErr),
  • 99.7% 在 ±9.4 个百分点以内(3·stdErr)。

你可以向草图中添加元素、合并草图,以及获取和比较签名。你无法检查某个特定元素是否已被添加、统计元素数量、删除元素或列出元素。

工作原理

经典 MinHash17 使用 k 个不同的哈希函数对每个元素进行哈希。这里有两个集合,A = {fox, cat, dog, owl} 和 B = {fox, dog, emu},以及它们在 k=4 时的元素哈希值:


        item   h1     h2     h3     h4     in A   in B
fox    0.07   0.52   0.66   0.38    ✓      ✓
cat    0.21   0.15   0.80   0.91    ✓
dog    0.48   0.33   0.09   0.74    ✓      ✓
emu    0.63   0.27   0.44   0.12           ✓
owl    0.90   0.71   0.58   0.29    ✓
      

对于每个哈希函数,集合只保留其元素中最小的哈希值。这 k 个最小值就是该集合的签名。要估计两个集合的相似度,逐位比较它们的签名,统计相等值的个数,再除以 k:


        h1     h2     h3     h4
A signature  0.07   0.15   0.09   0.29
B signature  0.07   0.27   0.09   0.12
equal        ✓             ✓
             → 2 of 4 = 0.5
      

估计的相似度(0.5)与实际值(2 个共有元素 / 5 个不同元素 = 0.4)不同。为了获得更准确的估计,k 通常比本例中大得多。

单置换哈希18 使用单个哈希函数对每个元素只哈希一次,并将哈希值的范围划分为 k 个相等的桶。每个桶保留其元素中最小的哈希值。下面是同样的集合在 k=4 时的情况,使用上面的 h1:


        bucket       0            1            2            3
range        0.00–0.25    0.25–0.50    0.50–0.75    0.75–1.00

A items      fox 0.07     dog 0.48                  owl 0.90
             cat 0.21
B items      fox 0.07     dog 0.48     emu 0.63

A minimums   0.07         0.48         ·            0.90
B minimums   0.07         0.48         0.63         ·
      

每个桶的作用类似于对其范围内元素单独进行的一次 MinHash。因此,各桶的最小值构成一个签名,比较两个签名的方式相同。但有一个问题:当集合不比 k 大很多时,某些桶会为空(如上图中的 · 所示),因此这些桶中没有可比较的内容。

最优致密化19 通过用同一集合中另一个桶的值填充每个空桶来解决这个问题。每个空桶按伪随机顺序尝试其他桶,并复制第一个非空桶的值:

文章标题:Go 中的概率数据结构,第二部分

正文:


        bucket       0         1         2         3
A minimums   0.07      0.48      ·         0.90
B minimums   0.07      0.48      0.63      ·

A signature  0.07      0.48      0.90 (3)  0.90
B signature  0.07      0.48      0.63  │   0.07 (0)
equal        ✓         ✓               │         │
             → 2 of 4 = 0.5            │         │
                                       │         │
             该值是从哪个 bucket 复制而来的
      

这个顺序只取决于空 bucket 的位置,因此两个相似的集合往往会用相同的值填充空位。这使得该估计对任意大小的集合都适用,误差与经典 MinHash 大致相同。

Unsure 在 sketch 中保留 k 个 bucket 最小值。Add 和 Merge 使用原始的 bucket。稠密化只发生在 Signature 中,它会复制一份 bucket,而不修改 sketch。

每个项用 64 位 wyhash 哈希一次。将哈希乘以 k 一次即可同时得到 bucket 和要存储的值:


        ┌─────────────────┬─────────────────┬─────────────────┐
│ 高 64 位:      │ 接下来 32 位:  │ 剩余:          │
│ [0,k) 中的 bucket │ 值            │ 未使用          │
└─────────────────┴─────────────────┴─────────────────┘
127              64                32                 0
      

稠密化以协调的方式填充空 bucket,将副本均匀地分散到非空 bucket 上。这使误差接近经典 MinHash,并且即使对于小集合也能让稠密化很快完成。

基准测试

以下是完整基准测试20的摘录,将 unsure 与 dgryski21(经典 MinHash)进行比较(ns/op,越低越好):

操作kunsuredgryski
Add64530
2565115
10245358
Similarity642524
256104103
1024378376

k=256、J=0.5 时相似度估计的 RMSE(越低越好):

不同项数unsuredgryski
2562.89%3.07%
1,0242.84%3.12%
4,0962.99%3.09%
16,3843.11%3.07%
内存1.0 KB2.0 KB

Unsure 添加项的速度比 dgryski 快 6–70 倍,比较签名的速度相同,准确度大致相同,并且只使用一半的内存。

  • Andrei Broder 的经典 MinHash 论文,1997 年。 ↩︎
  • Ping Li 等人的单置换哈希,2012 年。 ↩︎
  • Anshumali Shrivastava 的最优稠密化论文,2017 年。 ↩︎
  • MinHash 基准测试。 ↩︎
  • Damian Gryski 的 dgryski/go-minhash。 ↩︎

总结

Bloom filter 和 HyperLogLog 是大家的最爱,但它们并不是唯一有用的概率数据结构。在某些情况下,你可能会发现这些很有帮助:

  • 当你能事先知道所有项时,Binary fuse filter 是 Bloom filter 的更紧凑替代方案。
  • UltraLogLog 是 HyperLogLog 的更紧凑(但更慢)的替代方案。
  • Log-linear histogram 是 t-digest 的准确得多的替代方案(大小可变)。
  • MinHash 使用很小的固定大小签名来比较大型集合的相似度。

要在 Go 中使用它们,可以试试 nalgeon/unsure 包:


        go get github.com/nalgeon/unsure
      

★ 订阅以跟进新文章。

The translation is machine-generated and individual terms may be off. Nothing is rewritten or cut; the original is authoritative.

Published by Lobsters
This site only summarises and aggregates; copyright stays with the original author. Headlines and summaries follow the source — where they differ, the original wins.
Read the original ↗