Hashing techniques for data set similarity determination

Patent metadata

Field	Value
Publication number	US-9311403-B1
Application number	US-201113162061-A
Country	US
Kind code	B1
Filing date	Jun 16, 2011
Priority date	Jun 16, 2010
Publication date	Apr 12, 2016
Grant date	Apr 12, 2016

Abstract

Methods, systems and computer program product embodiments for hashing techniques for determining similarity between data sets are described herein. A method embodiment includes, initializing a random number generator with a weighted min-hash value as a seed, wherein the weighted min-hash value approximates a similarity distance between data sets. A number of bits in the weighted min-hash value is determined by uniformly sampling an integer bit value using the random number generator. A system embodiment includes a repository configured to store a plurality of data sets and a hash generator configured to generate weighted min-hash values from the data sets. The system further includes a similarity determiner configured to determine a similarity between the data sets.

First claim

What is claimed is:

1. A computer implemented method of improving similarity distance approximation between data sets, comprising:
initializing, using one or more processors, a random number generator with a weighted rain-hash value as a seed, wherein the weighted min-hash value approximates the similarity distance between two or more data sets;
uniformly sampling, using the one or more processors, an integer bit value using the random number generator to determine a first number of bits used to represent a single weighted min-hash value;
determining, using the one or more processors, an adjusted number of bits to sample based on distance estimate variances of a total number of bits to sample; and
varying, using the one or more processors, the determined first number of bits used to represent the single, weighted min-hash value to determine a least number of bits capable of being used to represent the single weighted rain-hash value while achieving a target weighted rain-hash accuracy, wherein the weighted min-hash accuracy specifies a similarity distance approximation between the data sets; and
adjusting a number of bits used to represent the single weighted rain-hash value based on the determined least number of bits.

2. The method of claim 1 , wherein the sampling minimizes inconsistency between the similarity distance and the approximation induced by the Hamming distance between bit samples.

3. The method of claim 1 , further comprising: selecting a plurality hash subsets from a plurality of weighted rain-hash values.

4. The method of claim 3 , wherein the selecting comprises: selecting the hash subsets using randomized hash selection.

5. The method of claim 3 , further comprising: adding hash subsets associated with the highest similarity distance approximation to a set of selected hashes.

6. An article of manufacture including a non-transitory computer-readable medium having instructions stored thereon that, when executed by a processing device, cause the processing device to perform operations comprising:
initializing, using one or more processors, a random number generator with a weighted min-hash value as a seed, wherein the weighted min-hash value approximates a similarly distance between two or more data sets;
uniformly sampling, using the one or more processors, an integer bit value using the random number generator to determine a first number of bits used to represent a single weighted min-hash value;
determining, using the one or more processors, an adjusted number of bits to sample based on distance estimate variances of a total number of bits to sample; and
varying, using the one or more processors, the determined first number of bits used to represent a single weighted min-hash value to determine a least number of bits capable of being used to represent, the single weighted rain-hash value while achieving a target weighted min-hash accuracy, wherein the weighted rain-hash accuracy specifies a similarity distance approximation between the data sets; and
adjusting a number of bits used to represent the single weighted min-hash value based on the determined least number of bits.

7. The article of manufacture of claim 6 , wherein the sampling minimizes a Hamming distance between the data sets.

8. The article of manufacture of claim 6 , the operations further comprising: selecting a plurality hash subsets from a plurality of weighted rain-hash values.

9. The article of manufacture of claim 8 , the selecting comprising:
selecting the hash subsets using randomized hash selection.

10. The article of manufacture of claim 8 , the operations further comprising: adding hash subsets with associated with the highest similarity distance approximation to a set of selected hashes.

11. A computer implemented method of improving similarity distance approximation between data sets, comprising:
determining, using one or more processors, a number of bits to sample for a weighted min-hash value; initializing, using the one or more processors, a random number generator with the weighted min-hash value as a seed, wherein the weighted min-hash value approximates a similarity distance between two or more data sets;
uniformly sampling, using the one or more processors, an integer bit value from numbers generated by the random number generator, wherein the sampled integer bit value comprises the determined number of bits to sample, wherein the sampling is performed in deterministic constant time, and wherein deterministic constant time sampling comprises pre-computing estimators of a distance between the two or more data sets based on random values; and
determining a number of bits to sample based on a distance estimate variance of a total number of bits available and the determined number of bits; and
varying, using the one or more processors, the determined first number of bits used to represent a single weighted min-hash value to determine a least number of bits capable of being used to represent the single weighted rain-hash value while achieving a target weighted min-hash accuracy, wherein the weighted min-hash accuracy specifies a similarity distance approximation between the data sets; and
adjusting a number of bits used to represent the single weighted rain-hash value based on the determined least number of bits.

12. The method of claim 11 , further comprising determining a Hamming similarity of the determined number of bits to sample for the weighted min-hash value.

13. The method of claim 11 , wherein the one or more bits are sampled from one or more images.

Assignees

• Ioffe Sergey
• Google Inc

Inventors

• Ioffe Sergey

Classifications

• G06F17/30864 Primary

  Physics · mapped topic

• G06F16/5838 Primary

  using colour · CPC title

• G06F16/583

  using metadata automatically derived from the content · CPC title

• G06F16/951 Primary

  Indexing; Web crawling techniques · CPC title