Implement CNF operations

[Oppen]

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.

[Oppen]

On a related issue: while I care most about the C version here, implementing in roaring first as an experiment may be a better idea, since it makes it easier to compare performance between several versions. Specially between only performing multiple unions at a time, having intermediate bitmaps for each clause, and multiple intersections of the results.

It could be an interesting convenience function either way.

[lemire]

Of some relevance...

• Compressed bitmap indexes: beyond unions and intersections, Software: Practice and Experience 46 (2), 2016