【论文阅读】– Omnisketch：高效的多维任意谓词高速流分析

Omnisketch：高效的多维任意谓词高速流分析

• • 摘要
  • 1 引言
  • 2 预备知识及相关工作
  • 3 OMNISKETCH：使用任意谓词估计频率
  • • 3.1 Sketch S0：Count-Min with rid-sets 用于估计带有谓词的查询
    • 3.2 Sketch S1 （OmniSketch）：通过采样实现亚线性空间
    • 3.3 扩展
  • 4 实验评价
  • • 4.1 S0 和 S1 的比较
    • 4.2 与最先进的比较
    • 4.3 不同流的 S1 评估
    • 4.4 范围查询
  • 5 总结
  • 参考文献

摘要

不同学科的一个关键需求是对快节奏的数据流执行分析，其性质类似于关系数据库中的传统 OLAP 分析，即使用过滤器和聚合。然而，由于存储要求高，以及存储海量数据时引入的延迟，存储无界流不是一种现实或理想的方法。因此，已经提出了许多概要/草图，它们可以在小内存（通常足够小以存储在RAM中）中总结流，这样就可以有效地近似聚合查询，而无需存储整个流。然而，过去的概要主要关注对单一属性流的总结，无法有效地处理对多个属性的任意子集进行过滤和约束。在这项工作中，我们提出了OmniSketch，这是第一个能够适应快节奏和复杂数据流（具有许多属性）的草图，并支持在查询时动态选择多个属性的过滤器的计数聚合。该草图提供概率保证、有利的空间精度权衡以及更新和查询执行的最坏情况下的对数复杂度。我们通过对真实和合成数据的实验证明，该草图优于最先进的技术，并且可以在配置好的精度保证下，以较小的内存需求近似复杂的临时查询。

PVLDB 参考格式：Wieger R. Punter, Odysseas Papapetrou, and Minos Garofalakis. OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates. PVLDB, 17(3): 319 – 331, 2023. doi:10.14778/3632093.3632098

PVLDB 工件可用性：源代码、数据和/或其他工件已在 https://github.com/wiegerpunter/omnisketch 上提供。

1 引言

筛选器和聚合器构成了数据分析的主力，并在所有数据库中实现。因此，已经实施了索引和存储技术，以有效地回答此类查询，即使在大数据上也是如此。当涉及到无法完整存储或实时查询的流数据时，首选技术基于草图 [5]：小内存数据结构，用于汇总流，随后可用于执行聚合查询。文献中的示例草图支持计数、范数和连接聚合的估计 [2， 6， 23]）、集合大小的估计 [9] 以及频繁项目和重击者的识别 [4]。

尽管被大量使用，但迄今为止，大多数草图都侧重于根据单个属性或预先选择的属性组合来总结频率分布。例如，考虑网络监控领域，其中 Count-min 草图经常用于统计维护 [6]。标准 IPv4 数据包报头定义至少 13 个字段/属性，包括版本、报头长度、总长度、DSCP 代码点、源地址和目标地址、协议，以及 30 个附加选项中的一个或多个。为了能够估计满足属性值组合（在查询时定义）的数据包数，我们需要构造一个草图，该草图使用这些属性的组合值（例如，它们的串联）作为键。作为运行示例，考虑图 1 中简化的 IPv4 标头流，它包含 13 个属性中的 4 个。为了总结每个 IP 地址发送的数据包数的分布，我们需要一个使用 ipSrc 作为密钥构建的草图。需要在 ipDest 上再绘制一个草图，以汇总每个 IP 地址接收的数据包数。如果我们还想汇总任意两个 IP 地址之间交换的数据包数，我们需要维护一个草图，该草图使用源-目标 IP 地址的串联作为键。为支持任意谓词（在此示例中，标题中包含的 13 个字段的任意子组合）而需要维护的草图数总计为 O （213） – 幂组的大小。将其推广到任意用例，估计 p 谓词的所有子组合的频率分布需要维护 2p − 1 草图。这显然是不可行的，因为空间要求和数据流上下文中出现的严格的效率限制。1

我们的贡献。在这项工作中，我们提出、分析和评估了一种名为 OmniSketch 的新型草图工具，它通过将草图与采样相结合，有效地解决了空间和时间效率问题。OmniSketch 结合了草图的紧凑性（这是减少内存约束所必需的）和采样的通用性（这是支持常规查询的关键），适用于在查询时动态决定的谓词。简而言之，用于汇总 p 属性数据流的 OmniSketch 由 p 个单独的小内存子草图组成，每个子草图都类似于 Count-Min 草图。但是，与 Count-Min 草图不同的是，OmniSketch 子草图中的单元格包含哈希到其中的所有记录的固定大小的摘要。在查询时，将定位并查询与查询相关的子草图以及每个子草图中的相关单元格，以估计答案。与以前的工作不同，OmniSketch 提供了计算复杂性（用于更新和查询），该复杂性随属性数量线性扩展（而不是指数级），使其成为迄今为止唯一可行的通用解决方案，用于在狭小空间内汇总具有许多属性的快节奏流。我们的草图以提供形式错误保证的理论分析为后盾，以及基于理论分析的自动初始化算法，以充分利用可用的草图存储器。

我们在真实和合成生成的流上对 OmniSketch 进行了实验性评估，并将其与最先进的竞争对手 Hydra 进行了比较。我们的实验证实，OmniSketch 是汇总复杂流的唯一可行选择，并且具有有利的复杂性和准确性权衡。相比之下，Hydra 在汇总具有五个或更多属性的流时变得非常慢，因此无法有效地汇总快节奏的流。

路线图。本文的其余部分结构如下。在第 2 节中，我们介绍了初步情况并讨论了相关工作。在第 3 节中，我们介绍了 OmniSketch 并分析了其理论特性，而第 4 节总结了我们的实验结果。我们总结了这项工作，并在第 5 节中总结了未来的计划。

2 预备知识及相关工作

预备知识。OmniSketch 继承了 CountMin 草图 [6] 的基本结构，并建立在 k-minwise 哈希理论 [22] 的基础上。现在，我们将简要介绍这两部作品，以深入理解我们的工作。

计数-最小素描（Count-Min Sketch）。由Cormode和Muthukrishnan于2005年提出[6]，计数-最小素描已成为数据流分布汇总的事实标准方法。一个计数-最小素描CM是一个二维数组，宽度为w，深度为d，并伴随有d个两两独立的哈希函数，将输入映射到范围

{

1

,

.

.

.

,

w

}

\{1, …, w\}

{1,…,w}内。设

C

M

[

j

,

h

j

(

⋅

)

]

CM[j, h_j(\cdot)]

CM[j,hj​(⋅)]表示二维数组中第j行，第

h

j

(

⋅

)

h_j(\cdot)

hj​(⋅)列的计数器。一条记录r（例如，一个IP地址）通过增加

C

M

[

j

,

h

j

(

r

)

]

CM[j, h_j(r)]

CM[j,hj​(r)]处的计数被添加到素描中一次，其中j属于

{

1

,

.

.

.

,

d

}

\{1, …, d\}

{1,…,d}。流中任何查询q的到达次数估计是通过查找每行j对应的单元格

C

M

[

j

,

h

j

(

q

)

]

CM[j, h_j(q)]

CM[j,hj​(q)]，并返回最小计数值，即

f

^

(

q

)

=

m

i

n

j

∈

{

1

,

.

.

.

,

d

}

(

C

M

[

j

,

h

j

(

q

)

]

)

\hat{f}(q) = min_{j\in\{1,…,d\}}(CM[j,h_j(q)])

f^​(q)=minj∈{1,…,d}​(CM[j,hj​(q)])。由于哈希冲突（除了q之外落在相同计数器上的其他项）f̂(q)可能是真实频率f(q)的过高估计。通过设置w = ⌈e/ε⌉和d = ⌈ln(1/δ)⌉，我们有f̂(q) - f(q) ≤ εN的概率≥1-δ，其中N是流的长度。

计数-最小草图（Count-Min sketches）也支持范围查询，通过将范围分解为规范覆盖（canonical covers）[6]来实现。为属性

a

a

a 添加范围查询的支持会使得空间和时间复杂度大约增加一个

O

(

log

⁡

(

∣

D

(

a

)

∣

)

)

O(\log(|D(a)|))

O(log(∣D(a)∣))的因子，其中(D(a))表示该属性的域。

由于计数-最小草图（Count-Min sketches）具有吸引人的成本-精度权衡，因此在快速数据流上维护多个草图也是可能的，每个草图总结一个属性。例如，我们的运行示例（图1）的数据流可以被4个单独的计数-最小草图所概括，这使得能够对以下四种过滤条件中的任何一种进行频率估计：WHERE ipSrc=?, WHERE ipDest=?, WHERE totalLen=?, WHERE dscp=?（其中？表示谓词值）。然而，计数-最小草图不支持在同一查询中使用多个谓词，例如，WHERE ipSrc=? AND ipDest=?。如果这些谓词组合在观察数据流之前已知，那么可以为每种组合构建一个单一的草图，索引属性的串联。例如，为了支持查询WHERE ipSrc=? AND ipDest=?, 我们可以为每条记录构造一个复合键，并将其汇总到一个草图中。然后，具有两个属性作为谓词集的查询可以通过以类似方式构建查询的复合键，并对其进行查询来回答。但是，如果这些谓词组合不是事先知道的，或者如果我们想让用户能够使用任意的属性组合进行查询，那么总结具有n个属性的流需要构建

2

n

−

1

2^n – 1

2n−1个草图，以覆盖所有可能的谓词组合。因此，从时间和空间复杂度的角度来看，这种做法不是一个可行的解决方案。

K-minwise 哈希。在这项工作中，我们依靠最小散列来估计多个集合的交集的基数。所有最小哈希方案背后的关键思想是使用一个或多个哈希函数对每个集合中的所有项目进行哈希处理，并且仅保留每个哈希函数具有最小哈希值的 B 项作为每个集合的样本。然后，可以缩放不同集合的这些样本的交集大小，以估计集合交集的基数。

我们在这项工作中将要使用的K-minwise哈希算法估计集合交集的基数如下[22]：设

R

1

,

R

2

,

…

,

R

p

R_1, R_2, \ldots, R_p

R1​,R2​,…,Rp​表示我们想要估计其交集基数的

p

p

p 个集合。首先，我们通过使用全局哈希函数

g

(

⋅

)

→

{

0

,

1

}

b

g(\cdot) \rightarrow \{0, 1\}^b

g(⋅)→{0,1}b对每个集合

R

i

R_i

Ri​中的每一项进行哈希，并保留

B

B

B 个最小的哈希值来构造每个集合的摘要

S

i

S_i

Si​，其中

b

b

b 至少设置为

⌈

log

⁡

(

4

B

2.5

/

δ

)

⌉

\lceil\log(4B^{2.5}/\delta)\rceil

⌈log(4B2.5/δ)⌉。然后，我们可以从这些摘要中估计

p

p

p 个集合的交集的基数

∣

R

∩

∣

=

∣

R

1

∩

.

.

.

∩

R

p

∣

|R_{\cap}| = |R_1 \cap … \cap R_p|

∣R∩​∣=∣R1​∩…∩Rp​∣ 为

R

^

∩

=

∣

⋂

i

=

1

p

S

i

∣

∗

n

m

a

x

/

B

\hat{R}_{\cap} = |\bigcap_{i=1}^{p} S_i| * n_{max}/B

R^∩​=∣⋂i=1p​Si​∣∗nmax​/B，其中

n

m

a

x

=

max

⁡

1

≤

i

≤

p

∣

R

i

∣

n_{max} = \max_{1 \leq i \leq p} |R_i|

nmax​=max1≤i≤p​∣Ri​∣ 。当

R

^

∩

≥

3

n

m

a

x

log

⁡

(

2

p

/

δ

)

/

(

B

ϵ

2

)

\hat{R}_{\cap} \geq 3n_{max} \log(2p/\delta)/(B\epsilon^2)

R^∩​≥3nmax​log(2p/δ)/(Bϵ2)时，此估计具有((\epsilon, \delta))保证。当上述条件不满足时，可以证明一个较弱的界：以概率

1

−

δ

/

B

1 – \delta/\sqrt{B}

1−δ/B

​，有

0

≤

∣

R

∩

∣

≤

4

n

m

a

x

log

⁡

(

2

p

/

δ

)

/

(

B

ϵ

2

)

0 \leq |R_{\cap}| \leq 4n_{max} \log(2p/\delta)/(B\epsilon^2)

0≤∣R∩​∣≤4nmax​log(2p/δ)/(Bϵ2) 。

我们选择了 K-minwise 哈希而不是其他采样方法，因为该算法已被证明性能同样好或优于其他采样方法（包括 [3， 16， 18]），并且空间复杂度几乎与问题的理论下限相匹配 [22]。此外，所选算法也适用于流数据，因为样本可以增量维护。

数据流模型和支持的查询。输入数据是一个记录流，例如，类似于图1中我们持续示例的记录。设A = {𝑎1, 𝑎2, …, 𝑎|A|}表示数据流的属性（在持续示例中，ipSrc、ipDest、totalLen、dscp）。每条记录还带有唯一的记录标识符（rid），标记为𝑎0——如果没有记录键存在，可以在摄入时轻松构建此类唯一的rids（例如，使用到达计数器）。我们假设了一个地标式流查询模型[21]，其中在数据流摄入的任何时间点都可以提出查询，并且该查询针对直到那时的所有数据流到达。形式上，设

R

=

{

r

e

c

1

,

r

e

c

2

,

.

.

.

,

r

e

c

N

}

R = \{rec_1, rec_2, …, rec_N\}

R={rec1​,rec2​,…,recN​}表示直到查询时间的所有数据流到达。查询𝑞是一个计数查询，包含对A的任何子集

{

a

2

,

a

j

,

a

k

,

.

.

.

}

\{a_2, a_j, a_k, …\}

{a2​,aj​,ak​,…}的选择谓词的合取：
Count (︁ 𝑟𝑒𝑐 ∈ R | 𝑟𝑒𝑐满足𝑞 =

q

i

q_i

qi​ ∧

q

j

q_j

qj​ ∧

q

k

q_k

qk​ … )︁
其中每个谓词

q

i

q_i

qi​ 可以是单个属性

a

i

a_i

ai​ 上的范围和等值谓词的析取。

其他相关工作。用于多维数据流的最新子种群草图是Hydra[20]。在外层，Hydra 由宽度为 w 和深度为 d 的 Count-Min 草图组成，并伴随着 d 成对独立哈希函数，这些哈希函数将输入域映射到 [1 . . . w]. 此草图中的每个单元格都包含一个嵌套的通用草图 [19]，用于保存详细的统计数据。当读取 p 属性的记录时，它会在 Hydra 草图中按如下方式进行哈希处理。首先，计算记录属性的所有

2

p

−

1

2^p − 1

2p−1 种可能组合。这些组合中的每一个都定义了此记录所属的子群体。然后使用 d 哈希函数对每个组合进行哈希处理，以在外部草图（每行一个单元格）中找到相应的单元格，并最终将组合添加到包含的通用草图中。对于查询执行，查询谓词被组合起来创建一个键，然后使用相同的 d 哈希函数对其进行哈希处理，以便在外部草图中查找相应的单元格。然后，我们使用相同的键查询嵌套的通用草图，以估计频率。

在全面的实验评估中，Hydra 的表现优于其他方法，并提供交互式查询延迟。

然而，这种草图有两个关键的缺点，使其对于具有许多属性的流来说不是一个可行的选择。首先，回想一下，每条记录会以不同的键被添加到草图中

2

p

−

1

2^p − 1

2p−1次——对应于每一种可能的组合一次。如我们稍后将展示的，这种指数级的复杂度即使对于数量适中的索引属性（即，𝑝 = 4）而言，在时间复杂度方面也会成为一个挑战，从而在汇总快节奏的数据流时造成问题。其次，由于草图中添加次数的急剧增加（随𝑝呈指数增长），近似误差也随之迅速增加。我们的实验结果表明，虽然Hydra在小的𝑝值下表现出色，但其误差（以及更新时间）随着𝑝的增加而呈指数级增长。

集合基数估计技术。有人提出采用不同采样法，根据流的少量记忆样本来估计流中不同项目的数量[11]。关键思想是将样本保持在不同的级别，总内存预算为 B。每个采样水平 l 中都包含一条记录，概率为

2

−

l

2^{−l}

2−l 。当样本总数（跨所有级别）超过 B 时，将丢弃最低级别，从而释放大约一半的内存，并为更高级别的更多样本腾出空间。流中不同项目数量的 （ε， δ） 估计值可以通过将最小存活采样水平

l

m

i

n

l_{min}

lmin​ 中的项目数乘以比例因子

2

l

m

i

n

2^{l_{min}}

2lmin​ 来计算。通过利用协调抽样，还可以使用不同抽样来估计集合交集的大小。在我们的上下文中，不同采样可以用作 K-minwise 散列的替代方案，以固定内存预算逐步维护流样本。在实践中，K-minwise 哈希在我们的实验中被证明可以更好地利用可用内存。因此，我们不报告具有不同采样的实验。

两层哈希草图（2LHS）[10]被提议用于任意集合表达式的基数估计，适用于包含一般更新（记录插入和删除）的数据流。一个2LHS

X

A

X_A

XA​ 包含两层桶，并实现为一个三维数组，大小为

k

log

⁡

(

M

)

×

s

×

2

k \log(M) imes s imes 2

klog(M)×s×2，其中

k

k

k 和

s

s

s 是用户可调参数，用于控制估计精度，而

M

M

M 是输入域的大小。从概念上讲，2LHS可以被视为区别采样的泛化，可以用来给出集合并集、交集和差集在一般更新（即，翻转[21]）数据流上的

(

ϵ

,

δ

)

(\epsilon, \delta)

(ϵ,δ) 基数估计。尽管2LHS可以用作K-minwise哈希的替代方案，但在2LHS结构中存在额外的空间/时间复杂度，这是处理数据流中记录删除实际所需的。因此，我们将OmniSketch设计的重点放在K-minwise哈希上，它为仅插入的流提供了一个更简单且空间效率更高的解决方案，并在论文后面讨论了面向一般更新的可能扩展。

文献中还提出了许多其他基于采样的技术，用于估计（仅插入）记录流上的集合并集、集合交集和任意集合表达式的基数 [7， 8， 14， 15， 17]。从本质上讲，这些方法类似于 K-minwise 哈希，具有相似的复杂性和理论保证。原则上，这些都可以与 OmniSketch 一起使用，以构建嵌套草图。但是，需要注意的是，这些方法（包括 K-minwise 哈希）都不支持基于谓词的过滤。因此，它们不能直接用于估计带有谓词的聚合查询的答案，这是我们工作的主要重点。

3 OMNISKETCH：使用任意谓词估计频率

我们现在介绍OmniSketch，这是一种允许对快速数据流上的带有谓词的查询进行高效频率估计的草图。我们将逐步构建最终的草图，分为三个连续的步骤。最初，我们描述了标准计数-最小草图的一种扩展，称为S0，它在单元格中保持额外的数据。利用这些附加信息，可以通过对计数最小估计器的直接推广来估计涉及谓词的基数。然后，在保持S0草图结构不变的情况下，我们提出了一种改进的估计算法及其相应的理论分析，以在不增加额外复杂度的情况下收紧误差界限。我们将新的草图估计器称为

S

0

∩

S0_∩

S0∩​，以区别于早期的估计器（称为

S

0

m

i

n

S0_{min}

S0min​）。最后，我们介绍了最终的OmniSketch（S1），它将

S

0

∩

S0_∩

S0∩​与一种采样技术相结合，以确保亚线性的空间复杂度。与以往的工作不同，所有三种草图都允许非常高效的更新（具有对数复杂度），因此可以轻松处理快节奏的数据流。

所有三种草图都基于一个共同的架构：每种草图都由一系列子草图组成，每个可搜索属性（即希望支持谓词的属性）分配有一个草图。我们将这些子草图称为属性草图，并用

C

M

1

,

C

M

2

,

.

.

.

,

C

M

∣

A

∣

CM_1, CM_2, …, CM_{|A|}

CM1​,CM2​,…,CM∣A∣​表示它们，其中A对应于可搜索属性的集合。每个𝐶𝑀𝑖是一个大小为𝑤×𝑑的数组，附带了𝑑个成对独立的哈希函数

h

i

1

(

⋅

)

,

h

i

2

(

⋅

)

,

.

.

.

h

i

d

(

⋅

)

h^1_i(\cdot),h^2_i(\cdot),…h^d_i(\cdot)

hi1​(⋅),hi2​(⋅),…hid​(⋅)（类似于计数-最小草图）。然而，与传统的CM草图不同，𝐶𝑀𝑖中的每个单元格包含记录标识符列表（rids），或是它们的指纹。根据记录在相应属性上的值，rids被放置或哈希到每个草图中。在执行查询时，会查询与查询谓词对应的属性草图，并对这些草图检索到的记录标识符进行交集运算，以计算答案的估计值。图2说明了一个样本数据集的通用草图架构，该数据集具有可搜索属性：。三种草图之间的差异在于：(a) 记录标识符如何在属性草图中被抽样和存储，以及 (b) 支持估计算法的理论，这影响了界限的紧密性。

在接下来的讨论中，我们使用A = {𝑎1, 𝑎2, …, 𝑎|A|}表示可搜索属性的集合，𝑞表示含有𝑝个谓词的查询，而𝑞𝑖表示属性𝑎𝑖 ∈ A的谓词。为了简化表述，除非特别说明，我们假定每个谓词𝑞𝑖是在属性𝑎𝑖上对常数值𝑣𝑞𝑖的等值谓词；也就是说，𝑞𝑖 := (𝑎𝑖 =

v

q

i

v_{qi}

vqi​)。每个属性𝑎𝑖的域用D(𝑎𝑖)表示。

不失一般性，我们假设𝑞包含了A的所有属性，即𝑝 = |A|（如果某些属性没有包含在查询中，我们在执行查询时简单地忽略相应的草图）；通常情况下，𝑝 ≤ |A|。我们用表1总结了常用的符号。

3.1 Sketch S0：Count-Min with rid-sets 用于估计带有谓词的查询

初始化。在初始化阶段，我们随机均匀地选择|A|×𝑑个成对独立的哈希函数 ℎ11(·), ℎ12(·), …, ℎ𝑑|A|(·)，其中每个函数满足 ℎ𝑗𝑖(): D(𝑎𝑖) → {1, …, 𝑤} 的映射规则。此外，我们构建了|A|个大小为𝑤×𝑑的数组𝐶𝑀1, 𝐶𝑀2, …, 𝐶𝑀|A|，并将它们的每一个单元格初始化为包含一个空链表。为了获得估计值的(𝜖, 𝛿)保证，我们将𝑤设定为1 + ⌈𝑒/𝜖⌉ = Θ(1/𝜖)，并将𝑑设定为⌈ln(1/𝛿)⌉。

插入。一条新记录

r

r

r 需要被添加到所有的

∣

A

∣

|A|

∣A∣ 个草图中。我们使用

r

i

r_i

ri​ 表示记录

r

r

r 在属性

a

i

a_i

ai​ 上的值，而

r

0

r_0

r0​ 则表示其唯一的记录标识符（rid）。对于每个可搜索属性

a

i

a_i

ai​ 和每一行

j

=

{

1

,

.

.

.

,

d

}

j = \{1, …, d\}

j={1,…,d} ，我们将

r

0

r_0

r0​ 添加到位置

C

M

i

[

j

,

h

i

j

(

r

i

)

]

CM_i[j, h^j_i(r_i)]

CMi​[j,hij​(ri​)] 处的所有链表中。

请注意，根据定义，S0 结构并不是严格意义上的“草图”，因为通过存储完整的 rid-set，它需要在流长度 N 中呈线性的空间。S0 执行的唯一汇总是通过哈希到 CountMin 存储桶中“模糊”单个属性值。尽管如此，它还是为我们最终的 OmniSketch 解决方案提供了概念上有用的第一步。

S0min估计器。设

f

(

q

)

f(q)

f(q)表示满足查询

q

q

q 中所有谓词的记录数目。遵循传统的计数-最小（Count-Min）估计程序[6]，我们可以按如下方式计算一个估计值

f

^

(

q

)

\hat{f}(q)

f^​(q) ：对于每一行

j

=

{

1

,

.

.

.

,

d

}

j = \{1, …, d\}

j={1,…,d} ，我们计算存储在单元格

C

M

1

[

j

,

h

1

j

(

v

q

1

)

]

,

C

M

2

[

j

,

h

2

j

(

v

q

2

)

]

,

.

.

.

,

C

M

p

[

j

,

h

p

j

(

v

q

p

)

]

CM_1[j, h^j_1(vq_1)], CM_2[j, h^j_2(vq_2)], …, CM_p[j, h^j_p(vq_p)]

CM1​[j,h1j​(vq1​)],CM2​[j,h2j​(vq2​)],…,CMp​[j,hpj​(vqp​)] 中所有记录的交集大小。我们对(d)行重复这一过程，并将最小值返回作为一个估计值。形式上表示如下：

f

^

(

q

)

=

min

⁡

j

=

{

1

,

.

.

.

,

d

}

∣

⋂

q

i

∈

q

C

M

i

[

j

,

h

j

(

v

q

i

)

]

∣

(

1

)

\hat{f}(q) = \min_{j=\{1,…,d\}} \left| \bigcap_{q_i \in q} CM_i [ j, h^j(v_{qi}) ] \right| \qquad (1)

f^​(q)=j={1,…,d}min​

​qi​∈q⋂​CMi​[j,hj(vqi​)]

​(1)

直观地说，交集将包含满足查询的所有记录 r 的 rid，因为对于所有谓词，这些记录将始终在与查询谓词相同的单元格上进行哈希处理，但是，交集也可能包含一些误报，即由于一个或多个随机冲突而在

C

M

i

[

j

，

h

i

j

（

v

q

i

）

]

CM_i [ j， h^j_i （v_{qi} ）]

CMi​[j，hij​（vqi​）] 中散列的记录。通过取所有 d 行的最小交集大小，我们尝试将此类误报的影响降至最低。

误差边界。以下引理为方程 1 的估计量提供了概率保证。

引理3.1. 设

f

^

(

q

)

\hat{f}(q)

f^​(q) 是根据公式1在使用

d

=

⌈

ln

⁡

(

1

δ

)

⌉

d = \lceil\ln(\frac{1}{\delta})\rceil

d=⌈ln(δ1​)⌉，

w

=

1

+

⌈

e

ϵ

⌉

w = 1 + \lceil\frac{e}{\epsilon}\rceil

w=1+⌈ϵe​⌉ 构造的草图上提供的估计值。对于含有

p

p

p 个谓词的查询

q

q

q ：

P

r

(

∣

f

^

(

q

)

−

f

(

q

)

∣

≤

ϵ

N

)

≥

1

−

δ

(

2

)

Pr\left(\left|\hat{f}(q) – f(q)\right| \leq \epsilon N\right) \geq 1 – \delta \qquad(2)

Pr(

​f^​(q)−f(q)

​≤ϵN)≥1−δ(2)

证明。考虑行

j

∈

{

1

,

.

.

.

,

d

}

j \in \{1, …, d\}

j∈{1,…,d}。我们定义指示变量

I

y

,

j

I_{y,j}

Iy,j​，当所有满足以下条件的记录(y)时，其值为1：

∀

q

i

∈

q

[

h

i

j

(

v

q

i

)

=

h

i

j

(

y

i

)
  

]

∧

∃

q

i

∈

q

[

v

q

i

≠

y

i

]

{\forall q_i \in q }[h^j_i(vq_i) = h^j_i(y_i) \;] \land \exists q_i \in q [v_{qi}
eq y_i]

∀qi​∈q[hij​(vqi​)=hij​(yi​)]∧∃qi​∈q[vqi​=yi​]

非正式地说，上述条件对于所有误报记录成立，即，那些包含在交集中但并不完全满足查询的记录。另外，变量

X

j

=

∑

y

=

1

N

−

f

(

q

)

I

y

,

j

X_j = \sum_{y=1}^{N-f(q)} I_{y,j}

Xj​=∑y=1N−f(q)​Iy,j​ 是对行

j

j

j 的这些误报的计数器。

回想一下，第 j 行的估计量如下：

f

^

j

(

q

)

=

∣

R

∩

j

∣

\hat{f}^j(q) = |R^j_∩|

f^​j(q)=∣R∩j​∣，其中

R

∩

j

R^j_∩

R∩j​ 表示位置

h

i

j

(

v

q

i

)

h^j_i(v_{qi})

hij​(vqi​) 处的单元格的交集，因为 i = {1， . . . ， p}。我们需要证明：（a）所有满足所有谓词的记录都将包含在

R

∩

j

R^j_∩

R∩j​中，即不会有假阴性，并且（b）假阳性的总数

X

X

X 是w.h.p.的上限。

对于(a)，注意到对于满足

y

i

=

v

q

i

y_i = v_{q_i}

yi​=vqi​​的任意记录

y

y

y ，其中

i

=

{

1

,

…

,

p

}

i = \{1, \ldots, p\}

i={1,…,p}，我们将有

y

i

=

v

q

i

⇒

h

i

j

(

y

i

)

=

h

i

j

(

v

q

i

)

y_i = v_{q_i} \Rightarrow h^j_{i}(y_i) = h^j_{i}(v_{q_i})

yi​=vqi​​⇒hij​(yi​)=hij​(vqi​​)。因此，满足所有谓词的所有记录都将被包含在

R

∩

j

R^j_ \cap

R∩j​中。

对于(b)，如果对于所有属性

y

i

y_i

yi​，当

y

i

≠

v

q

i

y_i
eq v_{q_i}

yi​=vqi​​时，我们有

h

i

j

(

y

i

)

=

h

i

j

(

v

q

i

)

h^j_{i}(y_i) = h^j_{i}(v_{q_i})

hij​(yi​)=hij​(vqi​​)，则记录将是错误的正例并使

X

j

X_j

Xj​的值增加1。令

X

k

j

X^j_{k}

Xkj​表示在

R

∩

j

R^j_\cap

R∩j​中满足恰好

p

−

k

p-k

p−k个谓词的记录数量，即，它们不满足

p

p

p个谓词中的

k

k

k个，但由于哈希冲突，它们仍被算法检索。那么，

X

j

=

∑

k

=

1

p

X

k

j

X_j = \sum^{p}_{k=1} X^j_{k}

Xj​=∑k=1p​Xkj​。

根据散列函数的构造，具有

y

i

≠

v

q

i

y_i
eq v_{qi}

yi​=vqi​的记录

y

y

y将以概率1/w使得

h

j

i

(

y

i

)

=

h

j

i

(

v

q

i

)

h_{ji}(y_i) = h_{ji}(v_{qi})

hji​(yi​)=hji​(vqi​)。由于散列函数是两两独立的，一个与查询

q

q

q在

k

k

k个属性上不同的记录散列到相同单元格的概率是

1

/

w

k

1/w^k

1/wk。因此，

E

[

X

k

j

]

≤

(

N

−

f

(

q

)

)

/

w

k

\mathbb{E}[X^j_{k}] \leq (N – f(q))/w^k

E[Xkj​]≤(N−f(q))/wk，并且

E

[

X

j

]

=

∑

k

=

1

p

E

[

X

k

j

]

≤

(

N

−

f

(

q

)

)

∗

(

1

/

w

+

1

/

w

2

+

.

.

.

+

1

/

w

p

)

=

(

N

−

f

(

q

)

)

∗

(

1

−

(

1

/

w

)

p

)

/

(

w

−

1

)

\mathbb{E}[X^j] = \sum^{p}_{k=1} \mathbb{E}[X^j_{k}] \leq (N – f(q))*(1/w + 1/w^2 + … + 1/w^p) = (N – f(q))*(1 – (1/w)^p)/(w – 1)

E[Xj]=∑k=1p​E[Xkj​]≤(N−f(q))∗(1/w+1/w2+…+1/wp)=(N−f(q))∗(1−(1/w)p)/(w−1)。通过设置

w

=

1

+

⌈

e

/

ϵ

⌉

w = 1 + \lceil e/\epsilon\rceil

w=1+⌈e/ϵ⌉，我们得到

E

[

X

]

=

(

N

−

f

(

q

)

)

/

e

∗

(

1

−

ϵ

p

)

/

ϵ

≤

ϵ

(

N

−

f

(

q

)

)

/

e

≤

ϵ

N

/

e

\mathbb{E}[X] = (N – f(q))/e * (1 – \epsilon^p)/\epsilon \leq \epsilon(N – f(q))/e \leq \epsilon N/e

E[X]=(N−f(q))/e∗(1−ϵp)/ϵ≤ϵ(N−f(q))/e≤ϵN/e。

注意到我们有d行，每行使用不同的散列函数。根据马尔可夫不等式，我们有

[

P

r

[

X

≥

ϵ

(

N

−

f

(

q

)

)

]

=

P

r

[

∀

j

∈

[

1…

d

]

.

f

^

j

(

q

)

>

f

(

q

)

+

ϵ

N

]

=

P

r

[

∀

j

∈

[

1…

d

]

.

X

j

>

e

E

[

X

]

]

f(q) + \epsilon N] = Pr[\forall_{j \in [1…d]}. X_j > eE[X]] < e^{-d}]

[Pr[X≥ϵ(N−f(q))]=Pr[∀j∈[1…d]​.f^​j​(q)>f(q)+ϵN]=Pr[∀j∈[1…d]​.Xj​>eE[X]]<e−d]，其中

f

(

q

)

f(q)

f(q)表示真实的答案，而

X

j

X_j

Xj​表示在第j行的误报数量，即

X

j

=

f

^

j

(

q

)

−

f

(

q

)

X_j = \hat{f}^j (q) – f(q)

Xj​=f^​j(q)−f(q)。最后的界限可以通过设置

d

=

⌈

ln

⁡

(

1

/

δ

)

⌉

d = \lceil \ln(1/\delta) \rceil

d=⌈ln(1/δ)⌉来得到。

S0∩：一个改进的估计器。S0min估计器基于标准Count-Min草图[6]中的传统估算逻辑；也就是说，它按行产生估计，并取所有d行估计的最小值。与标准的Count-Min估算相似，很容易看出S0min只能由于哈希桶碰撞（误报）而高估真实的计数值。然而，与标准的Count-Min相比，S0中的每个桶包含更多可以利用的详细信息，以提供更紧密的估计（即，具有较少的误报）。关键的观察点在于，通过构建S0的方式，满足完整查询的每条记录最终会出现在该查询的所有d行以及所有p个谓词的单元格中，而误报则只可能出现在少数几行中。因此，在不修改草图构造或空间/时间复杂度的情况下，我们可以通过去掉跨行的最小值操作，仅仅对所有d行返回的rid集进行交集运算，就能获得一个更紧密的估计器。我们将这个更紧密的S0估计器称为S0∩，并正式定义如下：

f

^

(

q

)

=

∣

⋂

i

=

{

1…

p

}

,

j

=

{

1…

d

}

C

M

i

[

j

,

h

j

i

(

v

q

i

)

]

∣

(

3

)

\hat{f}(q) = \left| \bigcap_{i=\{1…p\},j=\{1…d\}} CM_i[j, h_j^i(v_{q_i})] \right| \qquad (3)

f^​(q)=

​i={1…p},j={1…d}⋂​CMi​[j,hji​(vqi​​)]

​(3)
显然，这个新的S0∩估计器也仅能由于哈希碰撞而高估真实的计数值——同时，它保证了更少的误报，因为它总是小于或等于公式1中的S0min估计。我们现在展示S0∩更强的误差保证，证明它允许我们在不改变草图的空间复杂度的情况下，将误差限定在(\epsilon d (N – f(q)))而不是(\epsilon (N – f(q)))。

引理3.2. 设

f

^

(

q

)

\hat{f}(q)

f^​(q)是使用公式3在由

d

=

⌈

ln

⁡

(

1

δ

)

⌉

d = \lceil \ln(\frac{1}{\delta}) \rceil

d=⌈ln(δ1​)⌉，

w

=

1

+

⌈

e

ϵ

⌉

w = 1 + \lceil e^{\epsilon} \rceil

w=1+⌈eϵ⌉构建的草图上提供的估计值。对于有p个谓词的查询q：

P

(

∣

f

^

(

q

)

−

f

(

q

)

∣

≤

ϵ

d

(

N

−

f

(

q

)

)

≤

ϵ

d

N

)

≥

1

−

δ

P\left( \left| \hat{f}(q) – f(q) \right| \leq \epsilon^d (N – f(q)) \leq \epsilon^d N \right) \geq 1-\delta

P(

​f^​(q)−f(q)

​≤ϵd(N−f(q))≤ϵdN)≥1−δ
证明。证明类似于引理3.1的证明。我们定义指示变量

I

y

I_y

Iy​，当所有记录y满足以下条件时，它的值为1：

∀

q

i

∈

q

[

∀

1

≤

j

≤

d

[

h

j

i

(

v

q

i

)

=

h

j

i

(

y

i

)

]

∧

∃

q

i

∈

q

[

v

q

i

≠

y

i

]

]

\forall_{q_i \in q} [\forall _{1 \leq j \leq d} [h_j^i(v_{q_i}) = h_j^i(y_i)] \land \exists_{q_i \in q} [v_{q_i}
eq y_i]]

∀qi​∈q​[∀1≤j≤d​[hji​(vqi​​)=hji​(yi​)]∧∃qi​∈q​[vqi​​=yi​]]
非正式地说，

I

y

I_y

Iy​对于所有假正例记录变为1，即那些在所有d行和所有p个谓词下，哈希到与查询谓词值相同的单元格的记录。此外，

X

=

∑

y

=

1

N

−

f

(

q

)

I

y

X = \sum_{y=1}^{N-f(q)} I_y

X=∑y=1N−f(q)​Iy​是对假正例记录总数的计数器。

我们将证明以下两点：(a) 所有满足所有谓词的记录都将包含在

⋂

j

=

1

d

R

∩

j

\bigcap_{j=1}^{d} R^j_∩

⋂j=1d​R∩j​ 中，即不会有假阴性；以及，(b) 假阳性记录的数量

X

X

X 高概率下有界。

对于(a)，注意到对于任何记录

y

y

y 满足

y

i

=

v

q

i

y_i = v_{q_i}

yi​=vqi​​ 对于

i

=

{

1…

p

}

i = \{1 … p\}

i={1…p}，我们会有

y

i

=

v

q

i

⇒

∀

1

≤

j

≤

d

[

h

i

j

(

y

i

)

=

h

i

j

(

v

q

i

)

]

y_i = v_{q_i} \Rightarrow \forall _{1 \leq j \leq d} [h^j_i(y_i) = h^j_i(v_{q_i})]

yi​=vqi​​⇒∀1≤j≤d​[hij​(yi​)=hij​(vqi​​)]。因此，所有满足所有谓词的记录都将包含在所有

R

∩

j

R^j_∩

R∩j​ 的交集中，记作

R

∩

R_∩

R∩​。

对于(b)，一个记录

y

y

y 如果对于所有属性

y

i

y_i

yi​ （其中

y

i

≠

v

q

i

y_i
eq v_{q_i}

yi​=vqi​​）和所有行

j

∈

{

1…

d

}

j \in \{1 … d\}

j∈{1…d}，它与

h

i

j

(

v

q

i

)

h_i^j(v_{q_i})

hij​(vqi​​) 发生冲突，即

h

i

j

(

y

i

)

=

h

i

j

(

v

q

i

)

h_i^j(y_i) = h_i^j(v_{q_i})

hij​(yi​)=hij​(vqi​​)，则会增加

X

X

X 的值。在单一行

j

j

j 上发生这种冲突的概率是

P

r

[

h

i

j

(

y

i

)

=

h

i

j

(

v

q

i

)

]

=

1

/

w

Pr[h_i^j(y_i) = h_i^j(v_{q_i})] = 1/w

Pr[hij​(yi​)=hij​(vqi​​)]=1/w。此外，由于哈希函数在草图行之间是独立的，一个记录在所有

d

d

d 行

j

j

j 上与查询发生碰撞的概率将是

1

/

w

d

1/w^d

1/wd。

令

X

k

X_k

Xk​ 表示来自

R

R

R 的记录数量，这些记录恰好满足

p

−

k

p-k

p−k 个谓词。那么，

E

[

X

k

]

≤

(

N

−

f

(

q

)

)

/

w

k

d

E[X_k] \leq (N – f(q))/w^{kd}

E[Xk​]≤(N−f(q))/wkd，并且

E

[

X

]

=

∑

k

=

1

p

E

[

X

k

]

≤

(

N

−

f

(

q

)

)

∑

k

=

1

p

1

/

w

k

d

=

(

N

−

f

(

q

)

)

1

−

w

−

d

(

p

+

1

)

w

d

−

1

<

(

N

−

f

(

q

)

)

/

(

w

d

−

1

)

E[X] = \sum_{k=1}^{p} E[X_k] \leq (N – f(q)) \sum_{k=1}^{p} 1/w^{kd} = (N – f(q)) \frac{1-w^{-d(p+1)}}{w^d-1} < (N – f(q))/(w^d – 1)

E[X]=∑k=1p​E[Xk​]≤(N−f(q))∑k=1p​1/wkd=(N−f(q))wd−11−w−d(p+1)​<(N−f(q))/(wd−1)。通过设置

w

=

1

+

⌈

e

/

ϵ

⌉

w = 1 + \lceil e/\epsilon \rceil

w=1+⌈e/ϵ⌉，我们得到

E

[

X

]

≤

(

N

−

f

(

q

)

)

/

(

(

1

+

e

/

ϵ

)

d

−

1

)

≤

ϵ

d

(

N

−

f

(

q

)

)

/

e

d

E[X] \leq (N – f(q))/((1 + e/\epsilon)^d – 1) \leq \epsilon^d (N – f(q))/e^d

E[X]≤(N−f(q))/((1+e/ϵ)d−1)≤ϵd(N−f(q))/ed。