java - 用于数字检索的节省空间的概率数据结构

Question

假设我们有一个算法可以接收假设很长的 key 流。然后，当我们处理它时，它会为每个键生成一个介于 0 和 1 之间的值，用于后验检索。输入集足够大，我们无法为每个键存储一个值。值生成规则在键之间是独立的。

现在，假设我们可以容忍后验查找中的错误，但我们仍然希望最小化检索和原始值之间的差异(即在许多随机检索中渐进)。

例如，如果给定键的原始值为 0.008，则检索 0.06 比检索 0.6 好得多。

我们可以使用什么数据结构或算法来解决这个问题？

布隆过滤器是我能想到的最接近的数据结构。可以量化输出范围，对每个桶使用布隆过滤器，并以某种方式在检索时组合它们的输出以估计最可能的值。在我继续这条道路并重新发明轮子之前，是否有任何已知的数据结构、算法、理论或实践方法来解决这个问题？

理想情况下，我正在寻找一种可以参数化空间和错误率之间权衡的解决方案。

Answer 1

可能是布隆过滤器的一个变体，叫做 Compact Approximator : 像布隆过滤器但是被概括了所以条目是来自格的值。此处的格子只是在 0 和 1 之间 float (它具有比格子更多的结构，但它满足要求)或者您存储这些数字的方式。

更新用它和被记住的值之间的最大值替换相关条目，查询计算所有相关条目的最小值(下面的例子)。结果只能高估真实值。通过颠倒顺序(交换最小值和最大值并初始化为 1 而不是 0)，您可以获得低估，同时给出包含真实值的区间。

---

因此，例如，使用第一个近似值(高估)，输入一个数字如下所示:

index1 = hash1(key)
data[index1] = max(data[index1], value);
index2 = hash2(key)
data[index2] = max(data[index2], value);
... etc

得到高估看起来像:

result = 1
index1 = hash1(key)
result = min(data[index1], result);
index2 = hash2(key)
result = min(data[index2], result);
... etc