Alex Bowe

I've sort of made plans for the last four chapters, sort of :). I would have loved to write about Wavelet trees, but a lot has already been written about them. If you're into succinct data structures and are looking for something more practical, check out this blog on Succinct de Bruijn Graphs (https://www.alexbowe.com/succinct-debruijn-graphs/).

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/

At first I found intriguing to see no mention of SDSL[1], which probably is one of the best libraries in the field of compressed data structures, including compressed bitmaps. Probably because the index is built to answer a "different kind of queries". There is a blog commenting on those "other" queries[2]. In the same blog the author discusses some other compressed data structures included in the library. 1: https://github.com/simongog/sdsl-lite 2: http://alexbowe.com/rrr/

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…

Start with Wavelet trees (much more intuitive): https://www.alexbowe.com/wavelet-trees/ The matrix version is just an implementation detail to store the tree in a less tree-like shape so you don't need as many pointers.

> There is a lot of research into concise data structures for a very specific set of operations for DNA processing See: https://alexbowe.com/fm-index/ Impl: https://github.com/shibukawa/fm-index.jsx More: https://news.ycombinator.com/item?id=22544718

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/

This scale is pretty small and can be done on my laptop. If you need to do such operations at a truly large scale, this is an interesting article: http://alexbowe.com/rrr/ C++ implementation: https://github.com/simongog/sdsl-lite/blob/master/README.md

The FM-Index changed the way I think about searching. http://alexbowe.com/fm-index/

Your blog posts about wavelet trees (http://www.alexbowe.com/wavelet-trees) and RRR (http://www.alexbowe.com/yarrr-me-hearties) are very clear and well written! I've been thinking of writing some blog posts myself for a long time, now I think I will just link to yours. EDIT: I think WTs should really have a page on Wikipedia...

My bad, I got that wrong. The translated array should be: 1 0 2 3 0 3. I am correcting the article now. For a non-rushed, accurate description please look at: http://www.alexbowe.com/wavelet-trees Edit: Got it wrong again... I guess this is why we have computers and debuggers!

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+S…

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/