Skip to content

BitMagic release v3.18.0

Compare
Choose a tag to compare
@tlk00 tlk00 released this 24 Dec 19:30

Release Notes

  1. This release was about optimizations of search algorithms in bit-transposed sparse strings
    (memory efficient dictionaries) see str_sparse_vector<> in bmstrsparsevec.h
    Current release implemented re-mapping of dictionary charactes based on their presense in the transposed plains.
    This trick is makes bit-matrix more succinct and facilitates faster search.

Optimizations resulted in 2x times improvement in both linear dictionary scan (unsorted column)
and binary search (sorted index). Some extra large cases (hundreds of millions of strings)
showed performance parity with STL map with up to 20x times (sic!) memory footprint advantage.

  1. Updated example for memory efficient dictionaries (it uses NASA NED extragalactic database)
    to provide new performance metrics and explain optimization methods.
    see xsample05.cpp
    Tech.Note: http://bitmagic.io/star-search.html