I've been thinking for some time but can't figure a way out. I have big bitarray i.e. 1000+ items of 10_000 bits strings, I'm searching them now linearly. (currently it is stored in one chunk of memory).
I'm looking for some better algorithm for searching/matching !
Do you have any idea ?
bitarray looks like this :
0) 1011.... <= 10_000 bits
1) 1100....
2) 0010....
3) ........
...........
now find index of "1100...." :
find(1100....) = 1
50% of bits are 1, 50% are 0, always.
I could probably sort it by hamming distance, but will be time consuming! (and array grows dynamically, so i have to re-sort) and the search will still be slower if I search one by one (probably because python overhead). Currently the search is binary op+, but as you expect doesn't scale well i.e.
#duplicate the search item to the size of array
si_dup = search_item * array_size
dist's = (array ^ si_dup).count_by_row(1s)
top_idx = dist's.argmin()
The bad thing is that this is parallelize-able (I can process it in chunks), but python is not multi-threaded :(. Also can seem to find a DB which handle large binary-strings, that will be a way out for large sets, I think!
thanks, "locality sensitive hashing" was the key, I researched it a bit and that seem will be the solution for large bitarrays (LSH via BitSampling). For small ones the current approach I think will be faster.