6

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.

  • 1
    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
  • 1
  • 1
    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
1

Just an intuition. I haven't gone through the details and may be embarrassingly mistaken.

As your vectors all have the same dimensionality d and their distance is defined as their hamming distance you can represent each vector as a point on a d-dimensional hyper cube. The path between two points will be the hamming distance of their coordinates.

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).

You could bring this constant factor down by applying a more efficient search algorithm. Eg: Efficiently find binary strings with low Hamming distance in large set

  • I'm looking for something practical. 2^10000 is not. – CodesInChaos Jan 16 '16 at 19:30
  • Check the link I edited in. You can do a more efficient search then BFS in a d-hypercube and nearest hamming neighbour is a fairly well researched topic that google can help you with. But that is just optimization. :P – mpkorstanje Jan 16 '16 at 19:49
  • Might also be worth checking if you can reduce d a bit. Depends on your exact problem though. – mpkorstanje Jan 16 '16 at 19:50
  • The problem with a more efficient search algorithm is that building a tree structure of 100 billion data vectors of length 10000 bits each doesn't fit into the memory. – Trilarion Mar 30 '16 at 7:21

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.