康瑞部落

在物联网场景中，大量的浮点时间序列数据以流的方式生成，并在有限的带宽内传输，用于实时分析。为了提高效率，在传输前可以对数据进行压缩。但现有的浮点压缩方法要么是延迟较长的批处理压缩，要么是允许一定误差情况下压缩率差强人意的流式无损压缩。这两类算法都无法同时适应实时性要求和高压缩率要求。本次为大家带来重庆大学时空实验室和京东智能城市研究院联手在数据库领域顶级会议SIGMOD 2025发表的文章《Serf: Streaming Error-Bounded Floating-Point Compression》。

一. 背景

近年来，物联网得到了显著发展，传感器被分布在感兴趣区域的各个位置。如图1所示，在一个典型的物联网场景中，大量的浮点时间序列数据（简称时间序列）由各种传感器以流式方式持续生成，然后传输到服务器以进行进一步的实时分析和可视化。

图1. 流式误差有界浮点压缩的场景

这样的场景具有带宽有限、允许容错、有实时性要求的特点。而现有的时序数据压缩算法，可以分为三个主要类别：1) 批式无损压缩，2) 批式有损压缩， 3) 流式无损压缩。

批量无损压缩算法（例如，ALP）可以在不损失任何信息的情况下压缩时间序列，而批量有损压缩算法（例如，SZ 、MOST和 Machete）通常可以牺牲一些误差来获得更好的压缩率。这些批量压缩算法存在三个局限性。1) 采样率低的时候延迟长。它们需要等待批处理中的所有记录准备就绪，然后才能实际执行压缩操作。如果数据采样率较低，批量压缩将导致较长的延迟，这不符合上述实时性要求。2) 批量大小较小时性能较差。为了减少延迟，另一种解决方案是采用小批量技术，例如，将批量大小设置为小于50。然而，大多数批量压缩算法在面对小批量数据时的性能会急剧下降，因为它们难以发现记录之间的共享信息。3) 批处理中缓存记录的额外内存消耗。批量压缩算法需要在内存中缓存批处理中的所有记录，这可能会给边缘设备带来一定的压力，因为微型传感器设备的内存大小通常有限，注意这些有限的内存还需要支持某些程序的执行，例如压缩器和传输模块。

流式无损压缩算法可以在生成每条记录后立即对其进行压缩，同时保留所有信息。该领域中的几种最先进的方法，例如 Gorilla、Chimp 和 Elf ，都是基于对连续记录进行异或运算，因为时间序列中的连续记录通常变化不大，因此产生的异或值具有许多前导零或尾随零。然而，由于无损约束，当允许某些误差时，这些算法通常无法达到令人满意的压缩率。

据调研，目前还没有针对时间序列的流式有损压缩算法。流式有损压缩算法不仅解决了批量算法遇到的所有限制，而且与无损算法相比，实现了显著的压缩率。设计一种高效且紧凑的流式有损压缩算法将面临以下两个挑战。挑战一：如何在流式环境中实现具有误差界限保证的优秀压缩率？流式处理要求我们在每条记录生成后对其进行处理，这使得发现记录之间的共享信息变得困难。挑战二：如何在传感器有限的资源下确保高效率？注意传感器设备的计算和存储资源非常宝贵。因此，我们必须高效地处理数据，以避免堆积。

为了方便您的阅读和理解，给出下表：

表1. 文中符号及其含义

二. 方法介绍

2.1  基本方法Serf-Qt

Serf-Qt是一种基于量化的基本流式传输方法，其框架如图2所示。

图2. Serf-Qt的框架

2.1.1量化器和反量化器

量化直接解释就是将浮点数值转换为整数，因为相比于浮点数值，整数更容易被压缩。假设原始数值为 ⟨v₁, v₂, ...⟩，量化后的整数为⟨q₁, q₂, ...⟩，量化器执行以下操作：

其中[*]是将浮点数值舍入为整数的运算，ϵ_a是用户给定的绝对误差界限，而p_i是v_i的预测值（见下一段)。

给定q_i，反量化器通过以下方式计算恢复值v′：

可以证明 |v_i−v_i′| ≤ ϵ_a，即恢复值v_i′ 严格满足绝对误差界约束。由于时间序列中两个连续的值通常变化很小，我们可以简单地令p_i= v_i-1′（我们可以在压缩和解压缩期间计算v_i-1′）。特别地，v₀′ = v₀ = 0。

2.1.2 编码器和解码器

现有的基于量化的压缩方法只能在批处理模式下工作，因为它们使用批处理策略对量化的整数进行编码，例如，Huffman编码或FSE（有限状态熵）编码。为了支持流式压缩，我们建议用流式编码器替换批处理编码器。具体而言，由于v_i和p_i之间的差异很小，即q_i倾向于分布在0附近，因此我们采用Elias gamma编码，这是一种自解释的流式编码方法，适合于压缩小数值。为了适应Elias gamma编码只能对正整数进行编码这一事实，我们首先基于Zigzag编码将q_i转换为正整数，然后使用Elias gamma编码对结果进行编码，即：

此处，ZigzagEn(q_i ) = (q_i<< 1) xor (q_i>> 63)，其中xor是按位异或运算。如果q_i= 0，那么ZigzagEn(q_i) = 0，因此我们需要额外加 1 以确保 Elias gamma 编码的输入为正数。假设N_i= ZigzagEn(q_i) + 1，Elias gamma 编码写入⌊log₂N_i⌋个零，然后附加N_i的二进制数字。例如，如果q_i= 5，那么N_i= ZigzagEn(q_i) + 1 = 11，其中⌊log₂N_i⌋= 3，并且N_i的二进制数字是(1011)₂。因此，code_i= EliasGammaEn(N_i) = (000 1011)_2。

解码器是编码器的逆过程。它首先使用Elias gamma解码方法解码code_i，然后使用Zigzag解码方法解码结果，即：

具体而言，Elias gamma解码首先读取并计数code_i的二进制数字中的零，直到遇到第一个1（假设零的计数为n_i），然后读取剩余的n_i位。首次读取的1和n_i位组合成解码结果。例如，如果code_i= (000 1011)₂，则零的计数n_i为3，因此除了已读取的1之外，我们还需要再读取3位，形成N_i= EliasGammaDe(code_i) = (1011)₂ = 11。之后，我们减去1以抵消前面公式(3)添加的1。假设x是Zigzag解码的输入数字，则ZigzagDe(x) = (x >>> 1) xor (−(x&1))。

2.1.3讨论

Serf-Qt速度极快，对于给定的值，其时间复杂度和空间复杂度均为O(1)。然而，Serf-Qt不支持相对误差有界压缩，因为公式（2）中，我们需要知道依赖于原始值的误差界限来进行相对误差有界压缩，而这是不可用的。此外，当ϵ_a很小时，Serf-Qt的性能会很差，因为根据公式 (1)，q_i会趋于变大。在极端情况下，如果ϵ_a足够小，q_i可能会溢出（即超出整数可以表示的范围），这使得Serf-Qt失效。

2.2 基于异或的方法Serf-XOR

为了解决Serf-Qt的问题，文章提出了一种基于异或运算的方法Serf-XOR。据调研这是第一个基于异或运算的有损浮点压缩方法。

2.2.1 主要思想

现有的基于异或的浮点压缩方法基于以下假设：时间序列中任意两个连续的值变化不大，因此它们的异或值往往包含许多前导零和尾随零。然而，这个假设并不总是成立。首先，如果两个连续的值具有不同的符号（例如，图3(a)中显示的-0.96和2.02），他们的异或值不包含任何前导零。其次，即使两个连续的值具有相同的符号，如果它们的指数表示形式有突变（例如，图3(b)中显示的0.98和2.09），则前导零仍然非常少。第三，在大多数情况下，尾随零实际上相当少（例如，图3(a)中没有尾随0，图3(b)中的2个尾随0）。前导零和尾随零的缺乏会导致较差的压缩性能。为此，我们提出一种移位技术来增加前导零，以及一种近似技术来增加尾随零。

图3. Serf-XOR的动机

图4给出了Serf-XOR的框架，它包含两个主要部分：Serf-XOR压缩器和Serf-XOR解压缩器。

图4.Serf-XOR的框架

2.2.2  Serf-XOR压缩器

在 Serf-XOR 压缩器中，浮点数值 ⟨v₁, v₂,v₃ ...⟩ 依次流入移位器 (Shifter)，获得一个具有相同符号和相同指数的移位数值序列 ⟨s₁, s₂, s₃...⟩。之后，近似器(Approximator) 将移位数值逐一转换为近似数值序列 ⟨a₁, a₂, a₃...⟩。每个近似数值 a_i（除了第一个数值 a₁)）与其前一个数值  a_i-1执行异或 (XOR) 操作，从而产生一个具有大量前导零和尾随零的异或数值序列 ⟨xor₁,  xor₂, xor₃...⟩，该序列可以通过编码器 (Encoder) 进行压缩。

移位器：移位器给每个v_i增加一个整数偏移量λ，从而获得一个移位后的值s_i=v_i +λ，该值与其他移位后的值具有相同的符号（即正数）和相同的指数。因此，任何两个连续的移位后的值都可以产生一个具有许多前导零的异或值。但是如何确定一个合适的λ呢？

图5. 添加偏移量会导致信息丢失

一方面，λ应该足够大，以使所有s_i为正数并具有相同的指数。另一方面，如图6所示，添加偏移量可能会导致尾数右移，从而导致一些信息丢失。较大的偏移量通常意味着更多的信息丢失。在极端情况下，如果λ过大，s_i可能会溢出。为此，我们令λ为使所有s_i落在范围[2^u, 2^u+1)内的最小值，其中u是一个正整数，如图6所示。我们给出以下定理来找到 u和 λ。

图6. 位移器图示

定理 1。 给定一个时间序列TS=⟨v₁, v₂, ...⟩，假设 ∀v_i ∈TS，min ≤ v_i ≤ max。如果 u = ⌈log₂(⌊max⌋− ⌊min⌋ + 1)⌉ 且 λ = 2^u− ⌊min⌋，我们可以保证所有平移后的值s_i=v_i +λ都在范围 [2^u, 2^u+1) 内，并且λ同时是最小的。

近似器：在此模块中，对于每个位移值s_i，我们尝试找到一个近似值a_i∈ [s_i-ϵ,s_i+ϵ]，使得a_i和a_i-1共享最多的后缀位，即它们的异或结果具有最多的尾随零。这里，ϵ= ϵ_a（即，基于绝对误差界限）或ϵ=ϵ_r× |v_i|（即，基于相对误差界限）。

图9展示了近似器的基本思想，其中a_i-1= 2.535，s_i= 2.81，且ϵ= ϵ_a= 0.01。为了找到a_i∈ [s_i-ϵ,s_i+ϵ]，我们可以简单地将s_i的后45位设置为a_i-1的后45位，从而得到a_i = 2.800625（即，a_i由s_i的前19位和a_i-1的后45位组成，表示为a_i = pre₁₉ ⊢ suf₄₅。我们称s_i 为前缀锚点，a_i-1 为后缀锚点）。通过对a_i和a_i-1进行异或操作，我们可以得到一个异或值，该值具有许多前导零和尾随零。在解压缩期间，由于a_i∈[s_i-ϵ,s_i+ϵ]，我们有v_i'= a_i-λ∈[s_i-λ-ϵ,s_i-λ+ϵ]，即v_i'∈[v_i-ϵ,v_i+ϵ]，这满足误差界限的要求。下面介绍如何有效地找到一个合格的a_i。

一个直接的解决方案是迭代地检查a_i=pre_bn-j⊢ suf_j是否满足误差界限要求，其中