Binary Histogrammed Intensity Patches for Efficient and Robust Matching

http://stackoverflow.com/questions/12122416/find-the-pair-of-bitstrings-with-the-largest-number-of-common-set-bits

As far as I can tell, Taylor & Drummond (2011) do not purport to give an O(n) algorithm for finding the pair of bitstrings in an array with the largest number of common set bits. They sketch an argument that a record of the best such pairs can be updated in O(n) after a new bitstring has been added to the array (and two old bitstrings removed).

Certainly the explanation of the algorithm on page 252 is not very clear, and I think their sketch argument that the record can be updated in O(n) is incomplete at best, so I can see why you are confused.

Anyway, here's my best attempt to explain Algorithm 1 from the paper.

Algorithm

The algorithm takes an array of bitstrings and constructs a lookup tree. A lookup tree is a binary forest (set of binary trees) whose leaves are the original bitstrings from the array, whose internal nodes are new bitstrings, and where if node A is a parent of node B, then A & B = A (that is, all the set bits in A are also set in B).

For example, if the input is this array of bitstrings:

then the output is the lookup tree:

The algorithm as described in the paper proceeds as follows:

1. Let R be the initial set of bitstrings (the root set).

2. For each bitstring f1 in R that has no partner in R, find and record its partner (the bitstring f2 inR − {f1} which has the largest number of set bits in common with f1) and record the number of bits they have in common.

3. If there is no pair of bitstrings in R with any common set bits, stop.

4. Let f1 and f2 be the pair of bitstrings in R with the largest number of common set bits.

5. Let p = f1 & f2 be the parent of f1 and f2.

6. Remove f1 and f2 from R; add p to R.

7. Go to step 2.

Analysis

Suppose that the array contains n bitstrings of fixed length. Then the algorithm as described is O(n³) because step 2 is O(n²), and there are O(n) iterations, because at each iteration we remove two bitstrings from R and add one.

The paper contains an argument that step 2 is Ω(n²) only on the first time around the loop, and on other iterations it is O(n) because we only have to find the partner of p "and any other bitstrings in R whose partner was one of the two selected for combination." However, this argument is not convincing to me: it is not clear that there are only O(1) other such bitstrings. (Maybe there's a better argument?)

We could bring the algorithm down to O(n²) by storing the number of common set bits between every pair of bitstrings. This requires O(n²) extra space.

Reference

• S. Taylor & T. Drummond (2011). "Binary Histogrammed Intensity Patches for Efficient and Robust Matching". Int. J. Comput. Vis. 94:241–265.