M-CTX：用于轨迹分析的精确且可扩展空间上下文检索

# 面向轨迹分析的精确可扩展空间上下文检索
来源：https://arxiv.org/html/2606.15244

###### 摘要

现代轨迹预测器越来越多地依赖于外部空间上下文，例如地图几何、符号距离场 \(SDF\) 以及附近移动的智能体。虽然这种上下文提升了预测质量，但为每个训练锚点构建它已成为一个隐藏的系统瓶颈。在一个代表性的海事 AIS 流水线中，对于一个包含 5.48M 个锚点的语料库，空间上下文的构建大约需要 1717 个 CPU·天，其成本远超下游预测器。我们提出 M-CTX，一个用于轨迹分析的精确且可扩展的空间上下文检索框架。M-CTX 将上下文构建重新定义为一种“一次摄取、多次查询”的空间数据库工作负载，并用可组合的、基于索引的操作符取代了三个暴力阶段——OSM 范围检索、SDF 计算和移动船舶邻居查找。其学习型范围索引后端 BR-LZ 提供了完备召回率的 MBR 重叠范围检索，与全局扩展的单曲线基线相比，将候选放大倍数降低了 1.1 倍×–2.7 倍×。在四个海事区域、八个基线系统、最多 40M 个空间特征的合成工作负载以及 10^7 条记录的 AIS 流上，M-CTX 精确复现了参考上下文。在 5.48M 个锚点的语料库上，它将上下文构建时间从大约 1717 个 CPU·天减少到 1.8 小时，实测端到端加速比为 226 倍。一种可选的存储模式进一步将 SDF 上下文压缩了 64 倍，仅带来 0.04 米 ADE 的变化。这些结果表明，精确的空间上下文检索是现代轨迹分析中的一个一流数据库问题。代码和数据集公开于 https://github.com/mark000071/M-CTX-Traj。

## I. 引言

轨迹预测正日益变得上下文感知。在自动驾驶、城市交通和航海导航中，合理的未来运动不仅取决于智能体最近的轨迹，还取决于周围的地图几何、物理约束和附近的智能体。我们在海事交通中研究这一转变，公共自动识别系统 \(AIS\) 数据源提供了最大的移动对象数据开源来源之一。最近的海事预测器越来越多地依赖于海岸线、航道、符号距离场 \(SDF\) 和邻近船只。这些信号提高了预测质量，但也引入了一个新需求：必须为每个训练样本检索并物化空间上下文。

这种上下文构建通常被视为常规预处理，但在实践中，它主导了整个流水线。对于每个 AIS 锚点，参考流水线执行三个操作：(i) 检索与 5 公里窗口重叠的 OpenStreetMap \(OSM\) 特征；(ii) 将局部地图块栅格化到一个128×128 的网格上，并计算两个 SDF；(iii) 扫描船舶快照以查找 3 公里范围内的邻居。对包含 1,000 个锚点的子集进行性能分析（第三节 (https://arxiv.org/html/2606.15244#S3)）显示，仅 SDF 构建就占用了大约一半的墙钟时间，主要原因是二次距离变换。暴力邻居扫描又增加了四分之一。外推到完整的 5.48M 个锚点的语料库，上下文构建在模型训练开始前需要大约 1717 个 CPU·天。预测器不是瓶颈；上下文流水线才是。图1 (https://arxiv.org/html/2606.15244#S1.F1) 总结了这一动机以及 M-CTX 背后的数据库重构思路。

<figure>
<img alt="图1" src="x1.png"/>
<figcaption>图 1: M-CTX 将每个锚点的空间上下文构建重新定义为一种精确的、基于索引的数据库工作负载。</figcaption>
</figure>

我们的关键观察是，这个瓶颈是一个在没有空间数据管理的情况下实现的空间数据库工作负载。OSM 检索是一个静态范围查询问题，涉及地图特征，即空间索引（如 R-树 [1 (https://arxiv.org/html/2606.15244#bib.bib1)]）的典型工作负载。邻居检索是一个流式移动对象查询，匹配 TPR-树和 Bx-树 [2 (https://arxiv.org/html/2606.15244#bib.bib2),3 (https://arxiv.org/html/2606.15244#bib.bib3)] 等索引的设置。SDF 构建则反复计算本地栅格上的精确距离变换，而可分离的线性时间算法 [4 (https://arxiv.org/html/2606.15244#bib.bib4)] 是已知的。尽管这些操作出现在学习流水线中，但它们共同的结构是面向数据库的：数百万个锚点反复从可高度重用的静态和流式数据中请求精确的空间上下文。

我们提出 M-CTX，一个用于轨迹分析的精确且可扩展的空间上下文检索框架。M-CTX 用可组合的、基于索引的操作符取代了三个暴力阶段：一个精确的 OSM 范围检索器、一个线性时间 SDF 引擎和一个增量式移动对象邻居索引。该框架保留了参考上下文的模式与语义，使得下游模型无需代码更改或重新训练即可消费生成的张量。其学习型范围索引后端 BR-LZ 使用有界残差和段局部范围，在提供完备召回率的 MBR 重叠范围检索的同时，相对于全局扩展策略降低了候选放大倍数。

本文做出以下贡献。

- • **一个空间上下文检索工作负载。** 我们形式化了轨迹学习的上下文构建，将其视为一种“一次摄取、多次查询”的空间数据库工作负载，并通过性能分析表明其在一个代表性 AIS 学习流水线中占据主导地位。
- • **BR-LZ，一个完备召回率的学习型范围索引。** 我们为 MBR 重叠范围查询引入了一种有界残差学习 Z 阶索引。BR-LZ 提供了显式的完备召回率保证，并在相同召回率下，相对于全局扩展策略将候选放大倍数降低了 1.1 倍×–2.7 倍×。
- • **精确 SDF 加速与存储协同设计。** 我们使用线性时间精确距离变换替换了二次 SDF 内核，将 SDF 阶段加速了 163 倍。我们还展示了 SDF 上下文可以压缩 64 倍，仅带来 0.04 米 ADE 的变化。
- • **一个端到端的精确上下文框架。** 在四个海事区域、八个基线系统、合成扩展到 40M 个地图特征以及 10^7 条流式 AIS 记录上，M-CTX 保持了参考上下文的语义。在 5.48M 个锚点的语料库上，它将上下文构建时间从大约 1717 个 CPU·天减少到 1.8 小时，实测端到端加速比为 226 倍，同时为确定性 LSTM+Env-SDF 核心保留了下游预测。

M-CTX 表明，隐藏在现代时空学习流水线内部的检索工作负载是一流的数据库问题。通过结合精确的空间索引、线性时间上下文物化以及对下游预测器的即插即用兼容性，它消除了主要的数据瓶颈，而无需改变学习模型本身。

## II. 相关工作

#### 空间索引与地理空间数据系统

空间索引是数据库系统的核心主题。R-树 [1 (https://arxiv.org/html/2606.15244#bib.bib1)] 及其变体，包括 R+-树 [5 (https://arxiv.org/html/2606.15244#bib.bib5)]、Hilbert R-树 [6 (https://arxiv.org/html/2606.15244#bib.bib6)] 和 R*-树 [7 (https://arxiv.org/html/2606.15244#bib.bib7)]，仍然是矩形和区域查询的标准访问方法。诸如 kd-树 [8 (https://arxiv.org/html/2606.15244#bib.bib8)] 和四叉树 [9 (https://arxiv.org/html/2606.15244#bib.bib9)] 等内存结构提供了互补的设计点，而 GiST [10 (https://arxiv.org/html/2606.15244#bib.bib10)] 则将许多空间访问方法抽象在一个通用接口背后。对于静态、读密集型工作负载，批量加载往往起决定性作用：Sort-Tile-Recursive 算法 [11 (https://arxiv.org/html/2606.15244#bib.bib11)] 生成紧凑的 R-树布局，并在实践中广泛使用。最近的研究在动态和工作负载感知的设置下重新审视了空间索引，例如 Waffle [12 (https://arxiv.org/html/2606.15244#bib.bib12)]，它使基于磁盘的空间索引适应查询/更新的权衡。大规模地理空间系统，包括 SpatialHadoop [13 (https://arxiv.org/html/2606.15244#bib.bib13)]、GeoSpark/Sedona [14 (https://arxiv.org/html/2606.15244#bib.bib14)] 和 RDPro [15 (https://arxiv.org/html/2606.15244#bib.bib15)]，旨在处理分布式矢量或栅格分析。M-CTX 是互补的：它针对的是较轻量但重复的训练循环工作负载，其中相同的静态地图和流式 AIS 状态被查询数百万次，以物化为下游模型的精确张量。

#### 学习型和工作负载感知索引

学习型索引用关键分布模型替换了基于比较的访问方法的一部分 [16 (https://arxiv.org/html/2606.15244#bib.bib16)]。一维学习型索引，包括 FITing-Tree [17 (https://arxiv.org/html/2606.15244#bib.bib17)]、PGM-index [18 (https://arxiv.org/html/2606.15244#bib.bib18)]、RadixSpline [19 (https://arxiv.org/html/2606.15244#bib.bib19)]、ALEX [20 (https://arxiv.org/html/2606.15244#bib.bib20)] 和 SALI [21 (https://arxiv.org/html/2606.15244#bib.bib21)]，已经表明分布感知模型可以在合适的工作负载下减少查找成本或内存占用。近期的评估和综述进一步表明，学习型索引并非普遍优越；其有效性取决于工作负载、更新模式、模型误差和实现成本 [22 (https://arxiv.org/html/2606.15244#bib.bib22),23 (https://arxiv.org/html/2606.15244#bib.bib23),24 (https://arxiv.org/html/2606.15244#bib.bib24)]。多维学习型索引通过将对象投影到空间填充曲线 [25 (https://arxiv.org/html/2606.15244#bib.bib25)]、像 LISA [26 (https://arxiv.org/html/2606.15244#bib.bib26)] 那样使用局部模型划分空间、像 RSMI [27 (https://arxiv.org/html/2606.15244#bib.bib27)] 那样学习递归划分、或者像 Flood [28 (https://arxiv.org/html/2606.15244#bib.bib28)]、Tsunami [29 (https://arxiv.org/html/2606.15244#bib.bib29)]、Qd-tree [30 (https://arxiv.org/html/2606.15244#bib.bib30)] 和 LMSFC [31 (https://arxiv.org/html/2606.15244#bib.bib31)] 那样联合优化布局与划分，来扩展这一思路。

M-CTX 与其正确性要求方面的研究不同。上下文构建需要完备召回率的 MBR 重叠检索：即使特征的中心点位于查询窗口之外，只要其 MBR 与查询窗口重叠，就必须返回该特征。基于中心点的单曲线学习型索引可能会遗漏此类特征，除非对查询进行扩展。全局最大范围可以恢复召回率，但会产生松散的候选集。BR-LZ 通过将有界残差与段局部范围相结合，直接解决了这一差距，在提供完备召回率 MBR 重叠检索的同时，相对于全局扩展减少了候选放大。

#### 移动对象索引与流式邻居检索

邻居检索阶段与移动对象索引相关。TPR-树 [2 (https://arxiv.org/html/2606.15244#bib.bib2)] 索引了时间参数化的 MBR，并支持对移动对象的预测查询。Bx-树 [3 (https://arxiv.org/html/2606.15244#bib.bib3)] 将按时间划分的位置映射到空间填充曲线上，并用 B+-树进行索引，从而避免在频繁更新下进行完整的快照重建。这一特性与 AIS 流非常匹配，其中位置以规律节奏到达，并且针对滚动快照发出邻居查询。M-CTX 采用 Bx-树风格的后端，在键范围枚举后使用精确半径过滤器。与快照 KD-树基线的主要区别在于更新粒度：M-CTX 支持交错的插入和查询，这是实时上下文构建所必需的。

#### 距离变换与空间上下文物化

符号距离场被广泛用于编码几何约束，例如地图边界、可航行区域和物体表面。精确的欧几里得距离变换可以通过 Felzenszwalb–Huttenlocher 算法 [4 (https://arxiv.org/html/2606.15244#bib.bib4)] 在线性时间内计算；经典的替代方案如 Maurer 变换 [32 (https://arxiv.org/html/2606.15244#bib.bib32)] 具有相同的 Θ\(HW\) 界限。神经符号距离场如 DeepSDF [33 (https://arxiv.org/html/2606.15244#bib.bib33)] 学习隐式形状表示，而地理空间系统如 RDPro [15 (https://arxiv.org/html/2606.15244#bib.bib15)] 则专注于可扩展的栅格分析。M-CTX 不学习 SDF，也不针对通用栅格分析。相反，它用精确的线性时间变换替换了轨迹学习流水线中的二次每个锚点 SDF 内核，然后将存储表示与下游准确性协同设计。

#### 上下文感知轨迹预测

最近的轨迹预测器越来越多地以静态场景上下文和动态智能体交互为条件。在自动驾驶中，基于 Transformer 的模型如 MTR [34 (https://arxiv.org/html/2606.15244#bib.bib34)]、Wayformer [35 (https://arxiv.org/html/2606.15244#bib.bib35)]、QCNet [36 (https://arxiv.org/html/2606.15244#bib.bib36)] 和 Forecast-MAE [37 (https://arxiv.org/html/2606.15244#bib.bib37)] 显式编码了道路拓扑、地图元素、邻近智能体或掩码的车道/轨迹上下文。早期的通用预测器如 Trajectron++ [38 (https://arxiv.org/html/2606.15244#bib.bib38)] 和 AgentFormer [39 (https://arxiv.org/html/2606.15244#bib.bib39)] 同样确立了社会和環境上下文的重要性。海事预测也遵循了同样的趋势：基于 AIS 的模型包括循环和 Transformer 预测器 [40 (https://arxiv.org/html/2606.15244#bib.bib40),41 (https://arxiv.org/html/2606.15244#bib.bib41),42 (https://arxiv.org/html/2606.15244#bib.bib42)]，用于船舶交互和交通流的图模型 [43 (https://arxiv.org/html/2606.15244#bib.bib43),44 (https://arxiv.org/html/2606.15244#bib.bib44)]，以及更广泛的海事轨迹分析综述 [45 (https://arxiv.org/html/2606.15244#bib.bib45),46 (https://arxiv.org/html/2606.15244#bib.bib46)]。M-CTX 与这些预测器是正交的：它不提出新的预测模型，而是加速这些模型日益依赖的精确上下文检索流水线。

#### 定位

M-CTX 的主要区别不仅仅在于学习型索引与经典索引。经典的空间索引提供精确检索，但在构建、存储或嵌入轻量级训练流水线时可能更为沉重。学习型空间索引改善了空间占用或构建时间，但对于 MBR 重叠上下文检索，它们通常依赖于经验性召回率或全局扩展。M-CTX 探讨的问题是：学习型空间索引能否在保留学习型索引的部署优势的同时，恢复模型端检索所需的精确性？BR-LZ 针对静态 OSM 范围检索回答了这个问题，而 M-CTX 将其与精确的 SDF 物化和流式邻居索引相结合，形成了一个面向轨迹分析的、端到端的、保持模式的上下文检索系统。

## III. 问题形式化与工作负载特征描述

### III-A. 作为工作负载的上下文检索

上下文感知轨迹预测为每个 AIS*锚点* a = (lat, lon, t) 在输入到预测器之前，附加局部空间上下文。设 F = {f_1, ..., f_N} 是一个静态的 OSM 特征集合，其中每个特征有一个二维 MBR 和一个语义标签，并设 S 是一个带时间戳的船舶流。