Some thoughts on the paper as a researcher in space-efficient data structures: When we design compressed data structures, we generally assume that the data ha

Some thoughts on the paper as a researcher in space-efficient data structures: When we design compressed data structures, we generally assume that the data has been generated by some statistical or combinatorial model. Then we design the encoding for the data and the data structure itself, assuming that model. There are often principled ways to achieve that. We also need an index to find the correct block of data to decompress. This is where we often have to resort to ugly hacks. The constant-time select structure for bitvectors is a good example. To find the i-th 1-bit, we split the bitvector into blocks and superblocks of certain number of 1-bits. Then we have different ways to encode the blocks and superblocks, depending on whether they are dense or sparse. There are lots of special cases, but the index still often ends up wasting space for redundant information. We could adapt to the data better by adding even more special cases, but that quickly becomes impractical. The key idea in this paper is that data structures often contain components that are learnable. For example, B-trees and rank/select indexes are essentially increasing functions, which should be easy to learn. We can afford having more special cases, if we don't hard-code them but handle them as data. This in turn can make the indexes smaller and faster. The drawback is index construction, which requires a lot of resources. (This is a common problem with sophisticated data structures.) Spending minutes to index 200 million elements can be justified in some applications, but it's way too much in other applications.