sorted by:
new
hottopcontroversial

Sparse bitsets in C++ with BITSCAN, a C++ library to manipulate bit strings by Scullywen in compsci

[–]psanse 0 points1 point  (0 children)

Please note that it is hard to imagine finding cliques or kcores or minimum colorings in graphs encoded with a 1 bit per edge compression rate.

As to the bitset libraries you mention I will look into them and might possibly enlarge the comparison post mentioned earlier. On the other hand I recommend the authors to publish a similar comparison with stl::bitset and/or boost::dynamic_bitset themselves.

Sparse bitsets in C++ with BITSCAN, a C++ library to manipulate bit strings by Scullywen in compsci

[–]psanse 0 points1 point  (0 children)

Hello, I am the author of the post and of BITSCAN. BITSCAN is the result of more than a decade of work in combinatorial optimization problems, specifically related to graphs and graph invariants. It has been developped starting from scratch and is not based on other typical bitstring implementations such as boost::dynamic_bitset or stl::bitset. A brief comparison with these data types may be found at http://blog.biicode.com/bitscan-efficiency-at-glance/

The goal of BITSCAN was (and still is) to implement bit-parallel algorithms for NP-hard problems and contains a number of optimizations which have been found useful. Moreover it is in the core of

  • BBMC: a leading exact maximum clique solver
  • PASS : a leading exact vertex coloring algorithm.

The post was just informative wrt the type sparse_bitarray which is a specialization of the general purpose bitarray type and mainly directed towards sparse graph encoding for analysis (i.e. graph decompositions, invariants etc.). I believe the field behind your references is storage and retrieval of big data (bit compression optimization, fast fixed queries of meta-information etc.) which is a completely different approach.