Is there anything faster than BK-Tree?

Question

Python

I'm going to be storing a lot of data to search through it with "hamming distance".
Volume ~1,000,000. I decided to use a BK tree, but with the same million, the search turns out to be long, about 10-20 seconds.
The tree itself: dumpz.org/192335/ (Cython)
Maybe there are other, faster algorithms?

Answer 1

What order of distance are assumed in the query?
I would take an ordinary binary tree (branching by the value of some bit; each node indicates which bit to branch by). Then search(tree,d)=search(subtree with correct bit value,d)+search(subtree with incorrect bit value,d-1).

Answer 2

And for example, use specialized tools, such as sphinx?

Answer 3

v-tree. stackoverflow.com/questions/6389841/efficiently-find-binary-strings-with-low-hamming-distance-in-large-set