Alex Bowe

I'm most definitely not an expert in this area, but I have recently taken interest in learning about "succinct data structures", which from what I understand have their place in bioinformatics.

It's been a challenging topic to learn about, because most of the information comes from Computer Science papers and articles where the information is presented in a very formal, mathematical way, which I am just not used to.

Normally when thinking about data structures and algorithms, we're mostly concerned with optimizing for speed. Space complexity is not usually as big of a consideration. Succinct data structures are all about creating ways to achieve good runtime performance while representing the data in a "compressed" format. I think this comes in handy when doing things like DNA sequencing since data sets are so large.

I'm excited to check out some of links in the post, and in case any one else is interested in learning more about succinct data structures, here's a few resources I'd recommend:

Prof. Ben Langmead's YouTube channel: https://www.youtube.com/user/BenLangmead/featured

Alex Bowe's blog has some good content: https://www.alexbowe.com/articles/

Prof. Erik Demaine's "succinct" lectures from his adv. data structures course at MIT on YouTube: https://www.youtube.com/watch?v=3Y2weLDiUWw

Edward Kmett's Haskell live coding session going into some details about succinct: https://www.youtube.com/watch?v=9MKEmNNJgFc

There's also a lot of research papers, which you…

Gosh, I have a few!

Fistly, wavelet trees! Wavelet trees with something like RRR encoding for the bit vectors lets you work with massive datasets in positively tiny space and constant time. They're not even expensive to construct! My favorite introduction to the whole space of rank/select-friendly structures is Alex Bowe's tutorial: https://alexbowe.com/wavelet-trees/

I constantly agitate for people to realize that we now have an algorithm for O(n) generalized sorting. It's called discrimination sort, and while it's a complex subject its quite elegant once you internalize the algorithm. There's a talk by Prof. Henglein here: https://www.youtube.com/watch?v=sz9ZlZIRDAg

2017 saw the recommendation of a truly phenomenal approach to indexing data, using simple leaning structures. These indexes are poorly explored, there's still a ton of headroom here, but the paper is an incredibly cool read and very approachable: https://arxiv.org/abs/1712.01208

Another really cool family of algorithms and associated structures in distributed systems is CRDTs. They're poorly understood, but in research they have largely superseded operational transforms. The Wikipedia page branches off into lots of good research: https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type

If we slightly broadened the lens of what is an algorithm, my favoriate category-theoretic approaches to solving problems include Recursion Schemes which are a technique to totally separate the specification of…

There's a whole set of interesting data structures that are not very well known: succinct data structures[1]. The idea is simple: we want to store data in a compressed form, but also perform certain operations quickly without uncompressing.

These can be very useful for certain applications. The article on "Cramming 80,000 Words into a JavaScript File"[2] is a nice example. It shows you how you can store a compressed trie in memory but still use it. I also like this[3] series of blog posts leading up to wavelet trees.

These certainly count as obscure data structures, unlike many of the ones listed on SO. I had never even considered the idea of compressing data in memory like this, much less encountered actual examples of succinct data structures! I have to thank Edward Kmett for introducing me to the whole field.

These data structures are important not just because they're neat themselves, but because they got me to think a new way. In particular, I realized that using pointers all over the place--to represent things like trees--is not always efficient. Instead of parsing data, it might be better to store it as a blob of some sort with a binary index. Just starting to consider details like that is valuable all on its own.

[1]: http://en.wikipedia.org/wiki/Succinct_data_structure

[2]: http://stevehanov.ca/blog/index.php/?id=120

[3]: http://alexbowe.com/rrr/ and http://alexbowe.com/wavelet-trees/

There's a very good blog post for the implementation details here: http://alexbowe.com/wavelet-trees/ I had a decent implementation in Python, but it's on my old macbook that I would need to dig up. If you're interested you can add me on telegram: @rightcheek.

Now to go with Wavelet trees you may or may not need to know about suffix arrays and optimal suffix array construction. Take a look at this: https://en.wikipedia.org/wiki/Suffix_array This is what's going to give you space efficiency in combination with a wavelet tree. And the wavelet tree also gives you good rank/select efficiency.

Edit: Here's a suffix array construction algorithm implementation I did (not sure if it's fully correct) https://github.com/ethanwillis/comp7295_final/blob/master/saca.py It is based on this paper: https://local.ugene.unipro.ru/tracker/secure/attachment/12144/Linear+Suffix+Array+Construction+by+Almost+Pure+Induced-Sorting.pdf

I've looked into succinct data structures in the past [0] and not been totally satisfied with the stated time/space complexity (singling out the linked example because a lot of the literature is built on something similar).

Picking on the O(1) time complexity for rank queries, if the superstructure is constant sized then surely each block would have super-constant size and thus couldn't be walked in O(1) time, but conversely if the superstructure has super-constant size it itself can't be walked in O(1) time. In all cases the runtime of such a rank operation is greater than O(1).

Would somebody be willing to ELI5 what I'm missing?

[0] https://alexbowe.com/rrr/

In my field (bioinformatics), there is a trend of using a single hash function, an over-sized bloom filter which is then compressed with something like entropy optimal RRR[1] or RoaringBitmap bit vectors.
The resulting bloom filter ends up taking the same space than a properly sized bloom filter. There is two advantages: knowing the size of the set in advance is not necessary, and a single hash computation and memory access per query. However updates are not well supported.

[1] Raman, R., Raman, V., & Rao, S. S. (2002, January). Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. A blog post: https://alexbowe.com/rrr/