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

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

b 设置下, 一个叶子节点可能包含较多数据条目, 使用 LM 模型筛
若 N k 是一个叶子节点, 由于在一定的 h 和
选数据可能带来较高的 error-bound, 因而叶子节点使用 PLM 排序后的数据子集的分布
模型拟合按节点维度
a N k
CDF(T a N k ). 自顶向下筛选时, 叶子节点是最后一层, 通过该 PLM 模型, 对查询 q 的谓词在节点维度 a N k 上的范围
N k
], 用模型估算其两端点在数据子集 T N k 关于维度 a N k 的投影 T a N k 中的有序位置, 再将估算结果向两端
[lb q,a N k
N k
,ub q,a N k
分别扩张 eb M a N k 的宽度保证数据筛选没有遗漏. 注意, 叶子节点 PLM 模型估算位置的过程与中间节点 LM 模型
T
N k
稍有不同, 具体来说先定位输入值所在分段 (piece), 再用段上的局部 LM 模型估算位置. 计算完成后, 即可得到
] 包含的所有数据条目, 进一步扫描以确定每条数据是否在查询范围内. 当筛选与扫描完成, 自底向上
,ub q,a N k
[lb q,a N k
N k 直接返回经过“筛选+扫描”确定的查询结果子集. 结合公式 (1) 和公式 (11) 有:
合并查询结果时, 叶子节点

{ { }}
l r
′ ⩽ ⩽
(q) = i | lb q,a j ⩽ v t ′ ,a j ⩽ ub q,a j i (15)
i ,∀a j ∈ A,t M a N k (lb q,a N k )−eb M a N k n n ⩽ M a N k (ub q,a N k )+eb M a N k
I T N k
T T
T N k
T N k
N k N k
最终, 查询结果由根节点返回即 (q). 上述高效在线筛选方法, 在 LA-tree 每个节点上, 都能利用机器
I T (q) = I T N 1
b−1 个
学习模型以 O(1) 的开销快速准确筛选子节点和数据, 令查询扫描比进一步降低的同时无需与中间节点的
分位点以及叶子节点的排序数据做数值比较, 效率很高. 算法 2 描述了上述包含公式 (14) 和公式 (15) 的基于学习
模型的高效在线筛选方法.
算法 2. LA-tree 在线查询处理: latree-online( N k q).
,
输入: LA-tree 节点 N k , 在线查询 q;
输出: 节点索引功能返回的数据条目号集合 I T N k (q).
1. if C N k = ∅ then //叶子节点筛选与扫描
2. I T N k (q) ← Scan data tuples T N k after filtering by q 0 with PLM on dimension a N k
3. else //中间节点筛选
4. I T N k (q) ← ∅
[ ]
fchild,tchild ← Filter child nodes by with LM on dimension , refine by ±eb
5. lb q,a N k ,ub q,a N k a N k
6. for c from fchild to tchild do
7. (q) ∪ latree-online( N C N k ,c , q)
I T N k (q) ← I T N k
8. end for
9. end if
10. return I T N k (q)
上述算法 2 入口为 latree-online( N 1 q), 函数执行完毕后将返回查询 q 在数据 T 上的结果.
,
5 在线索引更新: 自适应增量式的索引更新方法
LA-tree 的在线索引更新由两部分组成: 增量更新与自适应更新. 增量更新保证新数据能够被实时插入并维护
局部有序性, 自适应更新则通过动态调整局部数据划分以适应数据分布和查询负载的变化, 两者共同确保索引在
动态环境下依然保持“均匀划分”与“查询感知”的特性. 增量更新: 该方法应对动态场景中的数据更新操作, 分为两
步骤: 先定位增删改的数据条目在索引中储存的位置, 再对该位置删除或插入新元素. 这里第 2 步较为简单, 使用标
O(1) 的时间内解决. 对于第 ′ ⟨ ⟩
记法即可在 1 步, 我们将数据条目转化为点查询, 即对新数据条目 t = v t ′ ,a 1 ,v t ′ ,a 2 ,...,v t ′ ,a d
转化为对应查询 q : [v t ′ ,a 1 ,v t ′ ,a 1 ]∧[v t ′ ,a 2 ,v t ′ ,a 2 ]∧...∧[v t ′ ,a d ,v t ′ ,a d ], 该查询基数恒为 1, 显然通过自顶向下的节点模型高效
映射, 仅需 O(h) 时间即可完成新数据条目的定位, 该过程如算法 3 所示.
算法 3. LA-tree 增量数据索引更新: latree-incremental-data-update( N k t , ).

输入: LA-tree 节点 N k , 更新数据条目 t;