Fast searching through bitarray?
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.