RoaringBitmap / RoaringBitmap/CRoaring
Compute cardinality of multiple unions or intersections at a time
Nobody has claimed this yet.
- Dominant language
- C
- Stars
- 1.9k
- Forks
- 334
- Avg merge
- 2d 5h
- Merged PRs (30d)
- 17
Description
I'm planning on implementing a feature to do this but I'd like early feedback on the design.
The idea is to use a heap such as in the roaring_bitmap_or_many_heap implementation to get pointers to all the containers sorted by key. This way I can compute unions of all containers of a given key in a single bitset container (since the contents will be discarded once I get its cardinality), so the memory use would be about 8k + sizeof(auxilliary_struct)*N, where N is the number of containers in the bitmaps passed to my function, and auxilliary_struct would be some structure with enough data to keep progress (most likely a pointer to a container, but I'll know better when I start coding). Another option is for auxiliary_struct to keep the lowest unprocessed key for sorting and the pointer to the bitmap, so our heap doesn't need to fit all the containers at once but keeps re-adding elements to the queue if they weren't exhausted.
Time complexity should be more or less the same as with an intermediate bitmap for union, but for bigger bitmaps it should save some space.
The same can be done for intersection.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by reviewing the existing roaring_bitmap_or_many_heap implementation mentioned in the issue and compare its container traversal with the proposed multi-union and multi-intersection cardinality operations. Done should be a settled API and design for computing these cardinalities without retaining an intermediate bitmap, with the memory and time trade-offs understood.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- c
- Domain
- data
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100