Succinct Data Structures

…d summary, and the tech is solid. It's just older than what excites me; a lot of progress has been made in 20 years and the majority of it hasn't found commercial applications. But here is a citation root for a lot of amazing work in this space: link My absolute hero Edward Kmett gave a talk stitching a lot of this work together a long time ago: link to this video . I have no idea if he's pursued it, it's just one of his many talks that left me with an incredibly lasting impression. Variants of this technique work for arbitrary documents and structures, work better at very high volume, have cache oblivious properties, and support transactions. Universal indexes that are reasonably good for all querie…

A binary tree doesn't have to be encoded using pointers. There are more efficient representations that /u/edwardkmett describes in this talk

I highly recommend watching kmett's video. I'm currently part way through watching right now. Myself, I've actually learnt a lot on this topic from watching his older videos and then doing my own reading on it. Here's an older video, although the low compression quality will require some intense concentration. link to this video

I find it mildly amusing that people are competing on the fastest decoder of horribly inefficient format. Don't get me wrong, I like e.g. ZX Spectrum demos, but the practical utility of such endeavor is questionable. But that aside, I wonder how this compares to the compressed indexes approaches (see link to this video and link ), obviously, once the index is built.

I first heard of the concept of succinct data structures from Edward Kmett, a famous Haskeller behind many popular Haskell libraries. He gave a talk on succinct data structures a long time ago: link to this video

Great post. There's a markup problem with the link to Succinct Data Structures, you included two links separated by a space: * link to this video * link to this video