Page 353 - 《软件学报》2025年第8期
P. 353
3776 软件学报 2025 年第 36 卷第 8 期
图 4 压缩策略示例
不同用户存在不同的查询性能与内存占用的需求, 可通过设定不同的 ε, 限制合并区间的概率, 从而实现索引
的查询效率与内存占用的折中. ε 越小, 区间合并的概率越低, 被压缩的叶子节点模型会越少, 叶子节点的整体预
测误差就越不受影响, 对查询效率的影响也就越小; 相反, ε 越大, 区间合并的概率越高, 叶子节点的整体误差就越
大, 相应地会导致压缩后的叶子节点模型的预测误差更大, 对查询效率的影响也就越大. 特别地, 当 ε 设定为 0 时,
表示不压缩任何叶子节点模型参数, 不做有损压缩以达到最优的查询效率; 当 ε 设定为 1 时, 表示只要有重叠就合
并, 即最大程度地进行有损压缩以获取最小的内存占用.
例 4: 如图 4 所示, 叶子节点 N n−5 , N n−4 , N n−3 , N n−2 , N n−1 未使用 LPC 时, 用最小二乘法计算的斜率分别为 2.58,
2 2 2 2 2
0.54, 3.12, 0.71, 2.28. 若使用 ε=1 的 LPC, 首先使用线性插值法计算 N 2 n−5 , N n−4 , N 2 n−3 , N n−2 , N 2 n−1 的斜率区间, 分别
2
2
为 [1.67, 3.33], [0.4, 0.57], [2.94, 4.0], [0.5, 0.92], [1.47, 3.18], 根据斜率的最小值对斜率区间排序, 排序结果为 [0.4,
0.57], [0.5, 0.92], [1.47, 3.18], [1.67, 3.33], [2.94, 4.0]. 之后, 遍历所有斜率区间. 区间 [0.4, 0.57] 与区间 [0.5, 0.92] 有
重叠, 合并这两个区间, 合并后的斜率区间为 [0.5, 0.57]. 区间 [0.5, 0.57] 与 [1.47, 2.91] 不重叠, 则不再继续合并,
叶子节点 N n−4 , N n−2 共享相同的斜率, 斜率值为区间 [0.5, 0.57] 中的一个随机值. 同理, 区间 [1.47, 3.18], [1.67,
2 2
3.33], [2.94, 4.0] 有重叠, 合并后的斜率区间为 [2.94, 3.18].
2.2 索引的更新策略
2.2.1 近似拟合方法 AFit
定义 3 (显著性水平 α). 显著性水平 α 是估计总体参数落在某一区间内出现失误的概率 α∈(0,1).
定义 4 (置信区间). 给定显著性水平 α, 若模型的斜率、截距或键 k 等参数落在使用 t 分布计算其所属区间内
的概率为 1–α, 则该区间称为参数的置信区间.
定义 5 (近似拟合). 给定显著性水平 α, 使用 t 分布和统计分析计算模型参数 (斜率和截距) 的置信区间. 拟合
更新缓冲区模型时, 在置信区间内随机选择一种参数值作为模型参数即为一次近似拟合.
定理 2. 在显著性水平 α 下, 近似拟合的模型参数与实际数据对应的模型参数之间的最大预测误差 Errmax 满
足如下不等式:
√ √
t ·σ 1 ¯ x 2 t ·σ 1 ¯ x 2
|x| min · √ − t ·σ· + ⩽ Errmax ⩽ |x| max · √ + t ·σ· + (7)
n n
l xx l xx l xx l xx
证明: 若给定键的位置 y, 键的数量 n, t 分布值 t 以及显著性水平 α, 中间变量 l yy , σ 以及 t 值的计算如下:
