概率数据结构：用一点误差换取巨大的空间

在处理海量数据时，经常会遇到这样一些问题：

• 一个网页爬虫已经抓取了数十亿个网址，如何快速判断一个新网址是否已经抓取过？
• 一个网站每天有上亿次访问，如何统计当天有多少个不同的访客？
• 一个网络监控系统每秒处理数百万个数据包，如何找出流量最大的那些来源地址？

如果要精确地回答这些问题，就需要保存所有出现过的元素：所有已抓取的网址、所有访客的标识、每个来源地址的计数。当数据规模达到数十亿量级时，仅存储这些数据就需要数十甚至数百 GB 的内存，查询和更新也会变得缓慢。

然而，在许多实际场景中，并不需要完全精确的答案。网页爬虫偶尔重复抓取一个网址，代价很小；访客数统计为一亿零三十万还是一亿零二十八万，对决策几乎没有影响。如果能够接受一个可控的、很小的误差，就可以使用概率数据结构（Probabilistic Data Structures），以远小于精确方法的内存，快速地给出近似答案。

本文介绍几种最常用的概率数据结构：用于成员查询的布隆过滤器及其变种，用于基数估计的 HyperLogLog，用于频率估计的 Count-Min Sketch，以及用于分位数估计和相似度估计的相关技术，并讨论它们的原理、误差特性和适用场景。

一、哈希函数：概率数据结构的基础

几乎所有概率数据结构都建立在哈希函数之上。一个好的哈希函数能够将任意输入映射为一个看起来随机、均匀分布的输出值：

• 确定性：相同的输入总是得到相同的输出；
• 均匀性：输出值在取值范围内均匀分布；
• 独立性：输入的微小变化会导致输出的巨大变化，不同输入的输出之间看起来相互独立。

概率数据结构正是利用了哈希值的"伪随机"特性：将确定的输入数据转化为近似随机的数值，然后借助概率论的结论来分析和控制误差。

在概率数据结构中使用的哈希函数，通常追求速度和分布质量，而不需要具备密码学安全性。需要多个独立哈希函数时，常用的技巧是双重哈希：只计算两个基础哈希值 h₁ 和 h₂，再通过 h₁ + i × h₂ 的方式派生出第 i 个哈希函数。理论分析表明，这种方式在实践中与使用真正独立的哈希函数效果相当，却大大减少了计算量。

二、布隆过滤器

要解决的问题

成员查询（Membership Query）是最基本的集合操作：判断一个元素是否属于某个集合。

精确的方法是使用哈希集合，将所有元素都存储下来。查询速度很快，但内存占用与元素的数量和大小成正比。如果集合中有十亿个平均长度为 50 字节的网址，仅存储这些网址本身就需要约 50GB 内存。

布隆过滤器（Bloom Filter）由 Burton Bloom 于 1970 年提出，它不存储元素本身，而只用一个比特数组来"记住"元素是否出现过。

结构与操作

布隆过滤器由两部分组成：

• 一个长度为 m 的比特数组，初始时所有位都为 0；
• k 个独立的哈希函数，每个函数将元素映射到数组中的一个位置。

插入一个元素时，用 k 个哈希函数分别计算出 k 个位置，将这些位置的比特都设为 1。

查询一个元素时，同样计算出 k 个位置，检查这些位置的比特：

• 如果任何一个位置为 0，那么该元素一定不在集合中，因为如果它被插入过，这些位置必然都已被设为 1；
• 如果所有位置都为 1，那么该元素可能在集合中。

之所以只能说"可能"，是因为这些位置的 1 有可能是由其他元素插入时设置的。这种情况下，布隆过滤器会错误地报告一个不存在的元素存在，这称为假阳性（False Positive）。

布隆过滤器有一个关键的性质：不会出现假阴性。凡是插入过的元素，查询时一定会返回"可能存在"。

误判率分析

假阳性的概率取决于三个参数：比特数组的长度 m、插入的元素数量 n，以及哈希函数的个数 k。

插入 n 个元素后，某一个特定比特仍然为 0 的概率约为 e^(−kn/m)。查询一个不存在的元素时，它的 k 个位置恰好全为 1 的概率，即假阳性率，约为：

p ≈ (1 − e^(−kn/m))^k

对于给定的 m 和 n，存在一个使误判率最低的哈希函数个数：

k = (m/n) × ln 2 ≈ 0.693 × (m/n)

此时，比特数组中大约一半的位为 1。在最优的 k 下，达到目标误判率 p 所需的比特数为：

m/n ≈ −1.44 × log₂ p

也就是说：

• 误判率为 1% 时，每个元素约需 9.6 个比特，使用 7 个哈希函数；
• 误判率为 0.1% 时，每个元素约需 14.4 个比特，使用 10 个哈希函数。

一个非常重要的特点是：所需的空间与元素本身的大小无关。无论元素是一个整数还是一个长达数 KB 的字符串，在布隆过滤器中都只占用约 10 个比特。存储十亿个网址，若接受 1% 的误判率，只需约 1.2GB 内存，而不是精确存储所需的数十 GB。

局限

布隆过滤器有几个固有的局限：

• 不支持删除：一个比特可能被多个元素共享。如果在删除一个元素时将它的 k 个位置置为 0，可能会影响其他元素，导致假阴性；
• 容量需要预先确定：比特数组的长度在创建时就固定了。如果插入的元素远超预期，比特数组中 1 的比例会越来越高，误判率会急剧上升，最终几乎所有查询都返回"可能存在"；
• 无法列举元素：布隆过滤器只能回答某个元素是否可能存在，无法取出集合中的元素；
• 查询需要多次随机内存访问：k 个位置分散在比特数组的各处，当数组很大时，每次查询可能导致 k 次缓存未命中。

典型应用

布隆过滤器最常见的用法是作为一个前置过滤器，用极小的代价排除掉大量"一定不存在"的查询，避免执行昂贵的后续操作：

• 数据库与存储引擎：基于 LSM 树的存储引擎为每个磁盘文件附带一个布隆过滤器。查询一个键时，先检查各文件的布隆过滤器，对于确定不包含该键的文件直接跳过，从而避免了大量无效的磁盘读取；
• 缓存穿透防护：将所有合法的键加入布隆过滤器，对于查询不存在的键的请求，在访问缓存和数据库之前就直接拦截；
• 网页爬虫去重：判断一个网址是否已经抓取过。少量的误判只会导致个别网址被跳过，影响很小；
• 分布式系统：在节点之间交换布隆过滤器，以较小的网络开销告知对方自己拥有哪些数据，例如在分布式连接操作中预先过滤不可能匹配的记录；
• 安全领域：快速判断一个网址或文件是否在已知的恶意列表中，只有在布隆过滤器返回可能存在时，才进行精确的检查。

三、布隆过滤器的变种

为了克服标准布隆过滤器的局限，研究者提出了多种变种。

计数布隆过滤器

计数布隆过滤器（Counting Bloom Filter）将比特数组中的每一位替换为一个小型计数器，通常为 4 位。

• 插入时，将 k 个位置的计数器都加 1；
• 删除时，将 k 个位置的计数器都减 1；
• 查询时，检查 k 个位置的计数器是否都大于 0。

这样就支持了删除操作。代价是空间占用增加为原来的数倍。此外，只能删除确实插入过的元素，如果删除一个从未插入的元素，可能会将其他元素的计数器错误地减为零，导致假阴性。

可扩展布隆过滤器

可扩展布隆过滤器（Scalable Bloom Filter）解决了容量需要预先确定的问题。

它由一系列布隆过滤器组成。当当前的过滤器接近容量上限时，就创建一个新的、容量更大的过滤器，后续的元素插入到新过滤器中。查询时，需要依次检查所有的过滤器，只要任何一个返回可能存在，即视为可能存在。

为了让整体的误判率保持在目标范围内，每个新增的过滤器都使用比前一个更严格的误判率，使得所有过滤器误判率之和收敛于一个有限值。

分块布隆过滤器

分块布隆过滤器（Blocked Bloom Filter）针对缓存性能进行了优化。

它将比特数组划分为许多大小等于一个缓存行的小块，例如 512 位。插入或查询一个元素时，先用一个哈希函数选定一个块，再在这个块内部设置或检查 k 个位置。这样，每次操作只需访问一个缓存行，大大减少了缓存未命中，配合 SIMD 指令还可以并行检查多个位置。

代价是误判率会略高于相同空间下的标准布隆过滤器，因为元素在各块之间的分布不完全均匀，部分块会比其他块更"满"。

布谷鸟过滤器

布谷鸟过滤器（Cuckoo Filter）是一种在许多方面优于布隆过滤器的替代结构，它基于布谷鸟哈希的思想。

布谷鸟过滤器不存储比特，而是存储元素的指纹：一个从元素哈希值中截取的短比特串，例如 8 位或 12 位。它维护一个由多个桶组成的哈希表，每个桶可以存放若干个指纹。

每个元素有两个候选桶：

桶₁ = hash(元素)
桶₂ = 桶₁ ⊕ hash(指纹)

这个设计的巧妙之处在于：已知一个指纹和它当前所在的桶，就可以通过同样的异或运算算出它的另一个候选桶，而不需要知道原始元素。

• 插入：计算元素的指纹和两个候选桶。如果其中有空位，就将指纹放入。如果两个桶都满了，就随机踢出其中一个桶里的某个指纹，将新指纹放入；被踢出的指纹移动到它的另一个候选桶中，如果那里也满了，就继续踢出，如此反复。如果反复踢出的次数超过上限，则认为过滤器已满；
• 查询：检查两个候选桶中是否存在该指纹；
• 删除：在两个候选桶中找到该指纹并移除。

布谷鸟过滤器的主要优点是：

• 支持删除，且不需要像计数布隆过滤器那样使用额外的计数器；
• 查询只访问两个桶，缓存效率高于需要访问 k 个分散位置的布隆过滤器；
• 在误判率较低时，例如低于约 3%，空间效率优于布隆过滤器。

其缺点是插入操作在过滤器接近满载时可能变慢甚至失败，并且同一个元素重复插入的次数受到桶容量的限制。

异或过滤器

如果集合是静态的，即一次性构建后不再修改，还可以使用异或过滤器（Xor Filter）等更节省空间的结构。

异或过滤器同样存储指纹。构建时，通过求解一组方程，为一个数组中的每个槽位赋值，使得对于集合中的每个元素，其三个哈希位置上的值异或起来恰好等于该元素的指纹。查询时，计算三个位置的异或值，与元素的指纹比较即可。

在相同的误判率下，异或过滤器比布隆过滤器节省约 20% 的空间，查询也只需三次内存访问。但它不支持插入和删除，任何修改都需要重新构建。这非常适合用于存储引擎中那些一旦写入就不再修改的数据文件。

四、基数估计：HyperLogLog

要解决的问题

基数（Cardinality）是指一个集合中不同元素的数量。统计网站的独立访客数、数据库中某列有多少个不同的值、网络中有多少个不同的来源地址，都是基数估计问题。

精确计算基数需要记住所有出现过的元素，内存占用与基数成正比。对于基数达到数亿甚至数十亿的场景，这种方法代价太高。

直观思路

HyperLogLog 背后的直觉来自一个简单的概率现象。

假设不断地抛一枚均匀的硬币，记录每一轮直到第一次出现正面所需的次数。连续出现 k 次反面再出现正面的概率是 1/2^(k+1)。如果在多轮实验中观察到的最长连续反面次数是 10，那么可以推测大约进行了 2^10 轮左右的实验，因为如此罕见的事件，平均需要这么多次尝试才会出现一次。

对应到基数估计：将每个元素哈希为一个随机的二进制串，观察其中前导零的个数。前导零的个数相当于"连续反面的次数"。如果在所有元素中观察到的最大前导零个数为 k，那么不同元素的数量大约是 2^k 量级。

关键在于：相同的元素总是产生相同的哈希值，重复出现不会影响最大前导零个数，因此这个方法统计的恰好是不同元素的数量。而只需要记住一个数字，即目前观察到的最大前导零个数，内存占用极小。

降低方差

仅用一个最大值进行估计，结果的方差极大：只要碰巧有一个元素的哈希值有很多前导零，估计值就会严重偏高。

分桶平均可以显著降低方差：

1. 用哈希值的前 b 位，将元素分配到 m = 2^b 个桶中；
2. 每个桶独立地记录其中元素哈希值剩余部分的最大前导零个数；
3. 综合所有桶的结果得出最终估计。

如何综合各桶的结果，是这一系列算法演进的关键。早期的方法使用算术平均，HyperLogLog 改用调和平均，它对少数偏大的异常值不敏感，能更有效地抑制离群值的影响。

HyperLogLog 的估计

HyperLogLog 的估计公式为：

E = α_m × m² × (Σ 2^(−M[j]))^(−1)

其中 M[j] 是第 j 个桶记录的值，α_m 是一个用于修正偏差的常数。

此外，HyperLogLog 在基数很小和很大时还需要进行修正：

• 当基数远小于桶的数量时，许多桶仍然为空，此时改用线性计数方法，根据空桶的比例估计基数，结果更准确；
• 早期版本在基数接近哈希空间上限时需要额外修正，使用 64 位哈希值后，这一问题在实际中基本不会出现。

精度与空间

HyperLogLog 的标准误差约为：

σ ≈ 1.04 / √m

例如：

• 使用 1024 个桶，标准误差约为 3.25%；
• 使用 16384 个桶，标准误差约为 0.81%。

每个桶只需存储一个最大前导零个数。对于 64 位哈希值，前导零个数不会超过 64，因此每个桶只需 6 位。16384 个桶总共只需约 12KB 内存，就能以约 0.8% 的标准误差估计高达数十亿甚至更大的基数。

这是一个惊人的空间效率：无论实际基数是一千还是一百亿，内存占用都固定为 12KB 左右。

可合并性

HyperLogLog 有一个极为实用的性质：可合并。两个使用相同参数构建的 HyperLogLog，只需逐个桶取最大值，就能得到它们并集的 HyperLogLog。

这带来了很大的便利：

• 分布式统计：每台服务器各自统计本地的访客，最后合并得到全局的独立访客数，无需汇总原始数据；
• 时间维度聚合：为每个小时保存一个 HyperLogLog，任意时间段的独立访客数可以通过合并对应小时的结构得到；
• 多维度分析：为不同的维度组合分别保存结构，按需合并。

需要注意的是，HyperLogLog 能够准确地计算并集的基数，但对于交集的基数，只能通过容斥原理间接估计：|A ∩ B| = |A| + |B| − |A ∪ B|。当交集相对于并集很小时，这种估计的相对误差可能非常大。

改进

在原始 HyperLogLog 的基础上，后续研究提出了一些改进：

• 使用 64 位哈希函数，避免了大基数时的哈希碰撞问题；
• 对小基数区间的偏差进行经验修正，提高小基数时的精度；
• 在基数较小时使用稀疏表示，只记录非空的桶，当基数增长到一定程度后再切换为稠密表示，节省小基数时的内存。

HyperLogLog 已被广泛集成到各种数据库、缓存系统和数据分析引擎中，用于实现近似的去重计数功能。

五、频率估计：Count-Min Sketch

要解决的问题

在数据流中，经常需要估计每个元素出现的频率：某个搜索词今天被搜索了多少次、某个地址发送了多少个数据包、某个商品被浏览了多少次。

精确的方法是为每个不同的元素维护一个计数器。但当不同元素的数量非常大时，例如网络流量中的地址组合，维护所有计数器的内存开销无法承受。

结构

Count-Min Sketch 是一种用固定大小的内存估计元素频率的结构，由一个 d 行 w 列的二维计数器数组，以及 d 个相互独立的哈希函数组成，每一行对应一个哈希函数。

更新：一个元素出现时，对每一行 i，用第 i 个哈希函数计算出列号，将该行该列的计数器加一。

查询：估计一个元素的频率时，同样计算出它在每一行的列号，读取 d 个计数器的值，取其中的最小值作为估计结果。

为什么取最小值

由于列数 w 远小于不同元素的数量，多个元素必然会被映射到同一个计数器上，计数器的值是这些元素频率的总和。因此，每一个计数器的值都大于或等于目标元素的真实频率，不会低估。

不同行使用不同的哈希函数，一个元素在某一行可能与许多高频元素碰撞，在另一行可能只与少数低频元素碰撞。取所有行中的最小值，就是选择碰撞最少、高估最小的那一个，从而得到最接近真实值的估计。

误差保证

Count-Min Sketch 提供了如下的误差保证：设所有元素频率之和为 N，选择 w = ⌈e/ε⌉，d = ⌈ln(1/δ)⌉，那么对于任意一个元素，估计值超过真实频率 εN 以上的概率不超过 δ。

例如，取 ε = 0.001，δ = 0.01，则需要约 2719 列、5 行，总共约一万三千多个计数器。无论数据流中有多少个不同的元素，都能保证以 99% 的概率，估计误差不超过总频数的千分之一。

需要注意的是，误差是相对于总频数 N 而言的，而不是相对于元素自身的频率。对于高频元素，这个误差相对于其真实频率来说很小，估计较为准确；而对于低频元素，误差可能远大于其真实频率，估计结果几乎没有意义。因此，Count-Min Sketch 特别适合用于发现高频元素，而不适合估计低频元素的精确计数。

改进与变种

• 保守更新：更新时，不是将 d 个计数器都加一，而是只增加那些当前值等于最小值的计数器。这样可以减少不必要的高估，在实践中显著提高精度，代价是不再支持减少计数的操作；
• Count Sketch：每一行额外使用一个将元素映射为 +1 或 −1 的哈希函数，更新时加上或减去该值，查询时取各行结果的中位数。由于碰撞带来的误差有正有负，可以相互抵消，估计是无偏的，在频率分布较为平坦时精度更高；
• 可合并性：使用相同参数和哈希函数的两个 Count-Min Sketch，只需将对应位置的计数器相加，就能得到合并后数据流的结构。

寻找高频元素

一个常见的需求是找出数据流中出现频率最高的前 K 个元素，即热门元素（Heavy Hitters）问题。

Count-Min Sketch 本身只能估计给定元素的频率，不能列出所有元素。常见的做法是将它与一个大小为 K 的最小堆结合：每处理一个元素，更新 Sketch 并查询其估计频率；如果估计频率超过了堆中的最小值，就将该元素加入堆中，替换掉频率最低的元素。

另一类专门的算法，例如空间节省算法（Space-Saving），直接维护固定数量的计数器，每个计数器记录一个元素及其计数。遇到新元素时，如果计数器已满，就替换掉计数最小的那个元素，并以被替换元素的计数加一作为新元素的初始计数。这类算法实现简单，在寻找热门元素方面效果非常好，被广泛用于网络流量分析、热门搜索词统计、缓存热点检测等场景。

六、分位数估计

在监控系统中，平均值往往会掩盖问题。例如，平均响应时间为 50 毫秒，可能隐藏着 1% 的请求需要 5 秒的事实。因此，分位数更能反映系统的真实表现：P50、P95、P99、P999 分别表示有 50%、95%、99%、99.9% 的请求的响应时间低于该值。

精确计算分位数需要保存并排序所有的数据点，在高吞吐的监控场景中代价过高。而且，分位数不能像平均值那样简单地合并：多台服务器的 P99 响应时间，无法通过任何简单的运算得出整体的 P99。

t-digest

t-digest 是一种常用的分位数估计结构。它将数据点聚合成一系列质心，每个质心记录一个均值和它所代表的数据点个数。

其核心设计在于：质心的大小随分位数位置变化。在分布的两端，即接近 0 和 1 的分位数附近，质心只允许包含很少的数据点，保留了较高的精度；在分布的中间区域，质心可以包含大量的数据点。这正好符合实际需求：人们最关心的往往是 P99、P999 这样的尾部分位数，需要更高的精度；而中位数附近的少许误差通常可以接受。

t-digest 支持合并，多个数据源的 t-digest 可以合并为一个，用于计算全局分位数。

其他方法

• 固定分桶直方图：预先定义一系列的区间边界，统计落入每个区间的数据点个数。实现简单、可以精确合并，但精度取决于区间的划分，需要预先知道数据的大致范围；
• 对数分桶直方图：区间边界按照指数增长，例如每个区间比前一个大一定的比例。这样可以用有限的桶数覆盖跨越多个数量级的数值范围，并保证相对误差有一个固定的上限。这类方法实现简单、合并方便，误差保证明确，在监控系统中得到了广泛应用；
• KLL 等基于采样压缩的算法：通过分层采样和压缩维护数据的摘要，提供可证明的秩误差保证，即估计的分位数在真实排序中的位置误差有明确的上界。

七、相似度估计：MinHash

要解决的问题

判断两个集合有多相似，是许多应用中的基本问题：两个网页的内容是否几乎相同，两个用户的兴趣是否相近，两份文档是否存在抄袭。

衡量集合相似度的常用指标是 Jaccard 相似度：两个集合交集的大小除以并集的大小。

J(A, B) = |A ∩ B| / |A ∪ B|

精确计算需要完整地比较两个集合。当集合很大，并且需要在海量集合之间两两比较时，计算量无法承受。

MinHash 的原理

MinHash 基于一个优雅的概率性质：

对两个集合的所有元素应用同一个随机哈希函数，分别取两个集合中哈希值的最小值。这两个最小值相等的概率，恰好等于两个集合的 Jaccard 相似度。

直观的理解是：在两个集合的并集中，哈希值最小的那个元素是随机均匀选出的。只有当这个元素恰好同时属于两个集合，即属于交集时，两个集合的最小哈希值才会相等。而它属于交集的概率，正是交集大小与并集大小之比。

因此，使用 k 个不同的哈希函数，为每个集合计算 k 个最小哈希值，组成一个长度为 k 的签名。两个集合签名中相同位置的值相等的比例，就是它们 Jaccard 相似度的估计。签名越长，估计越精确，标准误差约为 1/√k。

这样，无论原始集合有多大，都可以压缩为一个固定长度的签名，两个集合的相似度比较只需比较两个签名。

局部敏感哈希

即使每对集合的比较变得很快，在数以亿计的集合中两两比较，所需的比较次数仍然是天文数字。

局部敏感哈希（Locality Sensitive Hashing，LSH）可以进一步解决这个问题。其基本思路是：将每个集合的 MinHash 签名划分为若干段，每段包含若干个哈希值。对于每一段，将其内容作为键放入一个哈希表。只要两个集合有任意一段完全相同，就把它们作为候选对，再进行精确比较。

这种方式的效果是：相似度高的集合，很可能至少有一段完全相同，从而被选为候选；而相似度低的集合，几乎不可能有任何一段完全相同，被自动过滤掉。通过调整段的数量和每段的长度，可以控制相似度阈值以及假阳性和假阴性的比例。

MinHash 和局部敏感哈希被广泛用于网页去重、大规模数据集的近重复检测、推荐系统中的相似用户和相似物品查找，以及训练语料的去重清洗等场景。

八、各结构对比

九、使用中的注意事项

明确误差能否接受。 概率数据结构的结果是近似的，在使用之前必须确认业务能够接受这种误差。涉及计费、财务对账、权限判断等需要精确结果的场景，不应使用概率数据结构给出最终答案，但仍然可以用它进行前置过滤。

理解误差的方向。 不同结构的误差方向不同：布隆过滤器只会误报存在，不会漏报；Count-Min Sketch 只会高估，不会低估。根据误差方向设计业务逻辑，例如布隆过滤器返回"不存在"时可以直接信任，返回"存在"时再进行精确检查。

根据数据规模正确设置参数。 布隆过滤器的容量、HyperLogLog 的桶数、Count-Min Sketch 的宽度和深度，都直接决定了误差的大小。参数需要根据预期的数据规模和可接受的误差提前计算。特别是布隆过滤器，如果实际插入的元素远超设计容量，误判率会急剧上升，需要监控其填充程度。

合并时保持参数一致。 只有使用相同参数和相同哈希函数构建的结构才能合并。在分布式系统中，所有节点必须使用完全相同的配置，包括哈希函数的种子。

注意对抗性输入。 概率数据结构的误差分析假设输入与哈希函数无关。如果攻击者知道所使用的哈希函数，可能会构造特定的输入，例如大量与目标元素发生碰撞的元素，使误判率远高于预期。在面对不可信输入的场景中，可以使用带有随机密钥的哈希函数，使攻击者无法预测哈希结果。

结合精确方法使用。 概率数据结构常常与精确方法配合：用概率结构快速筛选候选，再对少量候选进行精确计算。这种组合在保证最终结果准确的同时，大幅降低了整体的计算和存储开销。

结语

概率数据结构体现了一种重要的工程思想：精确并不总是必要的，而对精确的执着往往代价高昂。通过接受一个小而可控的误差，布隆过滤器用每个元素十个比特回答成员查询，HyperLogLog 用十几 KB 统计数十亿个不同元素，Count-Min Sketch 用固定大小的数组追踪无限数据流中的高频元素，MinHash 将任意大小的集合压缩为一个固定长度的签名。

这些结构的共同基础，是哈希函数带来的伪随机性，以及概率论对随机现象的精确刻画。正是因为误差可以被严格地分析和控制，这些"不精确"的方法才能被放心地用在大规模的生产系统中。

在数据规模持续增长的今天，理解这些结构的原理和适用边界，能够为许多看似需要巨大资源的问题，找到一个简洁而高效的解决方案。