RoaringBitmap / RoaringBitmap/CRoaring
Implement CNF operations
Nobody has claimed this yet.
- Dominant language
- C
- Stars
- 1.9k
- Forks
- 334
- Avg merge
- 2d 5h
- Merged PRs (30d)
- 17
Description
Conjunctive normal form (CNF) is a notation to represent some operations frequently used in a few niches. It can be seen as an extension of a feature we already support, which is union and intersection of many bitmaps at a time.
The idea is to come up with an API to pass a list (or, rather, array) of bitmaps for which to perform this efficiently and with minimal intermediate bitmap creation. A way to just compute cardinality in a memory efficient way sounds like a good idea as well.
If the proposal gains interest I may try to implement it, as it's useful for a project I work with.
An example of such an API would be:
typedef struct {
size_t size;
roaring_bitmap_t *bitmaps[];
} clause_t;
roaring_cnf(size_t n_conj, ...);
where n_conj tells us the number of intersections to perform, or the number of clauses we will be passing, and the varargs would be the clause_t typed clauses to intersect, each of which will have all of their contents unioned first.
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
No files, tests, or entry points are named. Start by reviewing the existing APIs for union and intersection of multiple bitmaps, then determine how the proposed clause array and CNF operation should fit them. Done should include a defined API for clause intersections with unioned contents and an efficient cardinality-only option.
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