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

Question

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

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

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

我们可以使用哪些数据结构或算法来解决此问题？

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

我理想地寻找一种可以参数化空间和错误率之间权衡的解决方案.

Answer 1

也许Bloom过滤器的变体叫做Compact Approximator:就像一个布隆过滤器,但是一般化,所以条目是来自格子的值.这个晶格在这里只是浮动在0和1之间(它具有更多的结构,而不仅仅是一个晶格,但它满足要求)或者你存储这些数字.

更新将相关条目替换为它与被记住的值之间的最大值,查询计算其所有相关条目的最小值(下面的示例).结果只能高估真实价值.通过反转排序(交换最小值和最大值并初始化为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