3 ms·

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 comp

by pelario 10y ago

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 https://github.com/simongog/sdsl-lite 2: http://alexbowe.com/rrr/ http://alexbowe.com/rrr/

SloopJon 10y ago
I looked into succinct data structures last year in the context of encoding a list of offsets. Alex's blog was one of the launching points, and I also came across Daniel's FastPFor repository. There are some really interesting approaches to compressed data structures that preserve fast random access. This comparison of less exotic encodings was a good read too: http://www.stepanovpapers.com/CIKM_2011.pdf http://www.stepanovpapers.com/CIKM_2011.pdf
cbsmith 10y ago
a) The EWAH library is reference implementation provided to support the paper. SDSL is a library that collects together a bunch of such papers. It isn't odd that there is no mention of SDSL. It is a bit odd that SDSL makes no mention of any of Daniel's work. b) I haven't used SDSL much or RRR bit vectors, but IIRC it's more designed for maximum compactness as well as quick popcount & select type operations. You can do that with EWAH, but a lot of the power of EWAH and its ilk (BBC, WAH, etc.) is with set operators like AND, OR & ANDNOT. Does SDSL have the same kind of optimizations?
- pelario 10y ago
  The bitmaps in SDSL are indexed to support rank and select queries: How many 1's are from the beginning until position i, and conversely, which is the position of the j-th 1) [it uses popcount but is beyond it] So yes, the problems they are solving are different, even though the input data is the same.

by pelario 10y ago

SloopJon 10y ago

I looked into succinct data structures last year in the context of encoding a list of offsets. Alex's blog was one of the launching points, and I also came across Daniel's FastPFor repository. There are some really interesting approaches to compressed data structures that preserve fast random access. This comparison of less exotic encodings was a good read too: http://www.stepanovpapers.com/CIKM_2011.pdf http://www.stepanovpapers.com/CIKM_2011.pdf

cbsmith 10y ago

a) The EWAH library is reference implementation provided to support the paper. SDSL is a library that collects together a bunch of such papers. It isn't odd that there is no mention of SDSL. It is a bit odd that SDSL makes no mention of any of Daniel's work. b) I haven't used SDSL much or RRR bit vectors, but IIRC it's more designed for maximum compactness as well as quick popcount & select type operations. You can do that with EWAH, but a lot of the power of EWAH and its ilk (BBC, WAH, etc.) is with set operators like AND, OR & ANDNOT. Does SDSL have the same kind of optimizations?

pelario 10y ago
The bitmaps in SDSL are indexed to support rank and select queries: How many 1's are from the beginning until position i, and conversely, which is the position of the j-th 1) [it uses popcount but is beyond it] So yes, the problems they are solving are different, even though the input data is the same.