data-structures - 概率数据结构和草图有什么区别？

Question

根据这个 StackOverflow 问题，概率数据结构是给出近似而非精确答案的数据结构。特别是，它们的时间和空间复杂性非常低，并且易于并行化，这使得它们的使用效率非常高。提供的示例包括 Bloom Filters、Count-Min Sketch 和 HyperLogLog。

然而，所有这些数据结构也被称为“草图”数据结构——通过紧凑表示来近似一个大集合的结构，以实现更有效（但不太精确）的操作。

我看不出“草图”和“概率”数据结构之间的区别。

标签： data-structuresapproximationbloom-filterhyperloglog

Answer 1

有些概率数据结构不是近似值，例如跳过列表。