Table of Contents 1Sapling 2PLA-Index 3LISA: learned index Let’s summarize some tools for efficiently searching suffix arrays. 1 Sapling Sapling (Kirsche, Das, and Schatz 2020) works as follows: Choose a parameter \(p\) store for each of the \(2^p\) $p$-bit prefixes the corresponding position in the suffix array. When querying, first find the bucket for the query prefix. Then do a linear interpolation inside the bucket. Search the area \([-E, +E]\) around the interpolated position, where \(...
