RoaringBitmap
Implement CNF operations
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.
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.
Of some relevance...
- Compressed bitmap indexes: beyond unions and intersections, Software: Practice and Experience 46 (2), 2016
