💻 computer science

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

This paper introduces HRT-LI, a certified dynamic learned index for hierarchical string keys that maintains strict rank error guarantees by coupling a frozen predictive model with a ledger-based correction mechanism, validated through extensive experiments on hundreds of millions of real-world strings.

Original authors: Prathmesh Sayal, Kshiraja Nelapati

Published 2026-09-15

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Prathmesh Sayal, Kshiraja Nelapati

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast, silent machinery of the digital world, data is constantly being sorted, stored, and retrieved. To make sense of this deluge, computers rely on indexes, which are essentially highly organized maps that tell a machine exactly where to find a specific piece of information. For decades, these maps have been built using rigid, mathematical rules that work perfectly for simple numbers but struggle when faced with the messy reality of human language. Words, web addresses, and file names are not just numbers; they are strings of characters that can be short or long, and their order depends on every single letter and symbol they contain. When data changes—when a new file is added or an old one is deleted—the entire map can shift, forcing the computer to recalculate positions and often causing the system to lose its way. This is the central challenge of managing dynamic, hierarchical strings: keeping the map accurate without having to rebuild the entire thing from scratch every time a single letter changes.

Researchers at the Ramaiah Institute of Technology have tackled this problem with a new approach called HRT-LI, a system designed to keep these digital maps accurate even as the data within them grows and shrinks. Instead of trying to predict the exact location of every new piece of data with a complex model that might get confused by changes, the team decided to freeze a perfect snapshot of the data at a specific moment in time. They then built a separate, lightweight ledger to record every single addition and deletion that happens after that snapshot. Think of this ledger as a precise accounting book that tracks the difference between the original map and the current reality. When the computer needs to find a piece of data, it starts with the frozen map to get a rough idea of where to look, and then it consults the ledger to adjust that position based on exactly how many items have been added or removed since the snapshot was taken. This method allows the system to maintain a guaranteed level of accuracy for all the original data, while handling new entries with a different, exact counting method.

The researchers tested this system on a massive scale, using a dataset of nearly 200 million web host names collected from the Common Crawl project, a real-world archive of the internet. They subjected this enormous collection to a rigorous stress test, inserting 100,000 new names and deleting 100,000 existing ones. Throughout these changes, the system successfully tracked the position of every single item. The team verified 164 million answers against independent records, confirming that the system never lost its way. Even when the researchers asked the system to find the rank of a specific item—essentially asking "how many items come before this one?"—the answers were exact. The system proved that it could preserve the accuracy of the original data, known as the base, while simultaneously managing the chaos of new insertions and deletions. This was not a simulation or a small-scale experiment; it was a full-scale validation using real, messy data that mirrors the complexity of the actual internet.

A key finding of the study is that the system does not need to constantly retrain its internal models to stay accurate. In many other systems, adding or removing data forces the computer to relearn the patterns of the data, a process that is slow and computationally expensive. The HRT-LI system avoids this by keeping the core model frozen. The ledger handles the changes, shifting the predicted positions just enough to account for the new reality without altering the underlying map. This means that for the original data, the error margin remains exactly as it was when the system was first built. For the new data that was inserted after the snapshot, the system uses a different strategy: it counts the items exactly rather than guessing. This hybrid approach ensures that the system remains fast and reliable, even as the data set evolves.

The researchers also compared their method against other established ways of organizing data, such as adaptive radix trees and height-optimized tries, which are standard tools for handling string data. In tests involving millions of operations, the new system showed that it could maintain its integrity and provide exact answers, though it sometimes took slightly longer to perform simple lookups compared to these specialized tools. However, the trade-off was worth it for the guarantee of accuracy. The system proved that it could handle the specific, complex nature of hierarchical strings—like web addresses with multiple levels of subdomains—without losing precision. The ledger, which records the changes, was able to compress the information efficiently, sharing common parts of the strings to save space, much like a library catalog that groups books by their shared titles rather than listing every single page number.

One of the most significant aspects of this work is the sheer scale at which it was verified. The team did not just claim the system worked; they built a complete, independent verification process that checked every single answer. They ran the system five times, each time with a fresh start, and confirmed that the results were consistent. They also tested the system under different error tolerances, showing that it could be tuned to be extremely precise or slightly more flexible depending on the needs of the application. When the data became too large or the ledger grew too complex, the system demonstrated a way to rebuild itself, creating a new snapshot and clearing the ledger, effectively resetting the clock while preserving the accuracy of the data. This lifecycle management is crucial for any system that needs to run continuously in the real world.

The study concludes that it is possible to create a dynamic index for complex string data that remains accurate without constant retraining. By separating the stable, frozen map from the dynamic ledger of changes, the researchers have found a way to keep the system honest. The ledger acts as a bridge, translating the static predictions of the past into the living reality of the present. This approach offers a new path for managing the ever-growing volume of digital information, ensuring that even as the data shifts and changes, the computer always knows exactly where to look. The results are not a magic solution that eliminates all costs, but they provide a solid, verified foundation for building systems that can handle the complexity of the modern web with confidence and precision.

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

1. Problem Statement

Learned indexes estimate the position of a key in a sorted order using a machine learning model, typically reducing the search space to a bounded interval. However, dynamic operations (insertions and deletions) introduce a fundamental challenge: they shift the "live rank" of existing keys even if the keys' values remain unchanged. This "coordinate drift" invalidates the error guarantees of a frozen model, as the predicted rank no longer aligns with the true rank.

Existing dynamic learned indexes often rely on mutable models or specific data layouts to absorb updates, which can compromise the original error bounds or incur high retraining costs. Furthermore, handling variable-length hierarchical strings (such as URLs or file paths) requires strict bytewise lexicographic ordering, which is difficult to preserve when using approximate numerical features for prediction. The core problem addressed is how to maintain a verified error certificate for a frozen model while supporting arbitrary insertions and deletions in a dynamic, hierarchical string index.

2. Methodology: HRT-LI

The proposed solution, Hierarchical Rank-Transport Learned Index (HRT-LI), decouples the static model guarantee from the dynamic state of the data. It achieves this through three primary mechanisms:

A. Base Snapshot and Exact String Order

The system begins with a sorted, duplicate-free base set ( $S_0$ ) and a model ( $p_0$ ) that has been exhaustively validated to satisfy $|p_0(k) - \text{rank}_0(k)| \le \epsilon$ for all $k \in S_0$ .

Lexicode Representation: To ensure exact ordering for variable-length strings, the system uses a sparse-radix lexicode. It transforms byte strings by shifting values and appending a terminator, preserving strict bytewise lexicographic order (including prefix cases like /a vs /a/b) without relying on lossy numerical features for the final ordering decision.

B. Signed Prefix-Mass Ledger

Instead of retraining the model, HRT-LI maintains a signed radix ledger that records the difference between the current state ( $S_t$ ) and the base snapshot ( $S_0$ ).

Weighted Mutations: Insertions are assigned a weight of $+1$ , and deletions of base keys are assigned $-1$. Re-inserting a deleted key or deleting a newly inserted key results in an "annihilation" of the ledger entry (net weight 0).
Prefix Mass Calculation: The ledger computes the strict-prefix sum ( $\Delta_t(k)$ ) of these weights. This represents the exact number of keys that have been added or removed strictly before key $k$ in the current live set.
Rank Transport: The live rank is calculated by adding this correction to the base rank:
$\text{rank}_t(k) = \text{rank}_0(k) + \Delta_t(k)$
Crucially, the predicted rank is also transported: $p_t(k) = p_0(k) + \Delta_t(k)$ . Since the same correction is applied to both the prediction and the ground truth, the error bound remains invariant:
$|p_t(k) - \text{rank}_t(k)| = |p_0(k) - \text{rank}_0(k)| \le \epsilon$
This allows the original error certificate to survive arbitrary updates for all surviving base keys.

C. Guarded Recovery and Implementation

Base Keys: For keys present in the base snapshot, the system uses the transported prediction to define a bounded search interval, followed by exact binary search within that interval.
Inserted Keys: Keys not in the base snapshot do not inherit the model's error guarantee. Their exact rank is computed via exact counting of base keys below them, adjusted by the ledger's signed counts.
Packed Architecture: The implementation uses memory-mapped files for the base keys and a path-compressed byte radix tree for the ledger. It employs "guarded recovery," where the model guides the search, but exact string comparisons and bracket checks ensure correctness even if the model prediction is slightly off or if the ledger state changes.

3. Key Contributions

The paper outlines four main contributions:

Exact Hierarchical Formulation: A mathematical formulation of rank transport that separates order, prefix-mass, annihilation, and certificate preservation for variable-length strings.
Prefix-Mass Radix Ledger: A data structure that represents shared byte prefixes once, supporting efficient insertion, deletion, and exact live rank/count queries without treating lossy features as the ordering authority.
Numerically Certified Implementation: A packed implementation featuring guarded learned base recovery, explicit binary-search controls, and exception-safe signed-ledger mutations.
Real-Scale Evaluation: A comprehensive evaluation on 200 million natural Common Crawl host strings, including 100,000 held-out insertions and 100,000 base deletions. The study verifies 164 million timed answers against independent source-position oracles and performs exhaustive error checks across requested bounds ( $\epsilon = 16, 32, 64, 128$ ).

4. Results

The evaluation, conducted on a 200-million-key dataset, yielded the following findings:

Certificate Preservation: The system successfully maintained the error certificate for all surviving base keys after extensive mutations. Inverse writes (re-inserting deleted keys) correctly restored the ledger to zero, verifying the annihilation semantics.
Correctness: All 164 million timed answers matched their expected source positions. The system handled exact live ranks and range counts correctly, even for keys not present in the original base.
Performance vs. Specialists:
- In a comparison with specialized string indexes (ART, HOT, LITS) on a 10-million-key natural pool, HRT-LI was slower for membership lookups and mixed-write workloads.
- However, HRT-LI provided order-statistic capabilities (exact rank, predecessor, range count) that the baseline ART/HOT bindings in the study did not natively support.
- The "learned recovery" path was approximately 25–33% faster than a "binary-only" recovery path for live membership and rank queries, though this internal ablation did not establish competitive superiority over other specialized indexes.
Memory and Overhead: HRT-LI requires more memory and insertion time than simple sorted vectors due to the model and ledger overhead. The ledger implementation using linear sibling scans was found to be more space-efficient than a full Fenwick tree approach for the tested workloads.
Consolidation: A separate lifecycle audit demonstrated that the system can be rebuilt (consolidated) to a new base generation, verifying the new base and clearing the ledger, though this process is currently a blocking, offline operation.

5. Significance and Claims

The paper positions HRT-LI not as a drop-in replacement that outperforms all existing indexes in raw throughput, but as a correctness-preserving architecture for dynamic learned indexing.

Theoretical Contribution: It establishes that a frozen model's error certificate can be mathematically composed with exact dynamic order statistics for hierarchical strings. The "rank transport" identity proves that retraining is a cost/representation decision, not a logical necessity for maintaining error bounds after updates.
Practical Implication: The system offers a way to use learned indexes in dynamic environments where the cost of retraining is prohibitive or where strict error guarantees for the base data are required.
Modesty of Claims: The authors explicitly state that the results do not establish competitive throughput superiority over specialized indexes like ART or HOT for membership queries. The value proposition is the composition of a certified base with dynamic updates and the provision of exact rank/range operations, rather than raw speed. The paper concludes that while the core contract is proven at scale, practical deployment requires further work on consolidation triggers and online installation protocols to manage the growing delta.