概率数据结构和算法

PipelineDB包含许多在大多数数据库中不对用户开放的数据类型和聚合函数，这些对流式数据处理是非常有用的，下面将围绕这些数据类型和函数进行说明。

Bloom Filter

Bloom filters 是一种空间优化的数据结构，它用于评估集合的基数，以及判断一个元素是否在集合中。Bloom filters通过将元素映射到位图中的一位或多位来实现。当元素添加到Bloom filter中，其对应的位点（理想状态下只会对应1）就被会置为1。

简而言之，这意味着一个n位的输入可以被压缩到1位。Bloom filters可以节省巨大的空间，代价就是判断元素时存在一定的假阳性，因为单个输入可能会映射到多个位点上。

Bloom filters如何应用于PipelineDB

包含 SELECT DISTINCT (...) 语句的流视图使用Bloom filters来判断元素是否唯一以及是否将其输出到结果中。这使得流视图可以在常数空间复杂度的情况下对无限的流数据进行高精度的去重。

用于也可以自由构造Bloom filters并且通过 PipelineDB特有函数 进行操作。

Count-Min Sketch

Count-min sketch 是一种与Bloom filter相似的数据结构，主要的区别是Count-min sketch评估每个元素的频数，而Bloom filter只记录元素是否在集合中。

尽管用户可以自由构造Count-min sketch数据结构并通过 PipelineDB特有函数 进行操作，但目前Count-min sketch没有在PipelineDB函数中隐式使用。

Top-K

Filtered-Space Saving (FSS)是一种只消耗最小常数内存来精确评估流中最频繁的k个值的数据结构和算法。计算top-k最普通的方法就是维系一张值的计数表，但这在流中不实用。

FSS通过哈希运算将输入值归入对应的桶中。若输入值已在桶中，会增加其频数。若不存在，它会在满足一定条件时被添加进去。

目前FSS没有在PipelineDB中隐式使用。FSS及其相关函数通过 PipelineDB特有函数 和 流聚合 使用。

HyperLogLog

HyperLogLog 是一种与Bloom filters相似的数据结构，被设计用于高准确度地评估集合基数。就功能而言，HyperLogLog只支持添加元素以及评估集合中的所有元素。它不能像Bloom filters一样进行单个元素的检索，但空间利用率比Bloom filters更高。

HyperLogLog将输入流添加的元素进行分割，并存储每个子集中前导0的最大数量。由于在检查前导0个数前会对元素进行均匀散列，通常的观点是：前导0的个数越多，许多唯一元素被添加的概率就越高。根据经验，HyperLogLog估计的准确度是很高的，PipelineDB的HyperLogLog误差率只有大约0.81%（约千分之八）。

HyperLogLog在PipelineDB中的应用

包含 COUNT(DISTINCT ...) 语句的流视图借助HyperLogLog在常数空间复杂度下从无限的流数据中精确计算集合基数。hypothetical-set聚合函数，dense_rank 函数也使用HyperLogLog精确计算低排名元素并决定其排名。

用户也可以自由构造HyperLogLog数据结构并通过 PipelineDB特有函数 使用。

T-Digest

T–Digest 是一种支持精确排序统计的数据结构，如在常数空间复杂度下计算百分位数和中位数。以很小的误差达到高效的性能，使得T-Digest很适合用于流的排序计算，这要求输入是有限且有序以达到高度的精确性。T-Digest本质上是一种在元素被添加时智能调整桶和频数的自适应的直方图。

T–Digest在PipelineDB中的应用

percentile_cont 聚合函数在处理流数据时隐式使用T-Digest。用户可以自由构造T-Digest数据并通过 PipelineDB特有函数 使用。