Hashing techniques for data set similarity determination
AssigneeGoogle Inc.
InventorSergey Ioffe
Life of this patent
Estimating the term…
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.
Claims13
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.
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.
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.
Dependencies are inferred from the claim text.