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

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

,
其中, MP Q 是轨迹相似性查询的查询键, Traj-Sim(MP j , MP Q ) Traj-Sim(MP i , MP Q ) 是定义 8 中轨迹相似性程度计
算操作, 根据计算得到移动对象 MP j 与查询键 MP Q 的轨迹相似性程度最高, 为相似轨迹查询结果.

3 非均匀网格降维算法

移动对象数据查询时, 需要先进行数据降维, 现有降维算法中大多保留数据局部结构特征. 移动对象数据的空
间位置有均匀分布和非均匀分布两种情况, 且具有随时间变化、多粒度表示等特征, 仍是研究的难点. 因此, 提出
了一种均匀网格降维算法. 在处理移动对象数据时, 均匀网格是传统的划分方法之一, 假设空间可以均匀地划分为
多个网格单元, 以便于后续的数据分析和处理. 然而, 均匀网格在处理具有高度不均匀分布特征的移动对象数据时
存在明显的局限性. 具体来说, 均匀网格假定每个网格单元包含相同数量的数据点, 但移动对象往往呈现出不均匀
的空间分布. 在某些区域, 移动对象的聚集程度较高, 而在其他区域则可能没有任何对象. 这种不均匀分布会导致
空间的浪费, 尤其是在一些网格单元内没有移动对象经过时, 造成了不必要的内存和计算资源的消耗, 还影响了数
据处理的效率和准确性. 单纯依赖均匀网格方法会低效地利用空间资源, 并且未能有效捕捉数据的真实分布. 因
此, 根据移动对象的分布特点, 进一步优化得到非均匀的网格降维算法.
3.1 均匀网格降维算法
常见的墨卡托投影在高纬度地区出现严重畸变, 限制了其在全球范围内的精确应用. 通用横轴墨卡托投影虽
然适用于大范围区域, 但在跨带数据处理时需要额外的转换, 增加了复杂性和误差累积的风险. 而等距圆锥投影虽
然在一定区域内表现良好, 但其精度仅限于特定区域, 难以适应更广泛的地理范围 [60] . 而高斯-克吕格投影 [61] 在局
部区域内表现出更高的精度和计算效率, 能够有效减少变形, 尤其适用于需要高精度的区域性应用. 由于其能够在
较小范围内保持最小畸变, 便于后续基于 GeoHash 编码的空间数据降维处理, 因此成为降维过程中合适的选择.
将移动对象点的坐标点按照高斯-克吕格投影方式进行转换, 通过编码生成二进制字符串, 以实现数据降维. 均匀
网格编码算法首先通过遍历得到移动对象轨迹的区域边界, 将该区域矩形递归地进行二等分得到更多的矩形, 并
按照编码长度要求终止划分. 通过均匀网格编码算法得到的编码存在定理 1 所述性质.
定理 1. 给定移动对象位置 Loc 1 和 Loc 2 , 均匀网格编码可计算出 Code(Loc 1 ) 和 Code(Loc 2 ). 若 Pre(Code(Loc 1 )) =
Pre(Code(Loc 2 )) = pre |Code(Loc 1 )| ⩾ pre |Code(Loc 2 )| ⩾ pre, 则 Loc 1 和 Loc 2 均在编码为 pre 的网格中.
,
,
证明: 对于具有相同编码前缀 pre 的两个数据点 Loc 1 和 Loc 2 , 假设这两个数据点不在同一个网格中. 因为
Pre(Code(Loc 1 )) = Pre(Code(Loc 2 )) = pre, 所以两个数据点 Loc 1 和 Loc 2 经过二分编码后均被划分到编码为 pre 的
网格. 这与不在同一网格的假设矛盾, 不成立. 如果两个数据点前缀相同, 那么它们一定都在公共网格中.
均匀网格编码算法的具体实现步骤为: 首先将移动对象点的坐标存储在 MP 中; 其次将所有数据点进行高斯-
克吕格投影, 找出投影区域最小点和最大点; 最后对每个数据点编码, 奇数位为经度编码, 若当前数据点经度小于
平均值, 则编码左移 1 位, 末位赋 0, 否则赋 1. 将经度范围更新为当前数据点所在网格的经度范围值, 偶数位为纬
度编码, 按照上述方法类推至编码长度达到给定精度要求. 根据上述描述与定理 1 的编码特点, 两个移动对象点距
离越小, 通过网格降维后的公共前缀就会越长. 当编码 Code 1 以编码 Code 2 为前缀, 则 Code 1 对应的移动对象点一
定落在前缀码 Code 2 所对应的区域中.
3.2 非均匀网格降维算法

移动对象具有分布广、聚集多、非均匀的特点. 如果不考虑数据特点, 对所有数据均采用均匀网格划分会增
加存储空间, 降低处理效率. 本文通过网格密度计算数据密集程度, 并根据网格密度采取平衡措施, 针对数据分布
情况提出了非均匀网格降维算法. 一方面避免了存储大量空网格和低密度网格, 节省编码所需的存储空间; 另一方
面在查询阶段, 有效减少了读取操作代价, 对不符合范围条件的空网格和低密度网格进行有效过滤.
3.2.1 网格密度
为便于介绍网格密度值 (grid density, Dens), 先给出相关变量符号, 如表 2 所示.