3 ms·

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 com

by tikhonj 13y ago

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 http://en.wikipedia.org/wiki/Succinct_data_structure [2]: http://stevehanov.ca/blog/index.php/?id=120 http://stevehanov.ca/blog/index.php/?id=120 [3]: http://alexbowe.com/rrr/ http://alexbowe.com/rrr/ and http://alexbowe.com/wavelet-trees/ http://alexbowe.com/wavelet-trees/

siganakis 13y ago
The problem with succinct data structures (and wavelet trees especially, but also rank-select dictionaries) is that while they have excellent performance characteristics when you look at them from a theoretical perspective, they tend to perform relatively poorly in practice. This seems to be due to how much memory is accessed when checking a single bit, and the difficulty in predicting branches. Of course it could just be that all my implementations have sucked, but even in playing around with libcds[1] didn't yield the kind of performance expected. If anyone knows of a fast implementation of Wavelet Trees, I'd love to see it. [1] https://github.com/fclaude/libcds https://github.com/fclaude/libcds
- matt4711 13y ago
  I'm one of the authors of a more complete c++11 succinct data structure library [1] which includes several engineered implementations of wavelet trees, compressed suffix arrays and compressed suffix trees. while you are right that random access is one of the main bottlenecks of succinct data structures, we found that sometimes SDS can be faster than their uncompressed counterparts [2] The github URL contains some additional resources such as tutorial slides and cheatsheets if you want to check it out. [1] https://github.com/simongog/sdsl-lite/ https://github.com/simongog/sdsl-lite/ [2] http://people.eng.unimelb.edu.au/sgog/optimized.pdf http://people.eng.unimelb.edu.au/sgog/optimized.pdf
deleted 13y ago
[deleted]
ot 13y ago
> Instead of parsing data, it might be better to store it as a blob of some sort with a binary index. This is exactly something I did for JSON, I call it semi-indexing: instead of parsing it into a tree of pointers, I create a succinct representation of the parsing tree, which is orders of magnitude smaller than the original JSON. Construction is much faster than parsing because there are basically no memory allocations, and access is not that much slower. About performance of succinct data structures in general, it is true that they have shown poor practical performance, but things are changing, both because we have better CPUs (while memory latency is pretty much unchanged), and better algorithms are being found. I did my Ph.D. on practical succinct data structures. We found that in some applications, the access times are competitive or faster than the non-succinct counterparts, while the space is much smaller. One example is tries: in my thesis [2] there are experiments for string dictionaries, and for query autocompletion (for example for search engines). Another area where (quasi-)succinct data structures are having some success is inverted indexes: recently proposed posting lists based on Elias-Fano [3] have been shown to outperform standard delta-encoded posting lists for queries with sparse intersection, and are used in Facebook's graph search [4]. Finally, the biggest success story of SDS has historically been molecular biology, because the size of the DNA sequences processed is so large that non-succinct data structures are impractical. Many sequence assemblers/aligners use variants of FM-indexes and Compressed Suffix Arrays, that are self-indexes based on the Burrows-Wheeler Transform and Wavelet Trees. [1] https://github.com/ot/semi_index https://github.com/ot/semi_index [2] http://www.di.unipi.it/~ottavian/files/phd_thesis.pdf http://www.di.unipi.it/~ottavian/files/phd_thesis.pdf [3] http://vigna.di.unimi.it/ftp/papers/QuasiSuccinctIndices.pdf http://vigna.di.unimi.it/ftp/papers/QuasiSuccinctIndices.pdf [4] http://www.vldb.org/pvldb/vol6/p1150-curtiss.pdf http://www.vldb.org/pvldb/vol6/p1150-curtiss.pdf
- ocfnash 13y ago
  IMHO, the FM-index deserves to be highlighted. That it is possible to store a string in a compressed format which can answer length-P substring queries in O(P) time (with good constant factors) is quite surprising at first sight. I recently wrote a few words about this here: http://ocfnash.wordpress.com/2014/01/03/dna-of-a-password-disaster/ http://ocfnash.wordpress.com/2014/01/03/dna-of-a-password-di... By the time I finished I decided the whole area was exciting and seems not at all as well known as it should be. I also think there are plenty of related, as-yet-undiscovered ideas, waiting for somebody to find them!

by tikhonj 13y ago

siganakis 13y ago

The problem with succinct data structures (and wavelet trees especially, but also rank-select dictionaries) is that while they have excellent performance characteristics when you look at them from a theoretical perspective, they tend to perform relatively poorly in practice. This seems to be due to how much memory is accessed when checking a single bit, and the difficulty in predicting branches. Of course it could just be that all my implementations have sucked, but even in playing around with libcds[1] didn't yield the kind of performance expected. If anyone knows of a fast implementation of Wavelet Trees, I'd love to see it. [1] https://github.com/fclaude/libcds https://github.com/fclaude/libcds

matt4711 13y ago
I'm one of the authors of a more complete c++11 succinct data structure library [1] which includes several engineered implementations of wavelet trees, compressed suffix arrays and compressed suffix trees. while you are right that random access is one of the main bottlenecks of succinct data structures, we found that sometimes SDS can be faster than their uncompressed counterparts [2] The github URL contains some additional resources such as tutorial slides and cheatsheets if you want to check it out. [1] https://github.com/simongog/sdsl-lite/ https://github.com/simongog/sdsl-lite/ [2] http://people.eng.unimelb.edu.au/sgog/optimized.pdf http://people.eng.unimelb.edu.au/sgog/optimized.pdf

deleted 13y ago

[deleted]

ot 13y ago

> Instead of parsing data, it might be better to store it as a blob of some sort with a binary index. This is exactly something I did for JSON, I call it semi-indexing: instead of parsing it into a tree of pointers, I create a succinct representation of the parsing tree, which is orders of magnitude smaller than the original JSON. Construction is much faster than parsing because there are basically no memory allocations, and access is not that much slower. About performance of succinct data structures in general, it is true that they have shown poor practical performance, but things are changing, both because we have better CPUs (while memory latency is pretty much unchanged), and better algorithms are being found. I did my Ph.D. on practical succinct data structures. We found that in some applications, the access times are competitive or faster than the non-succinct counterparts, while the space is much smaller. One example is tries: in my thesis [2] there are experiments for string dictionaries, and for query autocompletion (for example for search engines). Another area where (quasi-)succinct data structures are having some success is inverted indexes: recently proposed posting lists based on Elias-Fano [3] have been shown to outperform standard delta-encoded posting lists for queries with sparse intersection, and are used in Facebook's graph search [4]. Finally, the biggest success story of SDS has historically been molecular biology, because the size of the DNA sequences processed is so large that non-succinct data structures are impractical. Many sequence assemblers/aligners use variants of FM-indexes and Compressed Suffix Arrays, that are self-indexes based on the Burrows-Wheeler Transform and Wavelet Trees. [1] https://github.com/ot/semi_index https://github.com/ot/semi_index [2] http://www.di.unipi.it/~ottavian/files/phd_thesis.pdf http://www.di.unipi.it/~ottavian/files/phd_thesis.pdf [3] http://vigna.di.unimi.it/ftp/papers/QuasiSuccinctIndices.pdf http://vigna.di.unimi.it/ftp/papers/QuasiSuccinctIndices.pdf [4] http://www.vldb.org/pvldb/vol6/p1150-curtiss.pdf http://www.vldb.org/pvldb/vol6/p1150-curtiss.pdf

ocfnash 13y ago
IMHO, the FM-index deserves to be highlighted. That it is possible to store a string in a compressed format which can answer length-P substring queries in O(P) time (with good constant factors) is quite surprising at first sight. I recently wrote a few words about this here: http://ocfnash.wordpress.com/2014/01/03/dna-of-a-password-disaster/ http://ocfnash.wordpress.com/2014/01/03/dna-of-a-password-di... By the time I finished I decided the whole area was exciting and seems not at all as well known as it should be. I also think there are plenty of related, as-yet-undiscovered ideas, waiting for somebody to find them!