Algebra or Sets and Logical operations

Algebra of Sets is a relatively simple thing and can be fully implemented on just a few operations: set assignment(s), AND, OR, NOT. Implementation of various logical compute patterns in BitMagic produced a reach set of APIs and requires a tutorial to explain use cases.

Logical API groups and general usage patterns

1. Basic 2-operand logical operations on vectors (OR, AND, MINUS, etc). VectorA = VectorA OPERATION VectorB.
2. 3-operand logical operations on vectors. Target = ArgA OPERATION ArgB. Source operands are immutable in this case. Operations of this type can also fuse an optimization/compression step
3. Operations between vector and list of integers (sorted or unsorted set). Mutable, changes the target vector. It is very often used for loading content from an STL container, C-arrays. Typical use case here is index construction. It can be also used for cases, when keeping a whole bit-vector is ineffcient (small integer lists), but final result needs a logical operation.
4. Operations between vector and serialized BLOB. Indexes and sets do not sit im memory all the time, BitMagic containers (all not just bvector<>) can be be saved and restored as a BLOB. Deserialization can be fused with a logical operation (memory efficiency, minimizes memory copying). Logical operations with a BLOB are based on operation codes, which makes it easy to build an SQL-like query language interpetor.
5. Fast aggregator (bm::aggregator<>). Aggregator is used when we need to run an operation on groups of vectors. Aggregator uses optimization techniques to prune the search space and minimize memory access. The best usage pattern here when we can have many (say more than 5) vectors or groups of vectors. Aggregator allocates its own temporary memory so the best usage model here is to create it once (per thread) and reuse it to run various operations on bit-vector groups. BitMagic library uses aggregator for searches in bit-transposed sparse matrices.

   Aggregator has an option to perform on-the-fly optimization(compression) of the result vector, which is faster than a separate call to bvector<>::optimize().

Why so many different ways to do the same?

Short answer: performance and convinience. Different use cases need different patterns and API implementations.

Logical bit-wise operations rely on very basic and very fast hardware. There should be a compelling reason to have different APIs to do over-engineering like this?

Top performance is needed for a few reasons.

• Full scale search systems often set a time budget, which is human factor. How long user wants to wait? Very often results need to be ready within hundreds of milliseconds. Fast system can evaluate multiple search hypothesis and combinations of logical formulas "cats AND dogs", "cats OR dogs", "cats BUT NOT dogs", etc. To see what is more relevant to the query. Fast speed can be translated into better, more relevant results. Smarter system.
• Better ranking. Again, this is about search budget. Logical search phase on inverted indexes would often require result set ranking to bring the most relevant data on top. Without touching details of ranking algorithms, this pahse can be expensive (yet important) so it is important to finish the preliminary search space reduction faster. Ranking algorithms itself may use logical operations and binary classifiers to understand how search results cluster, fast loical operations are helpful here as well.
• In the absense of fast implementation search systems often need to truncate results, say, we find only first 100. It is fine in many cases, but it is a lot more convenient if search is capable of bringing the whole results set (as a compressed vector) so that later stage (ranking or something else) can pick ten best out of thousands, not one hundred or work on the whole complete result set if it needs to. For example, later stage may be not ranking but big data visualization capable of its own data reduction and display techniques to show a meaningful representation of search result set. Search set truncation makes such scenarious hard.

Quick example

This example (part of BitMagic performance benchmark) a difference in 2-operand and 3-operand set union (logical OR). Example shows how to do functionally equivalent operations but 3-operand logic works faster in this case, because it fuses multiple operations (copy, OR and optimize). Variety of logial operations gives the right tool for every use case.

#include "bm.h"
void OrTest()
{
    bm::bvector<> bv1, bv2;
    bm::bvector<> bvt1, bvt2;
    generate_bvector(bv1, 40000000, false);
    generate_bvector(bv2, 40000000, false);

    {
        TimeTaker tt("OR-optimize (2 operand) bvector test", REPEATS*4);
        for (unsigned i = 0; i < REPEATS*4; ++i)
        {
            bvt1 = bv1;
            bvt1 |= bv2;
            bvt1.optimize();
        }
    }

    {
        TimeTaker tt("OR-optimize (3 operand) bvector test", REPEATS*4);
        for (unsigned i = 0; i < REPEATS*4; ++i)
        {
            bvt2.bit_or(bv1, bv2, bvect::opt_compress);
        }
    }
}

Subset, supersets, cardinality and dimentionality of bit-vector based sets

Before going farther with API description lets discuss a few assumptions of BitMagic library. By default bvector<> does not require you to specify its size. The sparse vector usage model is based on automatic memory management (somewhat similar to STL map<>) where you just load your set and container takes care of the memory management.

Set cardinality on bitsets is defined as population count bvector<>::count().

It is assumed that all our sets are really sub-sets of a super set U with a maximum cardinality of 2^31-1 (32-bit space). If you invert an empty bit-set - you get a superset (all bits are set to 1).

In some cases you don't need or want to operate on a full superset power. bvector<> has a resize() function, which you can use to set the maximum size (not cardinality). Set size defines the maximum element.

It should be noted, that explicitly setting the size does not save you much memory it is not a resource management thing. In terms of algebra of sets you are defining maximum possible cardinality or just size of your superset.

Operations on sets of reduced cardinality

Invert will only flip the bits in the closed range of [0..size()-1]. Other operations (OR, AND) will take size into account and automatically resize the target to the maximum of all arguments (maximum superset).

A question to ask here is why AND has to extend the superset, while it is clear (and even axiomatic) that sub-set intersection of small set with a bigger sub-set is always empty? Automatic extencion was done to make a clear rule of managing super-sets: the largest super-set defines the dimentionality, regardless of the operation we use on it.

Quick recap

1. bvector<>::size() returns dimentionality (default is full 32-bit space)
2. bvector<>::count() returns cardinality (actual number of elements in the set)
3. Logical operations change the size (dimentionality) to be maximum of operands even if cardinality gets reduced
4. Logical operations change the cardinality based on logical truth tables of a particular operation

Set Union (OR)

Logical disjunction (OR) truth table

bm::bvector<>   bv_A { 1, 2, 3 };
bm::bvector<>   bv_B { 1, 2, 4 };
bv_A.bit_or(bv_B); // 1, 2, 3, 4

bm::bvector<>   bv_A { 1, 2, 3 };
bm::bvector<>   bv_B { 1, 2, 4 };
bm::bvector<>   bv_T;
bv_T.bit_or(bv_A, bv_B, bm::bvector<>::opt_compress); // 1, 2, 3, 4

bm::bvector<>   bv_A { 1, 2, 3 };
bm::bvector<>   bv_B { 1, 2, 4 };
bv_A.combine_operation(bv_B, bm::BM_OR);

bm::bvector<>   bv_A { 1, 2, 3 };
vector blob;
    {
        bm::bvector<>   bv_B { 1, 2, 4 };
        make_BLOB(blob, bv_B);
    }
bm::operation_deserializer<bm::bvector<> > od;
od.deserialize(bv_A, blob.data(), bm::set_OR);

bm::bvector<>    bv_A { 1, 2, 3 };
vector vect_B { 1, 2, 4 };
bm::combine_or(bv_A, vect_B.begin(), vect_B.end());

bm::bvector<>     bv_A { 1, 2, 3 };
vector  vect_B { 1, 2, 4 };

const unsigned* arr = &vect_B[0];
bv_A.set(arr, unsigned(vect_B.size()), bm::BM_SORTED); // sorted - fastest

bm::bvector<>    bv_T; // target vector

bm::bvector<>    bv_A { 1, 2 };
bm::bvector<>    bv_B { 2, 3 };
bm::bvector<>    bv_C { 3, 4 };

bm::aggregator<bm::bvector<> > agg;
agg.set_optimization(); // perform on-the-fly optimization of result

// attach vectors to group 0 for OR operation
agg.add(&bv_A);
agg.add(&bv_B);
agg.add(&bv_C);

agg.combine_or(bv_T); // 1, 2, 3, 4

bm::bvector<>   bv_A { 1, 2, 3 };
bm::bvector<>   bv_B { 1, 2, 4 };
bv_A.merge(bv_B); // 1, 2, 3, 4, content of bv_B is not guaranteed to be preserved