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

CREATORFaruk Alpay, Levent Sarıoğlu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE135695
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.29061

Browse the full library · About the Tower of Babel