Compressing bitmaps jointly?

[Sean McAllister]

Hey all, I want to look at using roaring bitmaps to store an index for a database.  _but_ I want to subdivide it spatially with a quad tree.  E.g. at the top level I might have a bitmap for the entire database mapping which elements are points, then I'd subdivide that top level into four children and compute bitmaps for each of them.

Clearly, the child bitmaps will be subsets of the parent bitmap, so when I go to store this thing most of the data will be the same and I'd dearly like to deduplicate it as much as possible.

So, the question is: Is it possible to use CRoaring et al to jointly compress multiple bitmaps and deduplicate shared blocks?  If anyone's done it I'd enjoy seeing an example.

Sean

[Daniel Lemire]

You are probably looking for a spatial BSI (bit-slice index). CRoaring does not (yet) have BSI, but both the Go and Java versions do. Neither version supports spatial BSI at this time.

Al-Badarneh, A. F. (2000). The spatial bit-sliced: an index structure for spatial databases. Wayne State University.

Krčál, L., Ho, S. S., & Holub, J. (2021). Hierarchical Bitmap Indexing for Range and Membership Queries on Multidimensional Arrays. arXiv preprint arXiv:2108.13735.

Rinfret, D., O'Neil, P., & O'Neil, E. (2001, May). Bit-sliced index arithmetic. In Proceedings of the 2001 ACM SIGMOD international conference on Management of data (pp. 47-57).

[Sean McAllister]

That sounds exactly like what I want.   I plan to do the spatial part myself using S2 (http://s2geometry.io/) but I'll look at those papers, thank you!

--
You received this message because you are subscribed to a topic in the Google Groups "Roaring Bitmaps" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/roaring-bitmaps/all2TiGjGvc/unsubscribe.
To unsubscribe from this group and all its topics, send an email to roaring-bitma...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/roaring-bitmaps/79608410-f24f-410f-aaac-2c63c2c0278en%40googlegroups.com.