Page 15 - 《软件学报》2026年第2期

494 软件学报 2026 年第 37 卷第 2 期

16. Determine to build N k rooted subtree
17. for c from 1 to b do
18. ← latree-offline( , , w 层枚举

N C N k ,c T N k ,c Q N k ,c ht 0 +w ht +1) //开始下一级
19. end for
20. end if
21. else //节点已经确定, 只需向下穿过已建节点直到 ht 0 +w 层开始下一级枚举
22. for c from 1 to b do
,
23. N C N k ,c ← latree-offline( T N k ,c Q N k ,c ht 0 ht +1)
,

24. end for
25. end if
26. return N k

● 复杂度分析. 记整个查询负载训练集 Q 的平均选择度为 sel, 由于优化分数估计了扫描比的上界, 在每段搜
|T| sel, 相应地, 本段子树平均每个叶子节点被查询访问次数可以
索过程, 本段子树的叶子节点访问量可以近似为
(
w
O h |T|lg|T|+
近似为 |Q| sel, 同理可近似计算每层每个节点近似访问次数, 在此基础上求得算法时间复杂度为
( )
w w
h b w
lg|T|+h b|T| sel |Q|). 较小和较大的 w 分别接近算法涵盖的两种特殊情形: 完全贪心算法和全树枚举算法,
w
( )
w w
h b
w
w w O h |T|lg|T|+ (a) 能很好
分别对应复杂度 O(h |T|lg|T|+h b|Q| sel|T|) 和 |Q|lg|T| . 由于优化分数 OPRS T,Q,N k
w
地表征扫描比变化, 且剪枝作用明显, w ⩽ 2 即可算得较优的划分维度组合.
h
b −1
● LA-tree 超参数 h 和 b 分析. 可近似看作, LA-tree 索引将数据表 T 划分为小于 个单元, 因而调节 h 和 b
b−1
本质是平衡筛选和扫描阶段的用时, 显然 h 比 b 影响更大. 因此调节超参数的算法是, 首先由用户输入索引大小,
h 下使用邻近搜索方法调节到
进一步计算初始相等的 h 和 b, 再使用邻近搜索方法调节到最佳的 h, 最后在确定的
最佳的 b. 邻近搜索的每一步, 在 T 和 Q 的随机样本上构建索引并验证查询用时, 由于样本足够小, 超参数可被快
速调节.
4 在线查询处理: 基于学习模型的高效在线筛选方法
本文提出的基于学习模型的高效在线筛选方法, 通过在各节点训练线性回归模型拟合数据分布, 使索引能够
在每个节点以常数时间复杂度, 根据查询范围边界快速完成数据筛选, 从而同时保证筛选的准确性与高效性.
n 行且仅单维属性 , 将其升序排
X
● 准确性证明. 不失一般性地, 以单维索引问题展开分析. 给定数据表 T 有
X
序并记对应顺序条目号为 {i 1 ,i 2 ,...,i n }, 引入离散数据累积分布函数 (CDF) 刻画 T X 的分布 CDF(T ), 表明任意 T X
{ }
| v ⩽ x 0 |v ∈ T X |
X
取值的相对位置, 即 CDF(T = x 0 ) = .
n
设一线性回归模型 (LM) M T X(x) 拟合 CDF(T ), 在离线训练阶段仅根据数据分布求出其误差界限 (error-
X
bound), 记为 :
eb M T X
{ }
X
= max M T X(v)−CDF(T = v) | v ∈ T X (10)

eb M T X
基于公式 (10), 可以证明对于任意在线查询 [lb,ub], 所有查询范围内的数据条目一定在 M M T X (x) 估计的两端
位置各向外扩张一个 eb M T X 的范围内. 即基于 M T X(x) 的学习型索引可以表示为:

{ }
l r
⩽ ⩽ (11)
I T ([lb,ub]) = i l ,i l+1 ,...,i r | M T X(lb)−eb M T X ⩽ M T X(ub)+eb M T X ,v i l−1 ,X < lb ⩽ v i l ,X ⩽ v i r ,X ⩽ ub < v i r+1 ,X
n n
用不等式放缩法可证明公式 (11) 成立, 即该学习型索引 I T 的正确性. 由于 M T X(x) 是单调递增函数, 对于
X
∀v ∈ T , 若在线查询 [lb,ub] 满足 lb ⩽ v, 必有: