RoaringBitmap / RoaringBitmap/CRoaring

Implement CNF operations

Open
#308 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

enhancement
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

  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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.