本技术涉及计算机应用技术,介绍了一种在有向路网上构建误差受限的希尔伯特树学习索引的新方法。该技术通过将时空数据样本映射到位置-时间网格,并利用希尔伯特曲线对网格单元进行排序,以实现高效的数据索引。
背景技术
近些年随着移动设备的广泛使用以及定位设备精度的提高,大量移动轨迹被收集存储到移动数据轨迹库中。这些数据包含着移动对象的行动特征和交通信息,通过挖掘轨迹数据,可以总结人群移动规律,改善路网交通状况。目前环境下,轨迹数据呈现出数量繁多、高维复杂等特点,如何高效地查询轨迹数据成为一个关键问题。
目前的多维学习型索引可以分为模型拟合布局模式和模型生成布局模式。在模型拟合布局模式下,数据的存储顺序是预先确定好的,将数据按照某种固定的模式排序并放置,然后基于这种排序顺序训练模型来预测数据的位置,数据布局决定了训练模型。QiJianzhong等人在“Effectively Learning Spatial Indices”论文中提出了RSMI索引,该索引的核心思想是将多维空间中的点映射到排名空间,使用空间填充曲线对数据点进行排序,为每个数据点分配一个曲线值。排序结束后按照曲线值对数据点进行分块操作,训练一个多层感知器学习点的坐标到存储块位置的索引,递归地对数据进行分区和模型学习,直到每个分区的点数不超过设定的阈值为止。Zhang Songnian等人在“Efficient LearnedSpatial Index With Interpolation Function Based Learned Model”论文中提出了SPRIG+索引,该索引的核心思想是基于数据分布构建一个自适应网格,将空间划分为多个单元格。然后采用空间插值函数和动态编码技术构建IH-tree+索引。在进行范围查询时,通过插值模型预测查询点在网格中的位置,通过IH-tree+结构进行查询。
在模型生成布局模式下,首先选择一种能合理表示数据布局的模型,通过训练这个模型决定数据的存储分布,数据模型直接决定了数据布局。Li Pengfei等人在“LISA:ALearned Index Structure for Spatial Data”论文中提出了LISA索引,该索引将空间划分为网格单元,并根据坐标轴进行编号排序。然后LISA根据单元格的边界构建部分单调函数,通过这一预测函数将数据从多维空间映射到一维空间中。
现有的多维学习索引在处理大量高维轨迹数据时会面临冗余查询的问题,在进行磁盘读取操作时,系统可能会访问重复或者不必要的数据,增加了磁盘I/O操作的负担,降低了查询的总体性能。虽然上述提出的学习型索引方法通过降维、空间填充曲线、插值函数等方法处理、放置数据并训练机器学习模型以学习样本集的分布,但是他们都受限于数据的冗余扫描问题,此外,面对倾斜数据时,不均匀的数据密度分布也会导致学习模型的预测精度下降、搜索成本上升。
实现思路