Hamming distance calculation on a large dataset

This article will focus on the HEngine algorithm and the implementation of the solution to the problem of calculating Hamming distance on large amounts of data.

Introduction

Hamming distance is the number of different positions for lines with the same length. For example, HD ( 1 0 0 , 0 0 1 ) = 2.

For the first time, the problem of calculating the Hamming distance was posed by Minsky and Papert in 1969 [1], where the task was to search for all rows from the database that are within the specified Hamming distance to the requested.

Such a task is unusually simple, but the search for its effective solution is still on the agenda.

Hamming distance is already quite widely used for various tasks, such as finding close duplicates, pattern recognition, document classification, error correction, virus detection, etc.

For example, Manku and associates proposed a solution to the problem of clustering duplicates when indexing web documents based on Hamming distance calculation [2].
Miller and friends also proposed the concept of searching for songs by a given audio fragment [3], [4].
Similar solutions were used for the task of image retrieval and retina recognition [5], [6], etc.

Description of the problem

There is a database of binary strings T , of size n , where the length of each string is m . The requested string a and the required Hamming distance k .

The task is to search for all lines that are within the distance k .

In the original concept of the algorithm, two versions of the problem are considered: static and dynamic.

- In a static problem, the distance k is predetermined in advance.
- In dynamic, on the contrary, the required distance is not known in advance.

The article describes the solution of only a static problem.

Description of the HEngine algorithm for a static task

This implementation focuses on finding rows within k <= 10.

There are three solutions to the static problem: linear scan, query expansion, and database expansion.

In this case, by query expansion we mean the generation of all possible variants of lines that fit into a given distance for the original line.
Expanding the database implies the creation of multiple copies of this database, where either all possible options that meet the requirements of the required distance are either generated, or the data is processed in some other way (more on this later.).

HEngine [8] uses a combination of these three methods to effectively balance between memory and runtime.

Bit of theory

The algorithm is based on a small theorem that states the following:

If for two strings a and b the distance is HD ( a , b ) <= k , then if we divide strings a and b into substrings by the rcut method using the segmentation factor
r > = ⌊ k / 2⌋ + 1
, there must be at least q = r - ⌊ k / 2⌋ substrings, when their distance does not exceed one, HD ( a i, b i) <= 1.

Selecting substrings from the base string by the methodrcut is performed according to the following principles:
A value called a segmentation factor is selected that satisfies the condition
r > = ⌊ k / 2⌋ + 1

The length of the first r - ( m mod r ) substrings will have a length of ⌊ m / r ⌋, and the last m mod r substrings ⌈ m / r ⌉. Where m is the length of the string, ⌊ is rounding to the nearest bottom, and ⌉ rounding to the nearest top.

Now the same thing, just an example:

Given two binary strings of length m= 8 bits: A = 11110000 and B = 11010001, the distance between them is k = 2.
We choose the segmentation factor r = 2/2 + 1 = 2, that is, there will be 2 substrings in length m / r = 4 bits.

a1 = 1111, a2 = 0000
b1 = 1101, b2 = 0001

If we now calculate the distance between the corresponding substrings, then at least ( q = 2 - 2/2 = 1) one substring will coincide or their distance will not exceed one .

What we see:
HD (a1, b1) = HD (1111, 1101) = 1
and
HD (a2, b2) = HD (0000, 0001) = 1 The

substrings of the base line were called signatures .
The signatures or substrings a1 and b1 (a2 and b2, a3 and b3 ..., a r and b r ) are called compatible with each other, and if their number of different bits is not more than one, then these signatures are called matching .

And the main idea of ​​the HEngine algorithm is to prepare the database in such a way as to find matching signatures and then select those lines that are within the required Hamming distance.

Database preprocessing

We already know that if you correctly divide the string into substrings, then at least one substring will coincide with the corresponding substring or the number of different bits will not exceed one (the signatures will coincide).

This means that we do not need to exhaustively search all the rows from the database, but first we need to find the signatures that match, i.e. substrings will differ by a maximum of one.

But how to search by substrings?

The binary search method should do a good job of this. But it requires the list of strings to be sorted. But we get several substrings from one line. To perform a binary search on a list of substrings, it is necessary that each such list be sorted in advance.
Therefore, this begs the method of expanding the database, i.e., creating several tables, each for its own substring or signature. (Such a table is called a signature table . And the totality of such tables is a set of signatures ).

The original version of the algorithm also describes the permutation of substrings so that the selected substrings are in first place. This is done more for ease of implementation and for further optimizations of the algorithm:

There is a line A, which is divided into 3 substrings, a1, a2, a3, a complete list of permutations will be respectively:
a1, a2, a3
a2, a1, a3
a3, a1, a2

Then these signature tables are sorted.

Search implementation

At this stage, after preprocessing the database, we have several copies of the sorted tables, each for its own substring.

Obviously, if we want to find substrings first, we need to get signatures from the requested string in the same way that we used to create signature tables.

We also know that the necessary substrings differ by a maximum of one element. And to find them, you will need to use the query expansion method.

In other words, it is required for the selected substring to generate all combinations including this substring itself, in which the difference will be a maximum of one element. The number of such combinations will be equal to the length of the substring + 1.

And then perform a binary search in the corresponding signature table for a complete match.

Such actions must be performed for all substrings and for all tables.

And at the very end, you need to filter out those lines that do not fit in the specified limit of the Hamming distance. Those. perform a linear search on the found lines and leave only those lines that meet the condition HD ( a , b ) <= k .

Bloom filter

The authors propose using the Bloom filter [7] to reduce the number of binary searches.
A Bloom filter can quickly determine if a substring is in a table with a small percentage of false positives. Which is faster than a table hash.

If before a binary search for a substring in a table, the filter returns that this substring is not in this table, then it makes no sense to search.

Accordingly, you need to create one filter for each signature table.

The authors also note that using the Bloom filter in this way reduces query processing time by an average of 57.8%.

Now the same thing, only with an example

There is a database of binary strings 8 bits long:
11111111
10000001
00111110

The task is to find all strings where the number of different bits does not exceed 2 to the target string 10111111.
That means the required distance is k = 2.

1. Choose the segmentation factor.
Based on the formula, we choose the segmentation factor r = 2, which means that there will be two substrings from one line.

2. Create a set of signatures.
Since the number of substrings is 2, it is only necessary to create 2 tables:
T1 and T2

3. We save the substrings in the corresponding tables with preserving the link to the source.

T1 T2
1111 1111 => 11111111
1000 0001 => 10000001
0011 1110 => 00111110

4. Sort the tables. Each individually.
T1
0011 => 00111110
1000 => 10000001
1111 => 11111111

T2
0001 => 10000001
1110 => 00111110
1111 => 11111111

This completes the pre-processing. And proceed to the search.

1. Get the signatures of the requested string.
The search string 10111110 is broken into signatures. It turns out 1011 and 1100, respectively, the first for the first table, and the second for the second.

2. We generate all combinations differing by one.
The number of options will be 5.

2.1 For the first substring 1011:
1011
0 011
1 1 11
100 1
101 0

2.2 For the second substring 1100:
1100
0 100
1 0 00
11 1 0
110 1

3. Binary search.

3.1 For all generated variants of the first substring 1011, we perform a binary search in the first table for a complete match.

1011
0011 == 0011 => 00111110
1111 == 1111 => 11111111
1001
1010

Two substrings were found.

3.2 Now, for all variants of the second substring 1100, we perform a binary search in the second table.

1100
0100
1000
1110 == 1110 => 00111110
1101

One substring found.

4.
By combining the results into one list: 00111110
11111111

5. Linearly check for compliance and filter out unsuitable conditions <= 2:

HD (10111110, 00111110) = 1
HD (10111110, 11111111) = 2

Both lines satisfy the condition of difference of not more than two elements .

Although a linear search is being performed at this stage, it is expected that the list of candidate lines will not be large at all.
Under conditions when the number of candidates will be large, it is proposed to use a recursive version of HEngine.

Clearly

Figure 1 shows an example of the search algorithm.
For a line length of 64 and a distance limit of 4, the segmentation factor is 3, respectively only 3 substrings per line.
Where T1, T2, and T3 are signature tables containing only the substrings B1, B2, B3, 21, 21, and 22 bits long.

The requested string is divided into substrings. Next, a signature range is generated for the corresponding substrings. For the first and second signatures, the number of combinations will be 22. And the last signature gives 23 options. And at the end, a binary search is performed.


Figure 1. A simplified version of the processing of queries to signature tables.

results

The complexity of such an algorithm in the average case is O ( P * (log n + 1)), where n is the total number of rows in the database, log n + 1 is a binary search, and P is the number of binary searches: in our case, it is considered the number of combinations per table multiplied by the number of tables: P = (64 / r + 1) * r

In extreme cases, the complexity may exceed linear.

It is noted that this approach uses less memory in 4.65 and is 16% faster than the previous work described in [2]. And it is the fastest way known today to find all lines in a given limit.

Implementation

All this, of course, is tempting, but until you touch it in practice, it is difficult to assess the scale.
A prototype of HEngine [9] was created and tested on the available real data.

tests$ ./matches 7 data/db/table.txt data/query/face2.txt
Reading the dataset ........ done. 752420 db hashes and 343 query hashes.
Building with 7 hamming distance bound ....... done.
Building time: 12.964 seconds
Searching HEngine matches .......
found 100 total matches. HEngine query time: 0.1 seconds
Searching linear matches .......
found 100 total matches. Linear query time: 6.828 seconds

The results were pleasing, because finding 343 hashes from the database in 752420 takes ~ 0.1 seconds, which is 60 times faster than a linear search.

It would seem that one could stop here. But I really wanted to try to use it somehow in a real project.

One click before real use

There is a database of image hashes, and a backend for PHP.
The task was somehow to connect the functionality of HEngine and PHP.
It was decided to use FastCGI [10], the posts habrahabr.ru/post/154187 and habrahabr.ru/post/61532 helped me a lot in this .

From PHP, just call:

$list = file_get_contents( 'http://fcgi.local/?' . $hashes );

What ~ 0.5 seconds returns the result. When a linear search takes 9 seconds, and through queries to MySQL, at least 20 seconds.

Thanks to everyone who mastered.

References

[1] M. Minsky and S. Papert. Perceptrons. MIT Press, Cambridge, MA, 1969.
[2] GS Manku, A. Jain, and AD Sarma. Detecting nearduplicates for web crawling. In Proc. 16Th WWW, May 2007.
[3] ML Miller, MA Rodriguez, and IJ Cox. Audio fingerprinting: Nearest neighbor search in high-dimensional binary space. In MMSP, 2002.
[4] ML Miller, MA Rodriguez, and IJ Cox. Audio fingerprinting: nearest neighbor search in high dimensional binary spaces. Journal of VLSI Signal Processing, Springer, 41 (3): 285–291, 2005.
[5] J. Landr ́e and F. Truchetet. Image retrieval with binary hamming distance. In Proc. 2nd VISAPP, 2007.
[6] H. Yang and Y. Wang. A LBP-based face recognition method with hamming distance constraint. In Proc. Fourth ICIG, 2007.
[7] B. Bloom. Space / time trade-offs in hash coding with allowable errors. Communications of ACM, 13 (7): 422-426, 1970.
[8] Alex X. Liu, Ke Shen, Eric Torng. Large Scale Hamming Distance Query Processing. ICDE Conference, pages 553 - 564, 2011.
[9] github.com/valbok/HEngine My implementation of HEngine in C ++
[10] github.com/valbok/HEngine/blob/master/bin/fastcgi.cpp Sample wrapper program to search for hashes through FastCGI.