Hacker News Reader

Comment by siganakis | Hacker News Reader

Bitmaps are very good at "Seek" operations (where I try to find a value), but poor at "Access" (where I try to find the value at an index). This is because "Access" requires that I check all the bitmaps to see which one has the set value.

Also the "Word Aligned Hybrid" method of RLE compression is patented. http://www.freepatentsonline.com/6831575.html

View on HN

It's true that simple Access is O(N) as is, but you aren't limited to using the same index for forward and inverse lookups. It's even possible that you could use compressed bitmaps for both in less space than a fixed array. Single or multilevel indexing into the bitmap can also speed things up. The "Inverted Index" paper linked above has an interesting take.

Patents are thorny, and it's generally not recommended that developers read them: willful infringement equals treble damages, caveat lector. The license may make better reading <http://crd-legacy.lbl.gov/~kewu/fastbit/src/license.txt>. Search for "software patents pose a constant threat to the existence of any free program".

If it remains a concern, and realizing that any other scheme you choose is also likely to be encumbered, you may be able to substitute a different compression such as PForDelta. The important part is cache awareness and branch prediction -- this is likely where your wavelet code is falling short.

Good luck!

Reply on news.ycombinator.com