5 ms·

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

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/ 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 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 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 https://en.wikipedia.org/wiki/Conflict-free_replicated_data_... 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 recursive algorithms over data structures from both the structures and the code that the algorithm runs to compute a result (Patrick from Github has a great series on them here: https://blog.sumtypeofway.com/ https://blog.sumtypeofway.com/). I also love the modern and rapidly growing "Ghosts of Forgotten Proofs" as a way to let the compiler assert you've properly built and/or terminated values: https://github.com/matt-noonan/gdp-paper/releases/download/june-2018-draft/gdp.pdf https://github.com/matt-noonan/gdp-paper/releases/download/j...

GordonS 8y ago
Do you have any real-world examples where wavelet trees are used? They look really interesting, I'm just not sure where I'd ever use them!
andrewla 8y ago
Discrimination sort seems interesting, though couched in such complex terms that it's hard to follow (admittedly, I read the paper[1] instead of watching the video). As I understand it, it's a generalized MSD radix sort, and the difference in complexity analysis from traditional pairwise sorts is what the N stands for. For strings, we know that a fixed-size prefix (say a character) that can take on a known finite set of values is capable of discriminating; that is, being a partial order on strings. From this we can construct a radix sort on strings that never has to revisit a character. So the net running time is approximately O(total number of characters in all strings). In contrast, a naive comparison sort may operate in O(nlogn) comparisons, but each comparison has a cost proportional to the length of the string, since we have to re-compare from scratch, such that this works out closer to O(log n * total number of characters in all strings). My recollection is that MSD radix sorts are somewhat space-intensive, especially if we want them to be stable. I think O(n) space is required. Nonetheless, this is very interesting. [1] https://pdfs.semanticscholar.org/7e49/0023f84845c750f4a04b7dca8a0225d3e5d1.pdf https://pdfs.semanticscholar.org/7e49/0023f84845c750f4a04b7d...

GordonS 8y ago

Do you have any real-world examples where wavelet trees are used? They look really interesting, I'm just not sure where I'd ever use them!

andrewla 8y ago

Discrimination sort seems interesting, though couched in such complex terms that it's hard to follow (admittedly, I read the paper[1] instead of watching the video). As I understand it, it's a generalized MSD radix sort, and the difference in complexity analysis from traditional pairwise sorts is what the N stands for. For strings, we know that a fixed-size prefix (say a character) that can take on a known finite set of values is capable of discriminating; that is, being a partial order on strings. From this we can construct a radix sort on strings that never has to revisit a character. So the net running time is approximately O(total number of characters in all strings). In contrast, a naive comparison sort may operate in O(nlogn) comparisons, but each comparison has a cost proportional to the length of the string, since we have to re-compare from scratch, such that this works out closer to O(log n * total number of characters in all strings). My recollection is that MSD radix sorts are somewhat space-intensive, especially if we want them to be stable. I think O(n) space is required. Nonetheless, this is very interesting. [1] https://pdfs.semanticscholar.org/7e49/0023f84845c750f4a04b7dca8a0225d3e5d1.pdf https://pdfs.semanticscholar.org/7e49/0023f84845c750f4a04b7d...