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

Great piece of software! but... 128 bit and beyond? #281

Open gitmko0 opened 4 years ago

gitmko0 commented 4 years ago

I would like to have 128 bit bitmap and i understand that only 32bit is compatible across all programming platforms so possible to give example / suggestions on the best practises to break down 128 bit into 32bit segment?

i'm using it as a detection of bit added / "filter" and not as a bitset /mapping function. it's great to use this as "unique filter" for the compression results it gives. 5 bil items at 1meg ram total. fantastic memory savings for 64bit.

does anyone have prior example / experience in using this as a filter as i've mentioned? thx for this software in advance.

natalie-o-perret commented 3 years ago

I'm thinking about a cheap workaround / solution, for example for the 128 bits (ie. 16 bytes) using two uint64 which might just do, just dunno how bad is the bottleneck of splitting a 128bits into two uint64 👩‍🚀, it's still adding a few extra cycles... I'd rather have a single data structure to achieve the same thing which would help to further compress while using less cycles.

guymolinari commented 3 weeks ago

The roaring libraries support Bit Slice Indices (BSI). This is included as as subpackage in the GoLang version of RoaringBitmap. It could and should be ported to other languages implementing Roaring Bitmap. A BSI can now support arbitrarily large values. 128 bit values such as hashes or UUID can be stored in a BSI.