Distinct Counters

读书笔记 | Small Summaries for Big Data Ch9.3-9.4
9.4.3 Nesting Summaries
构建新摘要的一种自然方法是将摘要“嵌套”在一起。也就是说，我们使用一个摘要类型作为另一个摘要中的子结构。我们已经看到了一些符合这一描述的例子。例如，是通过在采样结构中嵌套 Sparse Recovery 摘要来构建的。接下来，我们将描述一些示例，其中一个摘要类型“嵌套”在另一个摘要中。

Summaries Using Probabilistic Counters
许多摘要（特别是草图摘要）是基于计数器的集合，这些计数器通过哈希函数计算映射到这些计数器的项目数。我们可以用 Morris Counter 概率计数器替换精确计数器。其结果是，当处理真正巨大的输入时，减少了摘要所需的空间

Morris Counter可以将精确计数器的比特大小被减小到了该量的对数。经过仔细论证，可以证明得出的估计值大致正确。

Summaries Using Distinct Counters
考虑这样一个问题，我们的输入是由一系列描述的，我们希望找到那些与大量不同y值相关的x值。例如，可以是图中的边，我们希望找到那些具有大量（不同）邻居的节点。

如果只有几个x值，那么我们将为每个x保留一个不同的计数器（KMV或HLL结构）。如果没有重复的，我们将使用频繁的项目结构，如 SpaceSaving 或 Count Min Sketch摘要。

因此，当有许多x值和许多重复时，为了解决问题的一般形式，我们可以将频繁项结构与基数计数器相结合。一个简单的实例化来自于获取Count Min Sketch，并用HLL摘要替换每个计数器。每次更新都使用Count Min Sketch的哈希函数将x映射到一组单元格。每个单元格都包含一个HLL，该HLL用y值更新。

新嵌套摘要的分析类似于Count Min Sketch的分析：为了估计与给定x关联的不同y的数量，我们检查映射该x的单元格。每一个都估计该x和其他碰撞项的不同y的数量。取这些估计值中的最小值，将碰撞项目产生的噪声量降至最低。