0
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ What do you mean by searching? What are the inputs? What's the operation you are trying to perform? Have you considered a hashtable, or standard algorithms for pattern matching in strings? $\endgroup$ – D.W.♦ Mar 1 '18 at 5:19
  • 1
    $\begingroup$ Could you sort it? How long are queries (the length of bitstring or several characters long)? $\endgroup$ – Evil Mar 1 '18 at 7:12
  • $\begingroup$ If your queries are prefixes, I agree that sorting the list is probably your best bet, then it's essentially binary search. You could also use a small table to speed up the start of the query (say, 256 entries to index the first byte of each array). $\endgroup$ – Pseudonym Mar 1 '18 at 7:18
  • 1
    $\begingroup$ Looking for exact matches doesn't look challenging: expecting enough queries to amortise preprocessing, identify a smallish set of easily accessible (addressable) units to tell all the items apart. For a query string, first check those to identify at most one candidate. Compare if necessary. $\endgroup$ – greybeard Mar 1 '18 at 11:31
  • $\begingroup$ Is the distribution uniform? $\endgroup$ – rus9384 Mar 1 '18 at 18:08
2
$\begingroup$

If you want to look for an exact match, use a hashtable. Choose a hash function that hashes a 10,000-bit string to a short hashcode. This approach will be simple and highly efficient: the running time will basically be the time to compute the hash of the 10,000-bit value that you are searching for.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ for now I'm doing exact match, but will need approx match soon i.e. argmin => argsort[1:top_n] $\endgroup$ – sten Mar 1 '18 at 21:02
  • $\begingroup$ 1000+ items read like needing 10+ well-selected bits to tell apart, a standard checksum over 10_000 bits strings is going to take its sweet time. $\endgroup$ – greybeard Mar 1 '18 at 21:07
  • $\begingroup$ @user1019129, please ask about approximate match separately, as that's a very different problem. You might research locality sensitive hashing first before asking. $\endgroup$ – D.W.♦ Mar 1 '18 at 21:10
  • $\begingroup$ @greybeard, hashing a 10,000-bit string should be very fast: I'd guess that you can hash 1.2KB of data in a few microseconds or less. I expect the time is probably dominated by memory bandwidth, i.e., the time to read in 1.2KB of data from RAM. $\endgroup$ – D.W.♦ Mar 1 '18 at 21:11
  • $\begingroup$ which hash algorithm is fast ? $\endgroup$ – sten Mar 25 '18 at 19:07
1
$\begingroup$

IMO, no sensible answer can be given without some knowledge on the distribution of the bits in those keys.

It might very well be that the first, say, 32 bits of the keys are completely discriminant and sorting or hasing on these will do the trick, with no need for full comparisons.

It could also be that the 600 first bits are always the same and this would defeat the above techniques.

There is not one-fits-all answer. Most probably, some form of compression followed by hashing would be welcome.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 50% of bits are 1, 50% are 0, always. $\endgroup$ – sten Mar 1 '18 at 17:26
  • $\begingroup$ @user1019129: this is not enough information. It only allows you to spare 1 bit per key. $\endgroup$ – Yves Daoust Mar 1 '18 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.