Re:EWAH – A compressed bitmap class in C++
by pelario on Wednesday January 04, 2017 @09:10AM
(#13318366)
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.
Re:EWAH – A compressed bitmap class in C++
by SloopJon on Wednesday January 04, 2017 @10:07AM
(#13318800)
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:
Re:EWAH – A compressed bitmap class in C++
by cbsmith on Wednesday January 04, 2017 @12:51PM
(#13320399)
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?
Re:EWAH – A compressed bitmap class in C++
by pelario on Thursday January 05, 2017 @04:55AM
(#13325972)
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.
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/
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
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?
So yes, the problems they are solving are different, even though the input data is the same.
(It also reminded me of the joke "Why does Edward Woodward have so many 'd's in his name?")