Bounding the Last Mile: Efficient Learned String Indexing
This addresses memory-intensive database applications by providing a more efficient string indexing method.
The paper tackles the problem of efficiently indexing strings in databases by introducing the RadixStringSpline (RSS) learned index structure, which approaches or exceeds the performance of traditional string indexes while using 7-70× less memory.
We introduce the RadixStringSpline (RSS) learned index structure for efficiently indexing strings. RSS is a tree of radix splines each indexing a fixed number of bytes. RSS approaches or exceeds the performance of traditional string indexes while using 7-70$\times$ less memory. RSS achieves this by using the minimal string prefix to sufficiently distinguish the data unlike most learned approaches which index the entire string. Additionally, the bounded-error nature of RSS accelerates the last mile search and also enables a memory-efficient hash-table lookup accelerator. We benchmark RSS on several real-world string datasets against ART and HOT. Our experiments suggest this line of research may be promising for future memory-intensive database applications.