[RFC] idea for a near duplicate filter

Elastic Stack Elasticsearch
1

I have an idea for a filter with a technique I used on another project. I thought I should share because this might be useful to someone.

Finding exact matches is an easy task but finding documents with small differences isnt. Google is using a technique which is very easy to implement and only costs 64 bit (if you choose this size). It is called simhash and is not to be confused with minhash (which Twitter is using).

In simple words simhash works like this:

  1. you hash every token with a classic hash (like Murmur)
  2. you sum up every first bit, second bit and so on (1 = +1 and 0 = -1)
  3. now you have 64 numbers and for every positive number the corresponding simhash bit is 1 and for every zero and negative number the simhash bit is 0

Thats it. Now if you searching for a near duplicate document you only have to compare the simhashes and if it only differs in a small number of bits (the Google paper says a hamming distance of 3 in 64) its a near duplicate.

And there is more. There are things you could do, like giving stop words only a small weight when adding up. Giving synonyms the same (murmur) hash with a smaller weight

Links:
http://www.wwwconference.org/www2007/papers/paper215.pdf


http://www.matpalm.com/resemblance/simhash/

--
You received this message because you are subscribed to the Google Groups "elasticsearch" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elasticsearch+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/elasticsearch/31fe6560-d066-481d-8b7a-7f51cab735a2%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

1 Like
2

Hello Valentin ,

Thanks for this suggestion.
We might find this useful in some of our projects.

Thanks
Vineeth

On Tue, Jul 29, 2014 at 2:42 AM, Valentin pletzer@gmail.com wrote:

I have an idea for a filter with a technique I used on another project. I
thought I should share because this might be useful to someone.

Finding exact matches is an easy task but finding documents with small
differences isnt. Google is using a technique which is very easy to
implement and only costs 64 bit (if you choose this size). It is called
simhash and is not to be confused with minhash (which Twitter is using).

In simple words simhash works like this:

  1. you hash every token with a classic hash (like Murmur)
  2. you sum up every first bit, second bit and so on (1 = +1 and 0 = -1)
  3. now you have 64 numbers and for every positive number the corresponding
    simhash bit is 1 and for every zero and negative number the simhash bit is 0

Thats it. Now if you searching for a near duplicate document you only have
to compare the simhashes and if it only differs in a small number of bits
(the Google paper says a hamming distance of 3 in 64) its a near duplicate.

And there is more. There are things you could do, like giving stop words
only a small weight when adding up. Giving synonyms the same (murmur) hash
with a smaller weight

Links:
http://www.wwwconference.org/www2007/papers/paper215.pdf

http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/CharikarEstim.pdf
simhash

GitHub - twitter/algebird: Abstract Algebra for Scala

--
You received this message because you are subscribed to the Google Groups
"elasticsearch" group.
To unsubscribe from this group and stop receiving emails from it, send an
email to elasticsearch+unsubscribe@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/elasticsearch/31fe6560-d066-481d-8b7a-7f51cab735a2%40googlegroups.com
.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "elasticsearch" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elasticsearch+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/elasticsearch/CAGdPd5%3Doqym%3D2y24rijgWekk2z5%2BZCYX%2BKg3UcCfet3-Lh%2BRjg%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.