HICAMP Bitmaps, any inspiration

RoaringBitmap / roaring

Roaring bitmaps in Go (golang), used by InfluxDB, Bleve, DataDog

http://roaringbitmap.org/

Apache License 2.0

2.53k stars 232 forks source link

HICAMP Bitmaps, any inspiration #74

Open glycerine opened 7 years ago

glycerine commented 7 years ago

I ran across a paper about HICAMP Bitmaps from folks at Stanford, and wondered if there were any good ideas to be learned from it. http://web.stanford.edu/~hlitz/papers/a7-wang.pdf

glycerine commented 7 years ago

and another paper from 2016 on efficient updates. http://stratos.seas.harvard.edu/files/stratos/files/upbit-sigmod16.pdf

lemire commented 7 years ago

The question is somewhat open-ended, do you have anything specific in mind?

glycerine commented 7 years ago

Nothing specific.

Mostly just wanted to save the references for later reading and investigation--and to see if you had any critique. I was hoping they would have done comparisons with roaring, but I didn't see any.

lemire commented 7 years ago

There are various relevant papers... Out of the top of my head, here is one paper that benchmarks against Roaring...

Guzun, Gheorghi, and Guadalupe Canahuate. "Hybrid query optimization for hard-to-compress bit-vectors." The VLDB Journal 25.3 (2016): 339-354. http://user.engineering.uiowa.edu/~gguzun/papers/Hybrid_Query_optimization.pdf

Obviously, they conclude that their novel approach is better in some sense (defined in the paper).