💻 computer science

HRT-LI: Certified Rank Transport for Dynamic Learned Index over Hierarchical String Keys

本文介绍了 HRT-LI，这是一种针对层级字符串键的认证动态学习索引，它通过将冻结的预测模型与基于账本的修正机制相结合来维持严格的秩误差保证，并通过在数亿个真实世界字符串上的广泛实验进行了验证。

原作者： Prathmesh Sayal, Kshiraja Nelapati

发布于 2026-09-15

📖 1 分钟阅读☕ 轻松阅读

原作者： Prathmesh Sayal, Kshiraja Nelapati

原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在数字世界庞大而沉默的机械运作中，数据正在不断地被排序、存储和检索。为了从这些信息洪流中理出头绪，计算机依赖于索引，这些索引本质上是高度组织的地图，能够精确地告诉机器在哪里可以找到特定的信息。几十年来，这些地图一直使用僵化的数学规则来构建，这些规则对于简单的数字运作完美，但在面对人类语言的复杂现实时却显得力不从心。单词、网址和文件名不仅仅是数字；它们是字符组成的字符串，长度不一，且其顺序取决于每一个字母和符号。当数据发生变化时——例如增加了一个新文件或删除了一个旧文件——整个地图可能会发生偏移，迫使计算机重新计算位置，并经常导致系统迷失方向。这就是管理动态层级字符串的核心挑战：如何在不因单个字符的变化而被迫从头重建整个地图的情况下，保持地图的准确性。

来自雷玛亚理工学院（Ramaiah Institute of Technology）的研究人员通过一种名为 HRT-LI 的新方法解决了这个问题，该系统旨在即使在数据增长和缩减时也能保持这些数字地图的准确性。研究团队并没有试图通过一个复杂的模型来预测每个新数据的确切位置（因为这种模型可能会被变化所干扰），而是决定冻结一个特定时刻的数据完美快照。随后，他们构建了一个独立的轻量级账本，用以记录该快照之后发生的每一次添加和删除。可以将这个账本想象成一本精确的会计账簿，记录着原始地图与当前现实之间的差异。当计算机需要查找某项数据时，它会从冻结的地图开始，获得一个大致的查找位置，然后查阅账本，根据自快照拍摄以来新增或删除的项目数量来调整该位置。这种方法允许系统为所有原始数据维持保证的准确水平，同时通过另一种精确计数的方法来处理新条目。

研究人员在大规模范围内测试了该系统，使用了来自 Common Crawl 项目（一个真实的互联网存档）的近亿个 Web 主机名数据集。他们对这一庞大集合进行了严格的压力测试，插入了 10 万个新名称并删除了 10 万个现有名称。在这些变化过程中，系统成功追踪了每一项数据的轨迹。团队将 1.64 亿个答案与独立记录进行了核对，确认系统从未迷失方向。甚至当研究人员要求系统查找特定项目的排名时——本质上是在问“在此之前有多少个项目？”——得到的答案也是精确的。该系统证明了它能够在管理新插入和删除的混乱情况的同时，保留原始数据（即基准）的准确性。这并非模拟或小规模实验，而是在反映了真实互联网复杂性的真实、杂乱数据上进行的全面验证。

该研究的一个关键发现是，该系统不需要为了保持准确性而不断对其内部模型进行重新训练。在许多其他系统中，添加或删除数据会迫使计算机重新学习数据的模式，这是一个缓慢且计算成本高昂的过程。HRT-LI 系统通过保持核心模型冻结来避免了这一点。账本处理变化，仅需对预测位置进行微调，以适应新的现实，而无需改变底层地图。这意味着对于原始数据，其误差范围与系统最初构建时完全一致。对于在插入后加入的新数据，系统则采用了不同的策略：它通过精确计数而非猜测来处理。这种混合方法确保了系统即使在数据集演变时，依然能保持快速且可靠。

研究人员还将他们的方法与其他处理字符串数据的标准工具（如自适应基数树和高度优化前缀树）进行了比较。在涉及数百万次操作的测试中，新系统显示出它能够保持完整性并提供精确答案，尽管与这些专门工具相比，它执行简单查找时有时会稍慢一些。然而，为了获得准确性的保证，这种权衡是值得的。该系统证明了它能够处理层级字符串（如具有多级子域的 Web 地址）的特定复杂性质，而不会丢失精度。记录变化的账本能够高效地压缩信息，通过共享字符串的共同部分来节省空间，就像图书馆目录通过将书籍按共同标题分组，而不是列出每一个页码一样。

这项工作最显著的方面之一是其验证的规模之大。团队不仅声称系统有效，还建立了一套完整的、独立的验证流程来检查每一个答案。他们运行了该系统五次，每次都从全新的状态开始，并确认结果是一致的。他们还在不同的误差容限下测试了系统，展示了它可以根据应用需求被调整为极其精确或略微灵活。当数据变得过于庞大或账本变得过于复杂时，系统展示了一种自我重建的方式，即创建一个新的快照并清空账本，从而有效地重置时钟，同时保留数据的准确性。这种生命周期管理对于任何需要在现实世界中持续运行的系统都至关重要。

研究结论指出，可以创建一个针对复杂字符串数据的动态索引，使其在无需不断重新训练的情况下保持准确。通过将稳定的、冻结的地图与动态的变化账本分离，研究人员找到了保持系统诚实的方法。账本充当了桥梁，将过去的静态预测转化为当下的鲜活现实。这种方法为管理不断增长的数字信息量提供了一条新路径，确保即使在数据发生偏移和变化时，计算机也始终知道确切的查找位置。研究结果并非一种消除了所有成本的魔术方案，但它们为构建能够以信心和精度应对现代网络复杂性的系统提供了坚实且经过验证的基础。

技术摘要：HRT-LI —— 用于分层字符串键动态学习索引的认证秩传输

1. 问题陈述

学习索引（Learned Indexes）通过机器学习模型估计键在排序序列中的位置，通常将搜索空间缩减到一个有界的区间。然而，动态操作（插入和删除）引入了一个根本性的挑战：它们会改变现有键的“实时秩”（live rank），即使这些键的值保持不变。这种“坐标漂移”（coordinate-drift）会导致冻结模型的误差保证失效，因为预测的秩不再与真实的秩对齐。

现有的动态学习索引通常依赖于可变模型或特定的数据布局来吸收更新，但这可能会损害原始的误差界限或产生高昂的重训练成本。此外，处理变长分层字符串（如 URL 或文件路径）需要严格的字节级字典序，这在利用近似数值特征进行预测时很难保持。核心问题在于：如何在支持动态、分层字符串索引的同时，为一个冻结模型维护一个经过验证的误差证书（verified error certificate）。

2. 方法论：HRT-LI

提出的解决方案——分层秩传输学习索引（Hierarchical Rank-Transport Learned Index, HRT-LI）——将静态模型的保证与数据的动态状态解耦。它通过以下三个主要机制实现：

A. 基础快照与精确字符串排序

系统始于一个排序且无重复的基础集合（ $S_0$ ）和一个模型（ $p_0$ ），该模型经过详尽验证，满足对于所有 $k \in S_0$ ，均有 $|p_0(k) - \text{rank}_0(k)| \le \epsilon$ 。

Lexicode 表示法： 为了确保变长字符串的精确排序，系统使用了一种稀疏基数（sparse-radix）lexicode。它通过移动数值并附加终止符来转换字节字符串，从而在不依赖有损数值特征进行最终排序决策的情况下，保持严格的字节级字典序（包括处理如 /a 与 /a/b 的前缀情况）。

B. 有符号前缀质量账本（Signed Prefix-Mass Ledger）

HRT-LI 不进行模型重训练，而是维护一个有符号基数账本（signed radix ledger），记录当前状态（ $S_t$ ）与基础快照（ $S_0$ ）之间的差异。

加权突变： 插入操作被分配权重 $+1$ ，基础键的删除被分配权重 $-1$。重新插入已删除的键或删除新插入的键会导致账本条目的“湮灭”（annihilation），即净权重为 0。
前缀质量计算： 账本计算这些权重的严格前缀和（ $\Delta_t(k)$ ）。这代表了在当前活跃集合中，位于键 $k$ 之前的键增加或减少的精确数量。
秩传输（Rank Transport）： 实时秩通过将此修正量叠加到基础秩上进行计算：
$\text{rank}_t(k) = \text{rank}_0(k) + \Delta_t(k)$
至关重要的是，预测的秩也被传输了： $p_t(k) = p_0(k) + \Delta_t(k)$ 。由于相同的修正量同时应用于预测值和真实值，误差界限保持不变：
$|p_t(k) - \text{rank}_t(k)| = |p_0(k) - \text{rank}_0(k)| \le \epsilon$
这使得原始误差证书对于所有存续的基础键在任意更新后依然有效。

C. 受保护的恢复与实现

基础键： 对于存在于基础快照中的键，系统使用传输后的预测值来定义有界搜索区间，随后在该区间内进行精确的二分查找。
插入键： 不在基础快照中的键不会继承模型的误差保证。它们的精确秩通过计算其下方的基础键数量，并结合账本的有符号计数来计算。
紧凑架构： 实现采用了用于存储基础键的内存映射文件和用于账本的路径压缩字节基数树（path-compressed byte radix tree）。它采用“受保护恢复”（guarded recovery）机制，即由模型引导搜索，但通过精确的字符串比较和边界检查来确保正确性，即使模型预测略有偏差或账本状态发生变化。

3. 主要贡献

本文概述了四项主要贡献：

精确的分层公式化： 提供了一种秩传输的数学公式，将顺序、前缀质量、湮灭以及针对变长字符串的证书保留进行分离。
前缀质量基数账本： 一种能够对共享字节前缀进行单次表示的数据结构，支持高效的插入、删除以及精确的实时秩/计数查询，且不将有损特征视为排序权威。
数值认证的实现： 一个包含受保护的学习基础恢复、显式二分查找控制和异常安全的有符号账本突变的紧凑实现。
大规模评估： 在 2 亿个自然 Common Crawl 主机字符串数据集上进行了全面的评估。研究验证了 1.64 亿个计时回答是否符合独立的源位置先知（source-position oracles），并执行了跨越不同边界（ $\epsilon = 16, 32, 64, 128$ ）的详尽误差检查。

4. 结果

在 2 亿规模键集的评估中，得出了以下发现：

证书保留： 在进行广泛的突变后，系统成功为所有存续的基础键维持了误差证书。逆向写入（重新插入被删除的键）正确地将账本恢复为零，验证了湮灭语义。
正确性： 所有 1.64 亿个计时回答均与其预期的源位置匹配。系统正确处理了精确的实时秩和范围计数，即使对于不存在于原始基础集中的键也是如此。
性能对比：
- 在针对 1,000 万个自然池的成员查询和混合写入负载与专门的字符串索引（ART, HOT, LITS）进行比较时，HRT-LI 在成员查询方面较慢。
- 然而，HRT-LI 提供了上述基准测试中的 ART/HOT 绑定原生不支持的序统计量能力（精确秩、前驱、范围计数）。
- “学习恢复”路径在处理实时成员查询和秩查询时，比“仅二分”恢复路径快约 25–33%，尽管这一内部消融实验并未建立其相对于其他专门索引的竞争优势。
内存与开销： 由于模型和账本的存在，HRT-LI 比简单的排序向量需要更多的内存和插入时间。研究发现，使用线性兄弟扫描（linear sibling scans）的账本实现比全量 Fenwick 树方法在测试负载下更具空间效率。
整合（Consolidation）： 一项单独的生命周期审计表明，系统可以重建（整合）为新的基础代际，通过验证新基础并清除账本，尽管该过程目前是阻塞式的离线操作。

5. 重要性与主张

本文将 HRT-LI 定位为，而非旨在超越所有现有索引在原始吞吐量上的掉入式替代品，而是一种面向动态学习索引的正确性保持架构。

理论贡献： 它确立了冻结模型的误差证书可以与分层字符串的动态精确序统计量进行数学组合。“秩传输”恒等式证明了重训练是一个成本/表示的选择，而不是在更新后维持误差界限的逻辑必要条件。
实际意义： 该系统提供了一种在重训练成本极高或需要对基础数据进行严格误差保证的动态环境中，使用学习索引的方法。
谦逊的主张： 作者明确指出，结果并未建立其在成员查询方面相对于 ART 或 HOT 等专门索引的竞争性吞吐量优势。其价值主张在于将经过认证的基础与动态更新进行组合，并提供精确的秩和范围操作，而非单纯追求原始速度。论文总结道，虽然其核心契约已在大规模环境下得到验证，但实际部署仍需在整合触发器和在线安装协议方面进行进一步工作，以管理不断增长的增量（delta）。