什么是概率数据结构？

Question

我已经阅读过像bloom过滤器和跳过列表这样的数据结构.

概率数据结构的共同特征是什么？它们用于什么？

Answer 1

可能有很多不同的(和好的)答案,但在我看来,概率数据结构的共同特征是它们为您提供了近似的,而不是精确的答案.

这里有多少件物品？约1523425,概率为99%

更新:快速搜索产生了关于该问题的体面文章的链接:

https://highlyscalable.wordpress.com/2012/05/01/probabilistic-structures-web-analytics-data-mining/

Answer 2

概率数据结构无法给出明确的答案,而是为您提供答案的合理近似值以及近似估计值的方法.它们对于大数据和流应用程序非常有用,因为它们可以显着减少所需的内存量(与提供精确答案的数据结构相比).

在大多数情况下,这些数据结构使用散列函数来随机化项目.因为它们忽略了碰撞,所以它们保持大小不变​​,但这也是它们无法为您提供精确值的原因.他们带来的好处:

• 他们使用少量内存(你可以控制多少)
• 它们可以很容易地并行化(哈希是独立的)
• 他们有不断的查询时间(甚至没有像字典中那样的摊销常数)

经常使用的概率数据结构是:

• 布隆过滤器
• count-min sketch
• hyperLogLog

Answer 3

如果您对概率数据结构感兴趣，则可能需要阅读我最近出版的《大数据应用程序的概率数据结构和算法》（ISBN：9783748190486，可在亚马逊上获得），在这里我已经解释了许多此类节省空间的数据结构和快速算法，这些算法在现代大数据应用程序中非常有用。

在本书中，您可以找到有助于解决大数据处理中常见问题的最新算法和数据结构，例如：

• 成员资格查询（Bloom过滤器，Counting Bloom过滤器，商过滤器，Cuckoo过滤器）。
• 基数（线性计数，概率计数，LogLog，HyperLogLog，HyperLogLog ++）。
• 频率（多数算法，频率，计数草图，计数最小草图）。
• 等级（随机采样，q消化，t消化）。
• 相似性（LSH，MinHash，SimHash）。

您可以在https://pdsa.gakhov.com上免费获得预览以及有关该书的所有相关信息。