11

I have a process, similar to tineye that generates perceptual hashes, these are 32bit ints.

I intend to store these in a sql database (maybe a nosql db) in the future

However, I'm stumped at how I would be able to retrieve records based on the similarity of hashes.

Any Ideas?

4
  • Probably going to need more information: are you considering the Hamming distance of the binary representations, or something else? Commented Mar 16, 2012 at 15:27
  • I'll be considering the hamming distance of the hash I have from the image, to the hashes stored in the database Commented Apr 17, 2012 at 17:19
  • What I meant was: unless I'm misunderstanding, Hamming distance is a property of a pair of strings, and you've got ints. How are you stringifying your ints - 32 1s and 0s, or some other way? Commented Apr 17, 2012 at 17:40
  • You're confusing the terminology of maths with the string type. A integer can be seen as a list of '0' and '1' elements. A 'string' type is just a list of bytes (let's not get into DBCS and unicode). Commented May 15, 2012 at 0:56

3 Answers 3

26

A common approach (at least common to me) is to divide your hash bit string in several chunks and query on these chunks for an exact match. This is a "pre-filter" step. You then can perform a bitwise hamming distance computation on the returned results which should be only a smaller subset of your overall dataset. This can be done using data files or SQL tables.

So in simple terms: Say you have a bunch of 32 bits hashes in a DB and that you want to find every hash that are within a 4 bits hamming distance of your "query" hash:

  1. Create a table with four columns: each will contain an 8 bits (as a string or int) slice of the 32 bits hashes, islice 1 to 4.

  2. Slice your query hash the same way in qslice 1 to 4.

  3. Query this table such that any of qslice1=islice1 or qslice2=islice2 or qslice3=islice3 or qslice4=islice4. This gives you every DB hash that are within 3 bits (4 - 1) of the query hash. It may contain more results, and this is why there is a step 4.

  4. For each returned hash, compute the exact hamming distance pair-wise with you query hash (reconstructing the index-side hash from the four slices)

The number of operations in step 4 should be much less than a full pair-wise hamming computation of your whole table.

This approach was first described afaik by Moses Charikar in its "simhash" seminal paper and the corresponding Google patent:

  1. APPROXIMATE NEAREST NEIGHBOR SEARCH IN HAMMING SPACE

[...] Given bit vectors consisting of d bits each, we choose N = O(n 1/(1+ ) ) random permutations of the bits. For each random permutation σ, we maintain a sorted order O σ of the bit vectors, in lexicographic order of the bits permuted by σ. Given a query bit vector q, we find the approximate nearest neighbor by doing the following:

For each permutation σ, we perform a binary search on O σ to locate the two bit vectors closest to q (in the lexicographic order obtained by bits permuted by σ). We now search in each of the sorted orders O σ examining elements above and below the position returned by the binary search in order of the length of the longest prefix that matches q.

Monika Henziger expanded on this in her paper "Finding near-duplicate web pages: a large-scale evaluation of algorithms":

3.3 The Results for Algorithm C

We partitioned the bit string of each page into 12 non- overlapping 4-byte pieces, creating 20B pieces, and computed the C-similarity of all pages that had at least one piece in common. This approach is guaranteed to find all pairs of pages with difference up to 11, i.e., C-similarity 373, but might miss some for larger differences.

NB: C-similarity is the same as the Hamming distance: The Hamming distance is the number of positions at which the corresponding bits differ while C-similarity is the number of positions at which the corresponding bits agree.

This is also explained in the paper Detecting Near-Duplicates for Web Crawling by Gurmeet Singh Manku, Arvind Jain, and Anish Das Sarma:

  1. THE HAMMING DISTANCE PROBLEM

Definition: Given a collection of f -bit fingerprints and a query fingerprint F, identify whether an existing fingerprint differs from F in at most k bits. (In the batch-mode version of the above problem, we have a set of query fingerprints instead of a single query fingerprint)

[...] Intuition: Consider a sorted table of 2 d f -bit truly random fingerprints. Focus on just the most significant d bits in the table. A listing of these d-bit numbers amounts to “almost a counter” in the sense that (a) quite a few 2 d bit- combinations exist, and (b) very few d-bit combinations are duplicated. On the other hand, the least significant f − d bits are “almost random”.

Now choose d such that |d − d| is a small integer. Since the table is sorted, a single probe suffices to identify all fingerprints which match F in d most significant bit-positions. Since |d − d| is small, the number of such matches is also expected to be small. For each matching fingerprint, we can easily figure out if it differs from F in at most k bit-positions or not (these differences would naturally be restricted to the f − d least-significant bit-positions).

The procedure described above helps us locate an existing fingerprint that differs from F in k bit-positions, all of which are restricted to be among the least significant f − d bits of F. This takes care of a fair number of cases. To cover all the cases, it suffices to build a small number of additional sorted tables, as formally outlined in the next Section.

PS: Most of these fine brains are/were associated with Google at some level or some time for these, FWIW.

Sign up to request clarification or add additional context in comments.

15 Comments

This is really a good discussion on the problem, I'm going to have to reassign the accepted answer to this one from @David Manheim's original answer
@PhilippeOmbredanne Your link is 404. Use the archive link instead: web.archive.org/web/20170309155017/http://www.cse.unsw.edu.au/…
I think this should not be the accepted answer. Probably the papers/patents are OK but the solution won't work. Now let me show how it yields a hash with 24 bits of Hamming distance: StoredHash=[0xFF],[0xFF],[0xFF],[0xFF], QueryHash= [0xFF],[0x00],[0x00], [0x00]. The condition is satisfied by q_slice1=i_slice1, hence we get the hash with 24 bits of distance selected.
I went ahead and implemented this - it works extremely well. I added around 3000 photos to an index using a 64-bit phash, using four 16-bit INT columns with a covering index in SQLite. ~98% of the returned results have the desired distance, less than 2% need further filtering. A duplicate search among all files takes ~2 seconds on my 7 years old system. This technique is crazy fast!
I have been thinking about this extensively and reading arxiv.org/pdf/1307.2982.pdf, a key reference. The confusion here is the wording used by Philippe Ombredanne, which is incorrect. To address @A.Genchev point, the correct wording is that it guarantees that any result within a hamming distance of 3 is included but it does not guarantee that all results have a hamming distance of 3 or fewer. As correctly demonstrated, 24 > 3 but no results <=3 will be missed
|
4

David's discussion is correct, but if you don't have a lot of data, check out Hamming distance on binary strings in SQL

Comments

1

To find hamming distance, you can just use bitwise addition and subtraction (& and ~ on the integers) in order to compute these.

SQL isn't made for this sort of processing. The comparisons on large data sets get very messy, and will not have the speed of a query that utilizes the strength of the system. That said, I've done similar things.

This will give you individual differences, which would need to be run on the full data set and ordered, which is messy at best. If you want it to run faster, you will need to use strategies like indexing by "region," or finding natural groupings in your data. There are umbrella clustering strategies, and similar - there is a lot of literature. It will, however, be messy in most traditional Database systems.

9 Comments

As you can see from the related questions and answers, the suggestions are almost all not using databases.
@DavidManheim IMHO there is nothing in SQL that prohibits this sort of processing. See my answer for a practical approach that works in and outside a DB.
FWIW, this "clever hack" as you call is considered by many as the state of the art for bounded hamming distance queries ;) .... and I agree SQL is not a panacea there (and this hack works equally if not better with sorted files and binary search)
The clever hack is implementing it in SQL, not the method itself!
@David Manheim - I'm not sure who downvoted you, however Phillipe's answer has a deeper discussion on the issues I had.
|

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.