概率数据结构和草图有什么区别?

Question

根据这个StackOverflow问题，概率数据结构是给出近似答案而不是精确答案的数据结构。特别是，它们具有非常低的时间和空间复杂性，并且易于并行化，使它们非常有效地使用结构。提供的示例包括布隆过滤器、最小计数草图和 HyperLogLog。

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

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

Answer 1

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