邻近毕业，仅用于记录。本论文代码实现于研一期间。

论文：Efficient Learned Spatial Index With Interpolation Function Based Learned Model

IEE链接：https://ieeexplore.ieee.org/abstract/document/9816118

SPRIG+基于SPRIG实现，本文将先简单介绍下SPRIG基础，然后在下一节探讨变体SPRIG+相关实现。

论文：SPRIG: A Learned Spatial Index for Range and kNN Queries

链接：https://dl.acm.org/doi/abs/10.1145/3469830.3470892

论文的主要贡献在于通过使用空间（多维）插值函数作为学习模型，直接应用于空间数据，以充分利用原始空间数据的空间分布信息。具体而言，论文设计了一种高效的基于空间插值函数的网格索引（SPRIG），用于处理范围查询和k最近邻查询。

空间插值函数：通过一组二维样本点和它们的对应值构建一个可以通过所有这些样本点的函数。给定任意点 (x, y)，可以使用插值函数估算 f(x, y) 的值。

SPRIG 索引的构建过程：

（1）一个n × m的网格布局Gn×m，其中n是沿x维度的列数，m 是沿 y 维度的行数

（2）一个表格 T

（3）基于空间插值函数 Fin 的学习模型

进行网格布局构建时，目标是构建一个 n × m 的网格布局 Gn×m，其中数据记录在列之间均匀分布。每一列应该包含大致相等数量的记录。为了实现这个目标，主要思想是找到每个维度的边界值，将空间划分为若干列，确保每列具有几乎相等数量的数据记录。

1、空间填充曲线的使用：

首先，论文使用了一种简单的空间填充曲线来对这些单元格进行索引。

分配整数在范围 [0, n×m−1] 作为沿 x 维度的单元格标识，并定义一个二维数组 Cid 以存储这些单元格的标识：Cid[i][j] = j ·n+i，其中 0 ≤ i < n 且 0 ≤ j < m。

2、表格T的构建：

构建一个表格 T，将单元格标识映射到覆盖的记录。表格 T 的键是单元格标识，值是一个包含指向第一条记录的指针和单元格中记录数的对 (firstAddress, size)。这一步的目的是为了更方便地管理每个单元格中的记录。

3、空间插值函数 Fin 的拟合：

基于之前构建的格网布局 Gn×m 和单元格标识 Cid，拟合一个空间插值函数 Fin。将 {Bx, By} 视为输入，将 Cid 视为期望的估计值，确定 Fin，即 Cid ← Fin(Bx, By)。

通过这一系列步骤，SPRIG 索引得以建立。该索引结构的设计旨在确保数据记录的均匀分布，并通过空间插值函数 Fin 进行快速的位置估计。这有助于提高对空间查询的处理效率。

再谈谈空间插值函数（Spatial Interpolation Function）：

空间插值函数用于通过一组二维样本点和它们的对应值构建一个可以通过所有这些样本点的函数。给定任意点 (x, y)，可以使用插值函数估算 f(x, y) 的值。

• 借鉴了学习型索引的思想，可以将样本值 vi 视为点 (xi, yi) 的位置，然后使用插值函数快速估算任意给定点的位置。
• 如果样本点不是随机的，而是能够表示原始空间数据的分布，可以使用较少的样本点来拟合空间插值函数，从而降低空间插值函数的存储开销。

误差保证（Error Guarantee）

1、误差保证的重要性：

学习型索引中，预测给定点的位置后，进行局部搜索是至关重要的。一般来说，局部搜索范围为[pos-eg,pos+eg]，其中pos是预测位置，eg是估计误差，也称为误差保证。

2、最大估计误差作为误差保证：

SPRIG方案采用最大估计误差作为误差保证。最大估计误差可以通过查询工作负载W来确定。

误差保证（eg）定义如下：

eg = Max(Fin(qx,qy)-f(qx,qy))

其中(qx,qy)∈W。这个误差保证反映了模型在查询工作负载下的最大预测误差。

3、误差保证在两个维度上的投影：

对于一个空间点，其空间位置可以由其x和y坐标确定。在SPRIG中，将估计的空间位置投影到x和y维度上，得到两个误差保证值，即

egx= max(Px(Fin(qx,qy))-Px(f(qx,qy))),

egy= max(Py(Fin(qx,qy))-Py(f(qx,qy))),

其中，Px()和Py()分别将空间位置投影到x和y维度。