9 ms·

Succinct data structures

588 points by pavel_lishin 2y ago

svachalek 2y ago
Wow, this is really fascinating. I guess it all comes down to how it's doing select and rank in constant time, which is probably some clever bit arithmetic. I'll have to look into how that works.
- zellyn 2y ago
  Some of it is moving or has moved down to the instruction sets: https://vaibhavsagar.com/blog/2019/09/08/popcount/ https://vaibhavsagar.com/blog/2019/09/08/popcount/
- judofyr 2y ago
  I can speak a bit about one of the approaches: "Practical Entropy-Compressed Rank/Select Dictionary" by Daisuke Okanohara and Kunihiko Sadakane. This presents two different variants: One for dense (i.e. more than 50% of the bits are set) and one for sparse. The dense implementation is basically based around partitioning them into "blocks" of a given size and then you can find the block by doing `block[idx / block_size]`. It then also groups each block into sub-blocks which helps you even further. All of these are additional data structures (very much like an index) which are stored next to the regular bitset. You use the blocks/sub-blocks to find roughly where in the bitset you are and then use a algorithm for finding the value in a given machine-word. The sparse implementation treats the bitset as an ordered list of numbers (e.g. 100001001 is interpreted as 0, 5, 8) and then it stores those numbers using Elias-Fano encoding. The higher bits of the Elias-Fano encoding happen to be dense and hence we can use the previous dense implementation on that higher bits and then combine it with the lower bits. I'm also aware of https://arxiv.org/abs/1706.00990 https://arxiv.org/abs/1706.00990 which is more about how to do this most efficiently at a machine-word level. "Engineering Compact Data Structures for Rank and Select Queries on Bit Vectors" is another quite recent paper which I haven't fully digested yet.
kccqzy 2y ago
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: http://youtu.be/uA0Z7_4J7u8 http://youtu.be/uA0Z7_4J7u8
- eru 2y ago
  Ed is great. He's not just a Haskeller, but has also done interesting work in the likes of C++ and 6502 assembly amongst others.
- kreyenborgi 2y ago
  His code on this seems to be https://hackage.haskell.org/package/structures https://hackage.haskell.org/package/structures There is also HaskellWorks packages like https://hackage.haskell.org/package/hw-xml https://hackage.haskell.org/package/hw-xml
  - kccqzy 2y ago
    He also has https://github.com/ekmett/succinct-binary https://github.com/ekmett/succinct-binary
- mrkeen 2y ago
  My Haskell attempt at Wavelet Matrices: https://github.com/jahaynes/waveletto https://github.com/jahaynes/waveletto
- johnpmayer 2y ago
  Whoa - I was there! This was at a small elm-lang meetup; Prezi hosted this while Evan was working there. Thank you for sharing this link!
tux3 2y ago
I really like the article, but it would benefit from some numbers or complexity estimates to get some intuitive sense of what the cost is. Am I paying 30% overhead for this particular index or that wavelet matrix? Is it double the memory use? Or is it O(log N)? No idea! "doesn't use much more space" could mean a lot of different things!
- judofyr 2y ago
  "Succinct data structure" does have a very strict definition which probably answers some of your questions: https://en.wikipedia.org/wiki/Succinct_data_structure https://en.wikipedia.org/wiki/Succinct_data_structure. It's all about being close to the theoretical minimum. > Am I paying 30% overhead for this particular index or that wavelet matrix? Nope! That would not fit the definition. That would be a "compact data structure" according to this definition.
  - jltsiren 2y ago
    You should be careful when using asymptotic bounds with more precision than about O(sqrt(n)). The bounds ignore constant factors, and the constant factors could be more significant than slowly growing non-constant factors for reasonable values of n. It's also very common in algorithm design that improving the asymptotic bounds and making the algorithm faster (or the data structure smaller) are orthogonal (or even opposite) goals. Real computers have complex performance characteristics and fixed word lengths, and it's rarely a good idea to implement a theoretical algorithm exactly as described. Succinct data structures often have a number of internal parameters. In a theoretical parameterization, those parameters may be described as being O(log n), O(log^2 n), or O(log log n). In a concrete implementation, it may be a good idea to use constant approximations for some nontrivial (such as 2x) performance gains. O(log n) could become 32 or 64, O(log^2 n) could become 1024 (or a power-of-2 multiple), and O(log log n) could become 4 or 8. And then, if you parameterize the succinct data structure with these constants, the space overhead becomes a constant fraction.
    - senderista 2y ago
      Succinct data structures require the extra space (above the information-theoretical minimum) to be an additive term of o(n) bits (little O, not big O). That just means that the extra space grows more slowly than n, as n approaches infinity, so their ratio (extra space)/n approaches 0 in the limit.
judofyr 2y ago
Succinct data structures are very fun! If anyone is interested, I've implemented some of this in Zig: https://github.com/judofyr/zini https://github.com/judofyr/zini. The main thing this implements is a minimal perfect hash function which uses less than 4 bits per element (and can respond to queries in ~50 ns). As a part of that I ended up implementing on of these indexes for constant-time select(n): https://github.com/judofyr/zini/blob/main/src/darray.zig https://github.com/judofyr/zini/blob/main/src/darray.zig. It feels kinda magic implementing these algorithms because everything becomes so tiny!
- thomasmg 2y ago
  For Java, C++, and Rust there is also https://sux.di.unimi.it/ https://sux.di.unimi.it/ maintained by Sebastiano Vigna, a professor from Italy. Together with his student (I also helped a bit), he wrote a paper about RecSplit, a minimal perfect hash function (MPHF) algorithm I have invented: https://arxiv.org/abs/1910.06416 https://arxiv.org/abs/1910.06416 - that algorithm uses around 1.56 bits per key. But it is quite slow. In January 2020 I presented the paper at a conference, that was right before the pandemic. The algorithm with the least memory usage (and much faster as well) is now Consensus-RecSplit: https://arxiv.org/abs/2502.05613 https://arxiv.org/abs/2502.05613 - it can do 1.44 bits per key, which is right at the theoretical minimum (meaning, there is no good way to shrink it further). At least a small part of my original invention is still used there, nice. The fastest current MPHF is probably PtrHash https://arxiv.org/abs/2502.15539 https://arxiv.org/abs/2502.15539 - both papers were published last month (February 2025) by the way.
  - rurban 2y ago
    I'm working on making pthash faster and more practical. I can compile the data and code to C++, send efficiently store the keys also to be able to eliminate false positives. https://github.com/rurban/pthash https://github.com/rurban/pthash
mzs 2y ago
The word count seems artificially increased in the post. Here's a succinct explanation: https://www.eecs.tufts.edu/~aloupis/comp150/projects/SuccinctTreesinPractice.pdf https://www.eecs.tufts.edu/~aloupis/comp150/projects/Succinc...
- pegasus 2y ago
  I didn't think that at all. In fact I found it very readable and prefer it over the drier presentation you linked. To each its own, I guess, but there's really no need to infer ulterior motives.
abetusk 2y ago
My goto library for succinct data structures is SDSL-Lite [0]. [0] https://github.com/simongog/sdsl-lite https://github.com/simongog/sdsl-lite
qazxcvbnm 2y ago
Note that succinct data structures may not be faster than conventional structures if your dataset fits in memory http://www.cs.cmu.edu/~huanche1/slides/FST.pdf http://www.cs.cmu.edu/~huanche1/slides/FST.pdf . Of course, for large datasets where storage access times dominate, succinct data structures win all around. In any case, succinct trees are works of art (If I recall https://arxiv.org/pdf/1805.11255 https://arxiv.org/pdf/1805.11255 was a good exposition) (just look at how that RMQ works)!
- yvdriess 2y ago
  True, but it depends on what you mean with fitting in memory. Succinct datastructures are used in genomics (e.g. bwa, megahit exome sequencer) because N is so large that you're actually hitting asymptotic behavior. For memory latency it can by making your memory footprint fit in LLC or a single node; cross-node NUMA latencies are typically enough to absolutely tank performance. It can theoretically also help in massively parallel access situations where bandwidth becomes a limiting concern. Although, I intuit we would need near-memory hardware to perform the rank+select. Otherwise the latency of the multiple dependent accesses will kill your performance again, cfr previous point. With a lot of parallel accesses, bandwidth could also be an issue in conventional structures.
- hinkley 2y ago
  As an application grows the features start to interact. We tend to not be paying much attention to how the old code 'fits into memory' while we are writing new code that also has to fit into memory. Once you have an entire system written the benefits of having four interacting features that each fit into a third of memory may be bigger than you think. And I don't know how well Intel's hardware level profiling information reveals that but I know for sure that the profiling tools that ship with most commercially viable programming languages never do. They blame issues on whoever touched the system last, and if that is an epicycle or a metastable situation then the apparent guilty party may be a frame-up, while the real culprit goes unpunished. As an example: if your workflow has a step that eventually needs to use 40% of available memory to solve a problem, then GC will almost always trigger within that step of the process, rather than in the other 60% of memory being systematically wasted by heaps of inefficient code in the leadup to this step, because the top of the memory sawtooth will almost always occur within that part of the call graph. But because the 40% is your intrinsic complexity, people's brains shut off the moment a cost is attributed to unavoidable work, instead of the avoidable work that really caused the majority of the problem.
lostmsu 2y ago
Way better detailed explanation: https://stackoverflow.com/questions/72580828/what-is-a-succinct-rank-data-structure-how-does-it-work https://stackoverflow.com/questions/72580828/what-is-a-succi...
- zero_shift 2y ago
  That IS excellent - thank you
- topspin 2y ago
  Yes, that's great. This part: "Intuitively, a succinct data structure is one whose space usage equals the space needed to write out the data, plus something that grows more slowly than that. If you're familiar with little-o notation, a succinct data structure is one whose space usage is X + o(X), where X is the number of bits needed to write out the data itself." Brings to mind COBS encoding, which does this for streams bytes containing arbitrary length "packets" or similar.
- adgjlsfhk1 2y ago
  This is great! I love both how far you can push this and get meaningful improvements, and how it's totally overkill for anything we'll ever be able to implement on a physical computer. The hardware focused approach is to use popcnt for a base size of 512 (since cache architecture will make you fetch that much memory if you touch the original array anyway). We then can store 1 UInt16 prefix sum per 512 bits (n/32 bits overall), and if we have more than 2^16 bits in total, we can store UInt64 prefixes every 2^16 bits (n/1024 bits overall). Theoretically, this approach uses O(nlogn) bits as opposed to o(n) for the theoretical approach, but in practice, for <2^64 bools, the actual storage ens up being n/32+n/1024 which is pretty hard to beat. The theoretical approach gets it's wins from making extremely clever use of the difference between O(loglog(n)) and O(1), but unfortunately for the foreseeable future, logn < 64 and loglog(n) < 6, so all the subtlety gets swallowed up into the base case of a single popcnt instruction.
- atiedebee 2y ago
  This is great. A very understandable explanation, thanks for sharing!
cxie 2y ago
Just spent my morning diving into succinct data structures after seeing this. The memory efficiency is incredible - especially the balanced parentheses tree representing a full node tree in just 2 bits per node! I've been working on a project parsing large (10GB+) XML files for scientific data analysis, and our current approach burns through RAM like crazy. Has anyone here successfully implemented these structures in production systems? The wavelet matrix concept seems particularly promising for our text-heavy workloads. I'm curious if the constant-time operations actually hold up under real-world conditions or if there are hidden performance cliffs. This feels like one of those CS concepts that should be more widely known but somehow got overlooked by mainstream programming. Kind of like how bloom filters were obscure until suddenly every system was using them.
- MortyWaves 2y ago
  When I’ve dealt with huge files in .NET, the usual approach is to stream the file such that only some of it is in memory at once. This way you can process files hundreds of GBs. Of course, if you truly need them all in memory at once for some reason I genuinely can’t think of, then you’d need something else. Does your language have the concept of streaming files?
  - crazygringo 2y ago
    If you're streaming something row-based like a CSV, or a zipped CSV, then that's usually easy. But when you get to hierarchical data structures like JSON/protobuf there very often simply isn't a streaming library available. There's a library function to decode the whole thing into an object in memory, and that's all. Nothing prevents streaming in theory, it's just far more complicated to write that library.
    - dilap 2y ago
      protobuf sure, but streaming libraries for json (and xml, as in the parent) are extremely common. not harder (maybe even easier) than non-streaming to write, tho more cumbersome to use, so something you'd reach for only if you specifically need it ('cuz of memory constraints) e.g. standard go json library https://pkg.go.dev/encoding/json#example-Decoder.Decode-Stream https://pkg.go.dev/encoding/json#example-Decoder.Decode-Stre...
MortyWaves 2y ago
> This is a field that seems to have emerged in computer science relatively recently; many of the important data structures were invented in the last 25 years. This is crazy!
sujayakar 2y ago
I really love this space: Navarro's book is an excellent survey. Erik Demaine has a few great lectures on succinct data structures too: L17 and L18 on https://courses.csail.mit.edu/6.851/spring12/lectures/ https://courses.csail.mit.edu/6.851/spring12/lectures/
yurivish 2y ago
I also emailed Gonzalo Navarro once to ask a question, and we had a great discussion and ended up writing a paper together about the answer. [1] Another paper of his that I really like combines a few elegant ideas into a simple implementation of bitvector rank/select: https://users.dcc.uchile.cl/~gnavarro/ps/sea12.1.pdf https://users.dcc.uchile.cl/~gnavarro/ps/sea12.1.pdf During this time I got really excited about succinct data structures and wrote a Rust library implementing many bitvector types and a wavelet matrix. [2] My interest came from a data visualization perspective -- I was curious if space-efficient data structures could fundamentally improve the interactive exploration of large datasets on the client side. Happy to chat about that if anyone's curious. [1] Paper: https://archive.yuri.is/pdfing/weighted_range_quantile_queries.pdf https://archive.yuri.is/pdfing/weighted_range_quantile_queri... though it's pretty hard to understand without some background context. I've been meaning to write a blog post explaining the core contribution, which is a simple tweak to one of Navarro's textbook data structures. [2] The rust version is here: https://github.com/yurivish/made-of-bits/tree/main/rust-playground/made-of-bits https://github.com/yurivish/made-of-bits/tree/main/rust-play... and an earlier pure-JS implementation is here: https://github.com/yurivish/made-of-bits/tree/main https://github.com/yurivish/made-of-bits/tree/main
- sitkack 2y ago
  Reading a Gonzalo Navarro paper is like going for walk, taking a shower and having a wonderful coffee. It literally sets the mind on fire. https://dblp.org/pid/n/GonzaloNavarro.html https://dblp.org/pid/n/GonzaloNavarro.html
  - SoftTalker 2y ago
    Well not literally.
    - penguin_booze 2y ago
      Well, literally doesn't mean literally anymore--literally.
      - 2y ago
eqvinox 2y ago
There's a relative of this in making in-memory node representation efficient for large structs that have a bunch of rarely-used fields: chunk up memory in units (most reasonably 8 bytes/pointer size), allocate offsets for rarely-used fields in ascending order, and then use bitmasks to indicate which fields are present. (Note the bits correspond to units, not fields; a 16-byte field would use 2 adjacent bits in the bitmask.) The trick is that masking & popcount (both low-cycle CPU instructions in most modern CPUs¹) make this quite fast to access and thus suitable for in-memory representation. The intended use is when presence of optional fields is known at allocation time and doesn't change afterwards, i.e. some object is built up into a dynamically allocated buffer whose size is shrunk down by omitting fields. Changing which fields are present afterwards requires reallocating the thing, which tends to make the entire pattern pointless. ¹ the real annoyance here is that almost all x86_64 CPUs have POPCNT, except the absolute earliest ones, but if you build e.g. some package for a Linux distribution without any CPU optimization flags it'll use a library fallback popcount routine rather than the instruction :(
- adgjlsfhk1 2y ago
  thankfully a number of distros are starting to ship packages for x86v2 by default (basically everything Core 2 and newer) which fixes this finally.
bo1024 2y ago
With advanced CS topics, it often works to search for "<topic> lecture notes".
deleted 2y ago
[deleted]
dsffsad 2y ago
[flagged]
senderista 2y ago
I'm sure it's out of date in some areas by now, but I have Navarro's textbook[1] and it's a great survey. (The only criticism that comes to mind is that it weirdly shortchanges Elias-Fano encoding[2], which is hugely important in practice but relegated to just an offhand sentence or two in the book.) [1] https://www.cambridge.org/core/books/compact-data-structures/68A5983E6F1176181291E235D0B7EB44 https://www.cambridge.org/core/books/compact-data-structures... [2] https://vigna.di.unimi.it/ftp/papers/QuasiSuccinctIndices.pdf https://vigna.di.unimi.it/ftp/papers/QuasiSuccinctIndices.pd...
hawaiianSpork 2y ago
How do succinct data structures do with vector operations on cpu? Not sure if they are succinct, but the Apache arrow format encodes data in several ways that is compact in memory but also allows operations on these structures.
mindcrime 2y ago
These are the days I really love HN. Despite having been in this field for 30 some odd years, I'd never heard of "succinct data structures" until now. And had I not seen this post, maybe I never would have. Is that important? Well, maybe. As I started digging in and looking for libraries that implement some of this stuff, I found that a popular graph processing library (JGraphT) uses a succinct data structure library (Sux4J) for working with large graphs. And working with graphs is something I've been doing a deep dive into lately. So yeah, if these data structures represent something that has practical applications in graph processing, then maybe finding this is important. Certainly I'm glad I stumbled across this in either case; the topic strikes me as fascinating.
ks2048 2y ago
As an old-school signal processing person, "wavelet" and "FM" are throwing me for a loop. I can see FM is named for the authors. "wavelet" - I don't see at first glance what the name means or if it's related to the signal processing concept.
- eru 2y ago
  Yes, the 'wavelet tree' (and other wavelet thingies in succinct data structures) are rather unfortunately named. It ranks right up there with 'wavefunction collapse' in procedural generation.
nmca 2y ago
As an aside, an FM index can be used to efficiently turn an LLM into an actual stochastic parrot (one that emits only substrings of some dataset). This is more useful than it sounds because you can use it for quoting from large corpora.
Brystephor 2y ago
Maybe a silly question, but has anyone used these in production? Or used libraries in production which are built on these structures? Im imagining a meeting about some project design, and thinking about how it'd go if someone suggested using parentheses to represent nodes of a tree. I imagine it'd get written off quickly. Not because it wouldn't work, but because of the complexity and learning curve involved.
- pelario 2y ago
  The most emblematic application in real life is in bioinformatics. BWA and Bowtie are two widely used softwares built upon them.
- 392 2y ago
  Why are you having project design meetings about details as low level as the in-memory representation of data in a program?
vismit2000 2y ago
Marisa trie is a really cool and useful succinct data structure (also mentioned in High Performance Python book): https://github.com/pytries/marisa-trie https://github.com/pytries/marisa-trie
- zupa-hu 2y ago
  They publish a benchmark for anyone interested: https://marisa-trie.readthedocs.io/en/latest/benchmarks.html https://marisa-trie.readthedocs.io/en/latest/benchmarks.html Summary for storing a list of 3M Russian words: - ~60x less memory - ~5-10x slower compared to hashmap
itronitron 2y ago
That tree format (using parentheses) is also known as Newick format >> https://en.wikipedia.org/wiki/Newick_format https://en.wikipedia.org/wiki/Newick_format But you can also simply store the tree structure as a single array of ints (or longs) ... each node in the tree corresponds to a unique index position, and the value at that position is the index position of the node's parent (or it's own position if it's a top level node) ... good stuff.
Validark 2y ago
One famously fun paper is "The LCA problem revisited" https://ics.uci.edu/~eppstein/261/BenFar-LCA-00.pdf https://ics.uci.edu/~eppstein/261/BenFar-LCA-00.pdf For those who can't read, I recommend this talk about it: https://youtu.be/4NXJm2T9Yks https://youtu.be/4NXJm2T9Yks
denvaar 2y ago
I also find Succinct Data Structures fascinating. I own Navarro's text book, and it's one of my favorite books to take to the coffee shop and try to understand. I also have a copy of Jacobson's Thesis. Since information is rather scarce, here's my shameless plug for a related blog post I made, which includes a few links at the end to more resources https://denvaar.dev/posts/jacobsons_rank.html https://denvaar.dev/posts/jacobsons_rank.html
__tidu 2y ago
are succinct data structures good for "dynamic" applications? ie modifying the data often, last time i looked into this field it seems that all the popular structures were very static in nature and had costly updates
- denvaar 2y ago
  Maybe there are more modern, advanced data structures / techniques, but yes, my understanding is that this is a common trade off (having your data structure be more static, with offline updates).
neuroelectron 2y ago
I've always gotten the 'ick' from XML/json etc. This is like my personal anti-nausea pill.
anshul-s 2y ago
Fascinating topic!
adonovan 2y ago
Funny, I recently independently reinvented [1] the "balanced parentheses tree" and was very satisfied with its flexibility and speed: it seemed so simple and general I was surprised not to already know it by name. Now I do! [1] https://pkg.go.dev/golang.org/x/tools/internal/astutil/cursor https://pkg.go.dev/golang.org/x/tools/internal/astutil/curso...
zavec 2y ago
> Ignorance can bring you far. See also: the undergrad who found a breakthrough in hash tables recently and wasn't put off by a long-standing conjecture about what the bound on their performance was because he simply wasn't aware of it

588 points by pavel_lishin 2y ago

Wow, this is really fascinating. I guess it all comes down to how it's doing select and rank in constant time, which is probably some clever bit arithmetic. I'll have to look into how that works.

zellyn 2y ago
Some of it is moving or has moved down to the instruction sets: https://vaibhavsagar.com/blog/2019/09/08/popcount/ https://vaibhavsagar.com/blog/2019/09/08/popcount/
judofyr 2y ago
I can speak a bit about one of the approaches: "Practical Entropy-Compressed Rank/Select Dictionary" by Daisuke Okanohara and Kunihiko Sadakane. This presents two different variants: One for dense (i.e. more than 50% of the bits are set) and one for sparse. The dense implementation is basically based around partitioning them into "blocks" of a given size and then you can find the block by doing `block[idx / block_size]`. It then also groups each block into sub-blocks which helps you even further. All of these are additional data structures (very much like an index) which are stored next to the regular bitset. You use the blocks/sub-blocks to find roughly where in the bitset you are and then use a algorithm for finding the value in a given machine-word. The sparse implementation treats the bitset as an ordered list of numbers (e.g. 100001001 is interpreted as 0, 5, 8) and then it stores those numbers using Elias-Fano encoding. The higher bits of the Elias-Fano encoding happen to be dense and hence we can use the previous dense implementation on that higher bits and then combine it with the lower bits. I'm also aware of https://arxiv.org/abs/1706.00990 https://arxiv.org/abs/1706.00990 which is more about how to do this most efficiently at a machine-word level. "Engineering Compact Data Structures for Rank and Select Queries on Bit Vectors" is another quite recent paper which I haven't fully digested yet.

kccqzy 2y ago

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: http://youtu.be/uA0Z7_4J7u8 http://youtu.be/uA0Z7_4J7u8

eru 2y ago
Ed is great. He's not just a Haskeller, but has also done interesting work in the likes of C++ and 6502 assembly amongst others.
kreyenborgi 2y ago
His code on this seems to be https://hackage.haskell.org/package/structures https://hackage.haskell.org/package/structures There is also HaskellWorks packages like https://hackage.haskell.org/package/hw-xml https://hackage.haskell.org/package/hw-xml
- kccqzy 2y ago
  He also has https://github.com/ekmett/succinct-binary https://github.com/ekmett/succinct-binary
mrkeen 2y ago
My Haskell attempt at Wavelet Matrices: https://github.com/jahaynes/waveletto https://github.com/jahaynes/waveletto
johnpmayer 2y ago
Whoa - I was there! This was at a small elm-lang meetup; Prezi hosted this while Evan was working there. Thank you for sharing this link!

tux3 2y ago

I really like the article, but it would benefit from some numbers or complexity estimates to get some intuitive sense of what the cost is. Am I paying 30% overhead for this particular index or that wavelet matrix? Is it double the memory use? Or is it O(log N)? No idea! "doesn't use much more space" could mean a lot of different things!

judofyr 2y ago
"Succinct data structure" does have a very strict definition which probably answers some of your questions: https://en.wikipedia.org/wiki/Succinct_data_structure https://en.wikipedia.org/wiki/Succinct_data_structure. It's all about being close to the theoretical minimum. > Am I paying 30% overhead for this particular index or that wavelet matrix? Nope! That would not fit the definition. That would be a "compact data structure" according to this definition.
- jltsiren 2y ago
  You should be careful when using asymptotic bounds with more precision than about O(sqrt(n)). The bounds ignore constant factors, and the constant factors could be more significant than slowly growing non-constant factors for reasonable values of n. It's also very common in algorithm design that improving the asymptotic bounds and making the algorithm faster (or the data structure smaller) are orthogonal (or even opposite) goals. Real computers have complex performance characteristics and fixed word lengths, and it's rarely a good idea to implement a theoretical algorithm exactly as described. Succinct data structures often have a number of internal parameters. In a theoretical parameterization, those parameters may be described as being O(log n), O(log^2 n), or O(log log n). In a concrete implementation, it may be a good idea to use constant approximations for some nontrivial (such as 2x) performance gains. O(log n) could become 32 or 64, O(log^2 n) could become 1024 (or a power-of-2 multiple), and O(log log n) could become 4 or 8. And then, if you parameterize the succinct data structure with these constants, the space overhead becomes a constant fraction.
  - senderista 2y ago
    Succinct data structures require the extra space (above the information-theoretical minimum) to be an additive term of o(n) bits (little O, not big O). That just means that the extra space grows more slowly than n, as n approaches infinity, so their ratio (extra space)/n approaches 0 in the limit.

judofyr 2y ago

Succinct data structures are very fun! If anyone is interested, I've implemented some of this in Zig: https://github.com/judofyr/zini https://github.com/judofyr/zini. The main thing this implements is a minimal perfect hash function which uses less than 4 bits per element (and can respond to queries in ~50 ns). As a part of that I ended up implementing on of these indexes for constant-time select(n): https://github.com/judofyr/zini/blob/main/src/darray.zig https://github.com/judofyr/zini/blob/main/src/darray.zig. It feels kinda magic implementing these algorithms because everything becomes so tiny!

thomasmg 2y ago
For Java, C++, and Rust there is also https://sux.di.unimi.it/ https://sux.di.unimi.it/ maintained by Sebastiano Vigna, a professor from Italy. Together with his student (I also helped a bit), he wrote a paper about RecSplit, a minimal perfect hash function (MPHF) algorithm I have invented: https://arxiv.org/abs/1910.06416 https://arxiv.org/abs/1910.06416 - that algorithm uses around 1.56 bits per key. But it is quite slow. In January 2020 I presented the paper at a conference, that was right before the pandemic. The algorithm with the least memory usage (and much faster as well) is now Consensus-RecSplit: https://arxiv.org/abs/2502.05613 https://arxiv.org/abs/2502.05613 - it can do 1.44 bits per key, which is right at the theoretical minimum (meaning, there is no good way to shrink it further). At least a small part of my original invention is still used there, nice. The fastest current MPHF is probably PtrHash https://arxiv.org/abs/2502.15539 https://arxiv.org/abs/2502.15539 - both papers were published last month (February 2025) by the way.
- rurban 2y ago
  I'm working on making pthash faster and more practical. I can compile the data and code to C++, send efficiently store the keys also to be able to eliminate false positives. https://github.com/rurban/pthash https://github.com/rurban/pthash

mzs 2y ago

The word count seems artificially increased in the post. Here's a succinct explanation: https://www.eecs.tufts.edu/~aloupis/comp150/projects/SuccinctTreesinPractice.pdf https://www.eecs.tufts.edu/~aloupis/comp150/projects/Succinc...

pegasus 2y ago
I didn't think that at all. In fact I found it very readable and prefer it over the drier presentation you linked. To each its own, I guess, but there's really no need to infer ulterior motives.

abetusk 2y ago

My goto library for succinct data structures is SDSL-Lite [0]. [0] https://github.com/simongog/sdsl-lite https://github.com/simongog/sdsl-lite

qazxcvbnm 2y ago

Note that succinct data structures may not be faster than conventional structures if your dataset fits in memory http://www.cs.cmu.edu/~huanche1/slides/FST.pdf http://www.cs.cmu.edu/~huanche1/slides/FST.pdf . Of course, for large datasets where storage access times dominate, succinct data structures win all around. In any case, succinct trees are works of art (If I recall https://arxiv.org/pdf/1805.11255 https://arxiv.org/pdf/1805.11255 was a good exposition) (just look at how that RMQ works)!

yvdriess 2y ago
True, but it depends on what you mean with fitting in memory. Succinct datastructures are used in genomics (e.g. bwa, megahit exome sequencer) because N is so large that you're actually hitting asymptotic behavior. For memory latency it can by making your memory footprint fit in LLC or a single node; cross-node NUMA latencies are typically enough to absolutely tank performance. It can theoretically also help in massively parallel access situations where bandwidth becomes a limiting concern. Although, I intuit we would need near-memory hardware to perform the rank+select. Otherwise the latency of the multiple dependent accesses will kill your performance again, cfr previous point. With a lot of parallel accesses, bandwidth could also be an issue in conventional structures.
hinkley 2y ago
As an application grows the features start to interact. We tend to not be paying much attention to how the old code 'fits into memory' while we are writing new code that also has to fit into memory. Once you have an entire system written the benefits of having four interacting features that each fit into a third of memory may be bigger than you think. And I don't know how well Intel's hardware level profiling information reveals that but I know for sure that the profiling tools that ship with most commercially viable programming languages never do. They blame issues on whoever touched the system last, and if that is an epicycle or a metastable situation then the apparent guilty party may be a frame-up, while the real culprit goes unpunished. As an example: if your workflow has a step that eventually needs to use 40% of available memory to solve a problem, then GC will almost always trigger within that step of the process, rather than in the other 60% of memory being systematically wasted by heaps of inefficient code in the leadup to this step, because the top of the memory sawtooth will almost always occur within that part of the call graph. But because the 40% is your intrinsic complexity, people's brains shut off the moment a cost is attributed to unavoidable work, instead of the avoidable work that really caused the majority of the problem.

lostmsu 2y ago

Way better detailed explanation: https://stackoverflow.com/questions/72580828/what-is-a-succinct-rank-data-structure-how-does-it-work https://stackoverflow.com/questions/72580828/what-is-a-succi...

zero_shift 2y ago
That IS excellent - thank you
topspin 2y ago
Yes, that's great. This part: "Intuitively, a succinct data structure is one whose space usage equals the space needed to write out the data, plus something that grows more slowly than that. If you're familiar with little-o notation, a succinct data structure is one whose space usage is X + o(X), where X is the number of bits needed to write out the data itself." Brings to mind COBS encoding, which does this for streams bytes containing arbitrary length "packets" or similar.
adgjlsfhk1 2y ago
This is great! I love both how far you can push this and get meaningful improvements, and how it's totally overkill for anything we'll ever be able to implement on a physical computer. The hardware focused approach is to use popcnt for a base size of 512 (since cache architecture will make you fetch that much memory if you touch the original array anyway). We then can store 1 UInt16 prefix sum per 512 bits (n/32 bits overall), and if we have more than 2^16 bits in total, we can store UInt64 prefixes every 2^16 bits (n/1024 bits overall). Theoretically, this approach uses O(nlogn) bits as opposed to o(n) for the theoretical approach, but in practice, for <2^64 bools, the actual storage ens up being n/32+n/1024 which is pretty hard to beat. The theoretical approach gets it's wins from making extremely clever use of the difference between O(loglog(n)) and O(1), but unfortunately for the foreseeable future, logn < 64 and loglog(n) < 6, so all the subtlety gets swallowed up into the base case of a single popcnt instruction.
atiedebee 2y ago
This is great. A very understandable explanation, thanks for sharing!

cxie 2y ago

Just spent my morning diving into succinct data structures after seeing this. The memory efficiency is incredible - especially the balanced parentheses tree representing a full node tree in just 2 bits per node! I've been working on a project parsing large (10GB+) XML files for scientific data analysis, and our current approach burns through RAM like crazy. Has anyone here successfully implemented these structures in production systems? The wavelet matrix concept seems particularly promising for our text-heavy workloads. I'm curious if the constant-time operations actually hold up under real-world conditions or if there are hidden performance cliffs. This feels like one of those CS concepts that should be more widely known but somehow got overlooked by mainstream programming. Kind of like how bloom filters were obscure until suddenly every system was using them.

MortyWaves 2y ago
When I’ve dealt with huge files in .NET, the usual approach is to stream the file such that only some of it is in memory at once. This way you can process files hundreds of GBs. Of course, if you truly need them all in memory at once for some reason I genuinely can’t think of, then you’d need something else. Does your language have the concept of streaming files?
- crazygringo 2y ago
  If you're streaming something row-based like a CSV, or a zipped CSV, then that's usually easy. But when you get to hierarchical data structures like JSON/protobuf there very often simply isn't a streaming library available. There's a library function to decode the whole thing into an object in memory, and that's all. Nothing prevents streaming in theory, it's just far more complicated to write that library.
  - dilap 2y ago
    protobuf sure, but streaming libraries for json (and xml, as in the parent) are extremely common. not harder (maybe even easier) than non-streaming to write, tho more cumbersome to use, so something you'd reach for only if you specifically need it ('cuz of memory constraints) e.g. standard go json library https://pkg.go.dev/encoding/json#example-Decoder.Decode-Stream https://pkg.go.dev/encoding/json#example-Decoder.Decode-Stre...

MortyWaves 2y ago

> This is a field that seems to have emerged in computer science relatively recently; many of the important data structures were invented in the last 25 years. This is crazy!

sujayakar 2y ago

I really love this space: Navarro's book is an excellent survey. Erik Demaine has a few great lectures on succinct data structures too: L17 and L18 on https://courses.csail.mit.edu/6.851/spring12/lectures/ https://courses.csail.mit.edu/6.851/spring12/lectures/

yurivish 2y ago

I also emailed Gonzalo Navarro once to ask a question, and we had a great discussion and ended up writing a paper together about the answer. [1] Another paper of his that I really like combines a few elegant ideas into a simple implementation of bitvector rank/select: https://users.dcc.uchile.cl/~gnavarro/ps/sea12.1.pdf https://users.dcc.uchile.cl/~gnavarro/ps/sea12.1.pdf During this time I got really excited about succinct data structures and wrote a Rust library implementing many bitvector types and a wavelet matrix. [2] My interest came from a data visualization perspective -- I was curious if space-efficient data structures could fundamentally improve the interactive exploration of large datasets on the client side. Happy to chat about that if anyone's curious. [1] Paper: https://archive.yuri.is/pdfing/weighted_range_quantile_queries.pdf https://archive.yuri.is/pdfing/weighted_range_quantile_queri... though it's pretty hard to understand without some background context. I've been meaning to write a blog post explaining the core contribution, which is a simple tweak to one of Navarro's textbook data structures. [2] The rust version is here: https://github.com/yurivish/made-of-bits/tree/main/rust-playground/made-of-bits https://github.com/yurivish/made-of-bits/tree/main/rust-play... and an earlier pure-JS implementation is here: https://github.com/yurivish/made-of-bits/tree/main https://github.com/yurivish/made-of-bits/tree/main

sitkack 2y ago
Reading a Gonzalo Navarro paper is like going for walk, taking a shower and having a wonderful coffee. It literally sets the mind on fire. https://dblp.org/pid/n/GonzaloNavarro.html https://dblp.org/pid/n/GonzaloNavarro.html
- SoftTalker 2y ago
  Well not literally.
  - penguin_booze 2y ago
    Well, literally doesn't mean literally anymore--literally.
    - 2y ago

eqvinox 2y ago

There's a relative of this in making in-memory node representation efficient for large structs that have a bunch of rarely-used fields: chunk up memory in units (most reasonably 8 bytes/pointer size), allocate offsets for rarely-used fields in ascending order, and then use bitmasks to indicate which fields are present. (Note the bits correspond to units, not fields; a 16-byte field would use 2 adjacent bits in the bitmask.) The trick is that masking & popcount (both low-cycle CPU instructions in most modern CPUs¹) make this quite fast to access and thus suitable for in-memory representation. The intended use is when presence of optional fields is known at allocation time and doesn't change afterwards, i.e. some object is built up into a dynamically allocated buffer whose size is shrunk down by omitting fields. Changing which fields are present afterwards requires reallocating the thing, which tends to make the entire pattern pointless. ¹ the real annoyance here is that almost all x86_64 CPUs have POPCNT, except the absolute earliest ones, but if you build e.g. some package for a Linux distribution without any CPU optimization flags it'll use a library fallback popcount routine rather than the instruction :(

adgjlsfhk1 2y ago
thankfully a number of distros are starting to ship packages for x86v2 by default (basically everything Core 2 and newer) which fixes this finally.

bo1024 2y ago

With advanced CS topics, it often works to search for "<topic> lecture notes".

deleted 2y ago

[deleted]

dsffsad 2y ago

[flagged]

senderista 2y ago

I'm sure it's out of date in some areas by now, but I have Navarro's textbook[1] and it's a great survey. (The only criticism that comes to mind is that it weirdly shortchanges Elias-Fano encoding[2], which is hugely important in practice but relegated to just an offhand sentence or two in the book.) [1] https://www.cambridge.org/core/books/compact-data-structures/68A5983E6F1176181291E235D0B7EB44 https://www.cambridge.org/core/books/compact-data-structures... [2] https://vigna.di.unimi.it/ftp/papers/QuasiSuccinctIndices.pdf https://vigna.di.unimi.it/ftp/papers/QuasiSuccinctIndices.pd...

hawaiianSpork 2y ago

How do succinct data structures do with vector operations on cpu? Not sure if they are succinct, but the Apache arrow format encodes data in several ways that is compact in memory but also allows operations on these structures.

mindcrime 2y ago

These are the days I really love HN. Despite having been in this field for 30 some odd years, I'd never heard of "succinct data structures" until now. And had I not seen this post, maybe I never would have. Is that important? Well, maybe. As I started digging in and looking for libraries that implement some of this stuff, I found that a popular graph processing library (JGraphT) uses a succinct data structure library (Sux4J) for working with large graphs. And working with graphs is something I've been doing a deep dive into lately. So yeah, if these data structures represent something that has practical applications in graph processing, then maybe finding this is important. Certainly I'm glad I stumbled across this in either case; the topic strikes me as fascinating.

ks2048 2y ago

As an old-school signal processing person, "wavelet" and "FM" are throwing me for a loop. I can see FM is named for the authors. "wavelet" - I don't see at first glance what the name means or if it's related to the signal processing concept.

eru 2y ago
Yes, the 'wavelet tree' (and other wavelet thingies in succinct data structures) are rather unfortunately named. It ranks right up there with 'wavefunction collapse' in procedural generation.

nmca 2y ago

As an aside, an FM index can be used to efficiently turn an LLM into an actual stochastic parrot (one that emits only substrings of some dataset). This is more useful than it sounds because you can use it for quoting from large corpora.

Brystephor 2y ago

Maybe a silly question, but has anyone used these in production? Or used libraries in production which are built on these structures? Im imagining a meeting about some project design, and thinking about how it'd go if someone suggested using parentheses to represent nodes of a tree. I imagine it'd get written off quickly. Not because it wouldn't work, but because of the complexity and learning curve involved.

pelario 2y ago
The most emblematic application in real life is in bioinformatics. BWA and Bowtie are two widely used softwares built upon them.
392 2y ago
Why are you having project design meetings about details as low level as the in-memory representation of data in a program?

vismit2000 2y ago

Marisa trie is a really cool and useful succinct data structure (also mentioned in High Performance Python book): https://github.com/pytries/marisa-trie https://github.com/pytries/marisa-trie

zupa-hu 2y ago
They publish a benchmark for anyone interested: https://marisa-trie.readthedocs.io/en/latest/benchmarks.html https://marisa-trie.readthedocs.io/en/latest/benchmarks.html Summary for storing a list of 3M Russian words: - ~60x less memory - ~5-10x slower compared to hashmap

itronitron 2y ago

That tree format (using parentheses) is also known as Newick format >> https://en.wikipedia.org/wiki/Newick_format https://en.wikipedia.org/wiki/Newick_format But you can also simply store the tree structure as a single array of ints (or longs) ... each node in the tree corresponds to a unique index position, and the value at that position is the index position of the node's parent (or it's own position if it's a top level node) ... good stuff.

Validark 2y ago

One famously fun paper is "The LCA problem revisited" https://ics.uci.edu/~eppstein/261/BenFar-LCA-00.pdf https://ics.uci.edu/~eppstein/261/BenFar-LCA-00.pdf For those who can't read, I recommend this talk about it: https://youtu.be/4NXJm2T9Yks https://youtu.be/4NXJm2T9Yks

denvaar 2y ago

I also find Succinct Data Structures fascinating. I own Navarro's text book, and it's one of my favorite books to take to the coffee shop and try to understand. I also have a copy of Jacobson's Thesis. Since information is rather scarce, here's my shameless plug for a related blog post I made, which includes a few links at the end to more resources https://denvaar.dev/posts/jacobsons_rank.html https://denvaar.dev/posts/jacobsons_rank.html

__tidu 2y ago

are succinct data structures good for "dynamic" applications? ie modifying the data often, last time i looked into this field it seems that all the popular structures were very static in nature and had costly updates

denvaar 2y ago
Maybe there are more modern, advanced data structures / techniques, but yes, my understanding is that this is a common trade off (having your data structure be more static, with offline updates).

neuroelectron 2y ago

I've always gotten the 'ick' from XML/json etc. This is like my personal anti-nausea pill.

anshul-s 2y ago

Fascinating topic!

adonovan 2y ago

Funny, I recently independently reinvented [1] the "balanced parentheses tree" and was very satisfied with its flexibility and speed: it seemed so simple and general I was surprised not to already know it by name. Now I do! [1] https://pkg.go.dev/golang.org/x/tools/internal/astutil/cursor https://pkg.go.dev/golang.org/x/tools/internal/astutil/curso...

zavec 2y ago

> Ignorance can bring you far. See also: the undergrad who found a breakthrough in hash tables recently and wasn't put off by a long-standing conjecture about what the bound on their performance was because he simply wasn't aware of it