3 ms·

I can't see how an algorithm to lookup bit 'i' in a compressed bitmap of size 'n' can ever be constant time. No matter how the bitmap is compressed, the block

I can't see how an algorithm to lookup bit 'i' in a compressed bitmap of size 'n' can ever be constant time. No matter how the bitmap is compressed, the block storage space for 'b' bits of the bitmap cannot be constant (since it's impossible to always compress 'b' bits of arbitrary data into fewer than 'b' bits). So, to find bit 'i' in the compressed form, you are going to have to parse the compressed data. A naive approach would just linearly read through the compressed data, giving O(n). Alternatively, the data structure could contain indexes, pointing to various places in the bitmap. You could get the cost down to O(log n) by making your index contain pointers to a binary subdivision of the bitmap. But we're still not constant time. If you index every 'x' bits, the cost drops to O(x). To reach constant time, you would need to index every bit in the bitmap, which obviously cannot be done without creating a data structure bigger than the original bitmap. (Edit: fixed my misuse of linear/constant time!)

amallia 9y ago
I can't see how an algorithm to lookup bit 'i' in a compressed bitmap of size 'n' can ever be constant time. What you do is decoding a block in constant time, as the block size is constant and you need exactly block size iterations. Accessing the i-th bit cannot be done in constant time as I already mentioned unless you also store all the offsets (including all-zeros/ones). In that case, all you have to do is moving to the i/b block (where is is the position you want to access and b is the block size) by skipping (len(C)+len(O)) * i/b bits.
- joosters 9y ago
  But to decode a block of size 'b' takes O(b), i.e. larger blocks take longer to decode. You can pick whatever size block you like, but smaller blocks lead to less compression. It's just another form of indexing.
leni536 9y ago
I just found the following paper on "random access compression". They do claim constant time lookup. https://pdfs.semanticscholar.org/1511/11c0c6dec6104bbf70d67d5146503bc45830.pdf https://pdfs.semanticscholar.org/1511/11c0c6dec6104bbf70d67d... But yeah, I agree, O(log n) access time is easily achievable. I wonder what compressed filesystems use for seeking in large files.
- joosters 9y ago
  Interesting paper, but I'm not sure that I understand its claims sufficiently. In section 3.1, it seems to talk about a table that is effectively an index into the compressed data. So to find the position of codeword 'i' you can look it up in the table select(D,i) This could be practical if the codes being compressed were large, because the index has a chance of being smaller than the original data. The original article is discussing a bitmap, so the codewords are 1 bit long and there is no chance that an index of positions of individual bits could ever be smaller than the original data.
jobigoud 9y ago
> I can't see how an algorithm to lookup bit 'i' in a compressed bitmap of size 'n' can ever be constant time. Well for lossy compression we can, texture compression works this way. Every 4x4 block or whatever block size is compressed to a fixed known length like 128 bits. Then you can address any pixel in constant time.

amallia 9y ago

I can't see how an algorithm to lookup bit 'i' in a compressed bitmap of size 'n' can ever be constant time. What you do is decoding a block in constant time, as the block size is constant and you need exactly block size iterations. Accessing the i-th bit cannot be done in constant time as I already mentioned unless you also store all the offsets (including all-zeros/ones). In that case, all you have to do is moving to the i/b block (where is is the position you want to access and b is the block size) by skipping (len(C)+len(O)) * i/b bits.

joosters 9y ago
But to decode a block of size 'b' takes O(b), i.e. larger blocks take longer to decode. You can pick whatever size block you like, but smaller blocks lead to less compression. It's just another form of indexing.

leni536 9y ago

I just found the following paper on "random access compression". They do claim constant time lookup. https://pdfs.semanticscholar.org/1511/11c0c6dec6104bbf70d67d5146503bc45830.pdf https://pdfs.semanticscholar.org/1511/11c0c6dec6104bbf70d67d... But yeah, I agree, O(log n) access time is easily achievable. I wonder what compressed filesystems use for seeking in large files.

joosters 9y ago
Interesting paper, but I'm not sure that I understand its claims sufficiently. In section 3.1, it seems to talk about a table that is effectively an index into the compressed data. So to find the position of codeword 'i' you can look it up in the table select(D,i) This could be practical if the codes being compressed were large, because the index has a chance of being smaller than the original data. The original article is discussing a bitmap, so the codewords are 1 bit long and there is no chance that an index of positions of individual bits could ever be smaller than the original data.

jobigoud 9y ago

> I can't see how an algorithm to lookup bit 'i' in a compressed bitmap of size 'n' can ever be constant time. Well for lossy compression we can, texture compression works this way. Every 4x4 block or whatever block size is compressed to a fixed known length like 128 bits. Then you can address any pixel in constant time.