Page 338 - 《软件学报》2026年第5期

王撷阳 等: 基于数据分布的移动对象学习索引及查询算法 2217

CDF 函数存在统计效应, 以随机数据集 (数据集具体内容详见第 6.1 节) 为例进行分析. 如图 6(a) 所示, 针对
整个数据集的 CDF 曲线趋势平缓且光滑规则, 但是如果仅选择数据集中的一段区间如图 6(b) 就会发现数据趋势
具有明显的分段性、随机性, 这就增加了对于数据拟合的难度, 而多阶段的线性回归模型能够更有效地从数据集
的完整区域中将预测缩小至数千个区域.

700
220
⑤
600
500 215 ④
Position (×10 2 ) 400 Position (×10 2 ) 210 ③

300
200
205 ②
100 ①
0 200
0 100 200 300 400 500 600 700 200 205 210 215 220
Key (×10 ) Key (×10 ) 2
2
(a) 完整数据集趋势 (b) 指定区间趋势
图 6 CDF 预测键值位置示意图

NUGC_LI 会根据 CDF 的概率分布曲线对数据集进行划分, 这个过程中就会造成第 2 部分内部节点各子树的
不同生长形态, 这一步骤与经典的 RMI 学习索引结构有所不同, RMI 对数据集进行均匀划分, 然后对各个数据子
集进行模型学习和训练, 但是 NUGC_LI 不追求数量上的平均划分, 会根据数据集的数据特点更加灵活地划分数
据. 例如图 6(b) 中的数据区间 [20 000, 22 000], 如果按照均匀划分将生成 [20 000, 20 500]、[20 500, 21 000]、
[21 000, 21 500]、[21 500, 22 000] 这 4 个数据节点, 但是在 NUGC_LI 的划分原则中, 因为 [20 500, 21 000] 区间中
存在明显的趋势变换, 因此在进行数据划分时, 会将原本的 [20 500, 21 000] 数据节点替换为一个内部节点, 该内部
节点存在两个均为数据节点的孩子节点, 分别存储图中的区间②和③, 这样的划分规则能够使得生成的数据节点
①②③④⑤大致符合同一线性趋势, 便于线性回归模型准确拟合该节点键值. 按照上述节点生长规律, 如算法 2
所示.
算法 2. 学习索引 NUGC_LI 构建算法.

输入: 键值数量 num_keys, 键值数组 value_keys, 预训练线性模型 pretrained_model, 节点阈值 NodeTHR, 代价模型
cost;
输出: 基于当前数据构建的学习索引 NUGC_LI.

1. keys_remaining ← num_keys
2. while keys_remaining do
3. if node.cost < best.cost then /*自下而上计算出 value_keys 的最优划分*/
4. num_leaf_nodes ++
5. leaf_node_bulkload()
6. NUGC_LI ← leaf_node
7. find_best_partition_top_down(value_keys);
8. if keys_remaining > NodeTHR 或 node.cost > best.cost then /*判断该节点是内部节点还是数据节点*/
9. num_internal_nodes++ /*键值数量超过阈值或代价较高时, 节点设置为内部节点*/
10. if 当前子树深度一致, 内部节点分布均匀 then