I am implementing an approximate similarity search using multi-index hashing. I have a set (T) of millions of strings (of same length)  and I have a query string(P) (or set of strings) that needs to find similar strings former set. My implementation is the following (assuming length is 64 and similarity is defined as hamming distance less than 15)Divide each string in T into 16 parts and store each part in a hash table  where key is the hash value and value is a vector  containing the indices of strings. Ex < 198675, {2, 7, 8, 456}> [I  have 16 such hash tables for each portion of the string]For a query string P, divide it into 16 parts and for each part collect the set of indices(if present) from each hash table and  then take the union of all. That becomes a small search space.Calculate the hamming distance between the query and the resulting set of strings.I have implemented in C++ and it's working fine, but I am still wondering how could I make it more faster. Any suggestions would be appreciated.
Approximate Similarity Search
strings;hashing;searching
Your method is reasonable.  There are other possibilities as well.Randomized algorithm: locality-sensitive hashingHere is a randomized algorithm that finds all matches with high probability (probability $1-\epsilon$ where $\epsilon$ is exponentially small, but not zero).  It will probably be more efficient.Build 100 tables.  Each table is constructed as follows: Randomly pick a subset of 8 positions (out of the 64 possible positions).  Now a string is hashed by keeping only the 8 characters from those 8 positions, and the string is stored in the hashtable keyed on that hash.  For instance, if the positions associated with a particular table are $i_1,i_2,\dots,i_8$, then the string $S$ is hashed by hashing $S[i_1],S[i_2],\dots,S[i_8]$ and using that hash value as the key to store $S$ in the table.  Each table has a different and randomly generated subset of positions.Store each of the millions strings in all 100 tables.  When you get a query string $Q$, look it up in each of the 100 tables to find all possible matches, take the union of those possible matches, and calculate the Hamming distance between $Q$ and each possible match.This is very similar to your method, but each part is longer (8 characters instead of 4 characters), so there will probably be many fewer false matches from the hashtable.There is no guarantee that this approach will find all valid matches, but most likely it will.  The probability that a valid match is not found is$$(1-(49/64)^8)^{100} \approx 0.0000035,$$so missing a match is unlikely.  You can tune the probability of a missed match by adjusting the number of tables, and you can adjust the parameters ($8,100$) to find the setting that gives you the best possible performance.This is effectively a form of locality-sensitive hashing (LSH).  There may be other schemes worth investigating.  You could also look at MinHash.TrieAnother approach is to store the dictionary of millions of strings in a trie data structure.  Given a query string $Q$, you can start traversing the trie, doing a recursive breadth-first search  to explore all paths that are at distance at most 15 from $Q$.  For many paths, you'll be able to immediately terminate the search.