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

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

的标准. 这种方法有效地合并了空网格和数据点极少的网格, 从而节约了存储空间. 通过采用交叉编码技术, 合并
网格时不需要更改网格标识或创建新的列表来记录合并动作, 将二进制编码右移一位从而与邻近网格合并. 根据
定理 1, 因为合并后的网格代表上一级的公共网格, 所以提取公共前缀作为新的编码.
鉴于所有网格编码都是唯一的二进制字符串, 并且具有递归前缀, 可以在降维后的数据上构建 B 树. 定义标
记位, 0 表示左子树, 1 表示右子树, 每个叶节点对应一个网格, 一个网格对应多个数据点.
在处理移动对象的动态更新时, 需要将新出现的移动对象点整合到现有的非均匀网格中, 以实现降维. 更新过
程中的降维步骤包括: 首先确定移动对象所在网格; 然后对比该网格更新后的密度值与预设的最高值, 如果密度值≤
最高值, 选择当前网格编码作为降维后的编码; 否则, 再次划分网格并使用一个 8 位的字段记录两次划分的局部编
码. 如果划分次数超过 8 次导致局部编码溢出, 进行全局更新, 重新构建非均匀网格. 非均匀网格算法能够支持更
新操作, 适用于更新频率不高、密度分布与历史移动对象相似的场景.
3.2.3 时间复杂度分析
由算法 1 可知在初始的均匀网格编码算法中, 采用了双层循环结构, 外层循环遍历移动对象点的投影值, 获取
每个点在两个维度上的空间位置, 内层循环则负责从最低位到最高位依次计算并赋值编码, 进行位移操作. 均匀网
O(M×L), 其中 M 为移动对象点个数, L 为编码长度.
格算法的时间复杂度为
在非均匀网格编码降维算法中, 原始实现涉及两个主要循环, 外部循环遍历所有移动对象计算每个均匀网格
的密度; 第 2 个循环则逐个检查均匀网格的密度是否达到阈值, 若未达到, 则执行网格合并操作, 并记录合并后网

格的更新值. 重复该过程直到所有网格合并满足相应条件. 该方法的时间复杂度为 O(M)+O(Num), 其中网格数
L
Num = 2 .
为提升降维效率, 将需要合并的网格中轨迹点一维编码右移一位, 设置原始轨迹点标签属性, 表示该点所在网
O(M).
格的移动对象点总数. 遍历一次移动对象点, 完成网格合并, 合并过程采用位运算, 因此时间复杂度降低到
算法 1. 非均匀网格降维算法 NUGC.

输入: 网格密度集合数组 Dens, 移动对象点数组 MP, 移动对象点个数 M, 均匀网格总数 Num, 一维编码长度 L;
输出: 一维非均匀编码 C.

1. Dens ← ∅
2. C ← 均匀网格降维算法 (MP)
3. average(Dens) ← get(Num, M)
4. for each iter ← 1 to Num do
5. C i ← 遍历网格得到每个网格编码
6. Dens ← 计算每个网格密度值
7. while Dens i < average(Dens) do
8. C i ≫ 1
9. return 降维后的一维非均匀网格编码数组 C
10. function 均匀网格降维算法 (MP)
11. for each iter ← 1 to |MP| do
12. GKpoints[i] ← GKprojection(MP[iter])
13. P min , P max ← GoThrough(GKpoints)
14. for each iter ← 1 to M do
15. get X median and Y median
16. for each iter ← 1 to L do
17. 计算并获得数据点的经度和纬度编码