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

Question

10

考虑我们有一个算法，接收一条假设很长的键流。随着我们处理每个密钥，它会生成0到1之间的值，以供后续检索。输入集足够大，因此我们无法为每个键存储一个值。生成值的规则在键之间是独立的。

现在假设我们可以容忍后续查找中的误差，但我们仍希望最小化检索值和原始值之间的差异（即渐近地在许多随机检索中）。

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

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

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

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

- Amelio Vazquez-Reina

我们可以进行范围分区并编写哈希函数将每个数字映射到特定的范围。根据误差因素，可以控制范围内的值。 - Ankur Shanbhag

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- harold · Accepted Answer

也许是布隆过滤器的变种紧凑逼近器：类似于布隆过滤器，但是将条目泛化为来自格的值。该格只是介于0和1之间的浮点数（它具有比仅仅是格更多的结构，但它满足要求），或者您存储这些数字的方式。

更新将相关条目替换为其和被记住值之间的最大值，查询计算所有相关条目的最小值（以下是示例）。结果只能高估真实值。通过反转排序（交换min和max并初始化为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