RoaringBitmap / RoaringBitmap/CRoaring

Compute cardinality of multiple unions or intersections at a time

Open
#298 4 comments 0 reactions 0 assignees View on GitHub

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

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.