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

2208 软件学报 2026 年第 37 卷第 5 期

持动态插入. RSMI 通过采用基于排序的排名空间映射, 将多维点映射到一维空间, 从而克服了 Z-order 空间填充
曲线的经验累积分布函数不均匀间隙问题. RSMI 将数据点按升序排列, 按照预定义的块大小将数据打包到一个
块中, 并且在数据集较大的情况下, 采用递归分区方法, 每个分区会训练一个机器学习模型来进行映射. 这些模型
将搜索关键字映射到磁盘块 ID, 从而加速查询过程. 2023 年, Ding 等人 [48] 提出基于基数表、样条点和倒排列表技
术构建的学习索引, 以有效地处理空间文本数据, 并使用 Morton 编码将高维坐标转换为一维坐标. 同时, 为了实时
处理数据的插入、删除和更新, 采用间隙数组存储底层数据, 研究者们还设计了以样条点为单位的空间重分配策
略, 并基于该索引提出查询处理算法, 高效处理不同的空间关键词查询. 同年, Li 等人 [49] 提出的 BMT 索引克服了
传统空间填充曲线 (space-filling curve, SFC) 方法的局限性, 传统的 SFC 使用固定的位合并模式, 无法考虑数据分
布或查询工作负载的变化. 其采用树形结构, 每个叶子节点对应一个子空间, 通过为不同维度的每个内部节点分配
比特值来从根到叶的路径创建位合并模式. 为了提高 BMT 的构建效率, 采用了强化学习技术来学习最优的构建
策略, 并将贪心策略与蒙特卡洛树搜索结合使用. 同年, Gao 等人 [50] 提出的 LMSFC 则聚焦于学习一个给定数据和
查询工作负载的参数化单调 Z-order. 通过学习特定实例的最优参数, LMSFC 能够最小化查询处理成本. 优化问题
通过贝叶斯优化方法来求解. 优化后, 采用基于密度的成本函数将数据点更高效地打包到磁盘页面中, 尽量减少 MBR
的空白空间. 然后, 使用如 PGM-index 等学习索引来查找与给定 Z 值对应的页. 与其他学习索引类似, LMSFC 通
过原地插入策略支持动态插入操作. BMT 和 LMSFC 都在多维数据索引领域提供了先进的优化技术, 能够根据特
定数据和查询分布动态优化数据布局和查询处理操作, 显著改善了查询性能.
学习索引作为数据库研究热点已经取得了一系列的成果, 但目前关于多维学习索引的动态更新、支持处理更
多查询类型、与图数据库的结合等方面还有许多关键问题尚未解决, 需要更进一步的探索研究 [51] .
1.2.3 数据划分方法
均匀划分策略是一种常见的方法 [52] , 通过将数据均匀地分配给学习模型再进行拟合. 这种方法没有将数据特
点和模型融合, 较难得到最优划分结果. ALEX 提出了一种自上而下划分策略, 通过多次访问数据集依靠代价模型
估计进行划分. 还有学者提出了贪心算法 [53] 进行数据划分, 旨在降低模型的误差范围.
1.3 查询算法
移动对象数据库中存放的数据量规模巨大, 且数据的表现形式比关系型数据库更为复杂. 所以, 移动对象数据
库在存储、索引以及查询等方面的技术难度比关系型数据库更大. 同时, 因为移动对象的数据含有时间、空间属
性, 所以在移动对象的查询处理方面, 需要指明时间和空间请求, 现有针对移动对象的经典查询技术可以分为以下
几个类型.
1.3.1 范围查询
移动对象数据库中最基本、应用最广泛的查询类型之一, 由用户给定一个时间区域和一个空间区域, 数据库
查询得到所有满足该时空范围条件的移动对象并返回给用户. 范围查询在许多智慧城市应用中均有体现, 例如交
通轨迹识别. 2019 年, Yu 等人 [54] 提出一种分布式混合索引, 将全局网格索引和局部 VR 树索引相结合, 将其部署
在服务器集群上, 以维护海量移动对象数据和连续的范围查询. 2023 年, Baride 等人 [55] 为解决难以选择合适距离
阈值的问题, 提出了一种用于共置模式挖掘的范围查询, 识别了搭配模式的若干结构属性, 使得查询条件从单个距
离阈值更改为距离间隔, 并通过使用多类型数据集, 证明该算法的优越性.
1.3.2 最近邻查询
GPS 技术和嵌入式设备的迅速发展使得最近邻查询受到越来越广泛的关注, 它是指用户给定一个需查询的移
动对象, 数据库在当前数据集中查询与该指定移动对象距离最近的指定个数对象, 作为查询结果返回. 最常见的最
近邻查询是 k 近邻查询 KNN, 也就是查询距离指定移动对象最近的 k 个移动对象, 其中 k 为随机指定的数字. 例
如, 乘客使用打车软件时, 应用程序会根据查询位置返回距离该乘客最近的网约车并自动派单, 以保证服务质量.
2016 年, Yi 等人 [56] 研究移动对象在近似 k 近邻查询中保留其位置和查询隐私的问题, 提出了建立在 Paillier 公钥
密码系统上的通用解决方案, 可以应用于基于位置的私有查询的多个离散类型属性. 2021 年, Levchenko 等人 [57] 提