# Finding similar high dimensional vectors

I have two lists (sizes `m` and `n`) containing high dimensional bit-vectors. All vectors have the same number of dimensions and use Hamming distance as measure if distance.

For each element in the first list I want to find the closest elements in the second list. Such a closest element may differ by several thousand bits from the element I'm searching for.

The naive approach would be computing the hamming distance for each pair of vectors, but that has runtime O(m*n) making it infeasible. So I'm looking for an algorithm that's significantly faster.

Lets say I have d=10000, m=1 billion and n=100 billion and I want the algorithm to terminate in a couple of CPU days.

The elements in the first list are created by taking a random element from the second list and flipping each bit with the same probability p < 0.5. I want to support values of p that are as close as possible to 0.5. I'm fine with probabilistic algorithms that find matches with high probability.

• A few off the bat questions / things to consider: 1) Is the relationship between two vectors entirely random? I mean, if they're close in one part, does it predict in any way their distance in another part? 2) Just to be sure, do you need absolute best match, or good match with some threshold is feasible? 3) Is it an option to send this to a GPU? Looks to me like you could benefit from massive parallelism, if speed is really an issue. 4) Do you have access to a CPU which has a bit count instruction (popcnt)? Using xor+popcnt on a large numeric type would speed things up I guess. – Joanis Jan 17 '16 at 4:18
• No idea what the RAM requirements would be, but could you build an R tree from your vectors? That should easily give you the information you would want. – soandos Jan 18 '16 at 15:24
• @soandos As far as I can tell, trees only work for low dimensional problems. – CodesInChaos Jan 18 '16 at 15:34
• How can you even store that amount of data? No matter how I calculate it, that at lease few dozens of terrabytes. – Euphoric Feb 16 '16 at 11:26

All points in n are marked. This takes `O(n)` time. Then for each point in m you execute a breadth first search for any marked node. This will take `O(m * (|V|+|E|))` time. Altogether `O(n + m * (|V|+|E|))` time. However as the number of vertices and edges are derived from d and d is a constant we are left with `O(n + m)`.