Question about decoding speed

[vteromero]

Question about decoding speed

[vteromero]

Thank you @mavam!

I think it's a bit of both.

I haven't spent much time in trying to optimise the library in terms of performance and I believe that there is room for improvement. But at this stage, I'd rather get feedback and think about next steps.

In theory, the decoding algorithm runs in O(nW / 2) in best case and O(nW) in worst case, where n is the size of the input and W corresponds to the word size (8, 16, 32 or 64). That's true if we consider that calculating the number of bits of a value and reading bits from a bit stream are both constant-ish.

[mavam]

Good to know that you haven't spent a lot of effort into tuning. Linear performance in the input is definitely something we can work with conceptually.

For us, we'd be interested in integrating VTEnc as an alternative representation to EWAH bitmaps. The binary operations we perform on sorted integer lists are intersection, union, and negation/complement. The unary operations are mostly rank and select queries.

(Our basic abstrction might serve as a reference for the operations to be performed, but the name will change to something more general in the future, i.e., it will be more than just a bitmap-based abstraction.)

[vteromero]

I'm afraid that VTEnc doesn't support bitmap operations, it's a pure compression algorithm for sorted lists of integers.

[mavam]

Understood. I didn't mean to diverge the discussion, my comment was a bit more general: I consider a bitmap an isomorphic representing of a sorted list of integers where the indices of 1-bits are the values. So for example, intersecting a bitmap with a list of integers works just fine when abstracting a way the implementation details.