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.

Improve this question
7
  • 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, 2016 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, 2016 at 15:24
  • @soandos As far as I can tell, trees only work for low dimensional problems.
    – CodesInChaos
    Jan 18, 2016 at 15:34
  • 1
    Locality-sensitive hashing ... Bit sampling for Hamming distance (en.wikipedia.org)
    – rwong
    Feb 16, 2016 at 10:16
  • 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, 2016 at 11:26

1 Answer 1

Reset to default
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

Improve this answer
4
  • I'm looking for something practical. 2^10000 is not.
    – CodesInChaos
    Jan 16, 2016 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
    – M.P. Korstanje
    Jan 16, 2016 at 19:49
  • Might also be worth checking if you can reduce d a bit. Depends on your exact problem though.
    – M.P. Korstanje
    Jan 16, 2016 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, 2016 at 7:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.