Residual-Entropy Accounting for Routed Atom-Budgeted Learned Indexes
Faruk Alpay, Levent Sarıoğlu · 2026
Read Residual-Entropy Accounting for Routed Atom-Budgeted Learned Indexes by Faruk Alpay, Levent Sarıoğlu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-29061.txt.
Description
Faruk Alpay and Levent Sarioglu study predecessor and rank search in a routed, atom-budgeted learned index with certified repair. A directory routes queries to ranges, a predictor returns a certified rank window, and repair closes the rest by comparison. Their core measure is conditional residual answer entropy, the uncertainty left once leaf, predictor, certificate, and prior data are known. They prove a two-sided accounting theorem tying that measure to query time scale for that design. Benchmarks against PGM-index, RadixSpline, and binary search expose overheads, not speed gains.
Catalog record
| CREATOR | Faruk Alpay, Levent Sarıoğlu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 135695 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.29061