US 7,925,598 B2 · Efficient weighted consistent sampling

Abstract

A method and a processing device may be provided for performing efficient weighted consistent sampling. A group of sets having multiple elements with associated weights may be provided. A single hash function may be applied to each of the elements of the group of sets to produce consistent uniformly distributed non-negative random numbers. Transformed values corresponding to each of the elements may be produced by determining a wth root of a value based on applying the hash function to a respective element, where w may be based on a weight associated with the respective element. A minimum transformed value or a maximum transformed value may be determined for each of the sets. Sets having matching ones of the minimum transformed value or the maximum transformed value may be determined. The determined sets may be considered to be similar.

Claims19

Dependent claims

A machine-implemented method for performing weighted consistent sampling, the machine-implemented method comprising:

transforming each respective consistent uniformly distributed non-negative random number, representing a corresponding element of a plurality of sets, to a transformed value according to a formula
h
x
←
a
-
(
1
-
h
⁡
(
x
)
)
1
w
⁡
(
x
)
b
,
where h(x) is a consistent uniformly distributed non-negative random number representing a corresponding element x of a set, a and b are constants, and w(x) is a weight assigned to the corresponding element x;
determining a respective minimum transformed value for each of the plurality of sets or a respective maximum transformed value for each of the plurality of sets;
and
determining which of the plurality of sets are at least similar based on the respective determined minimum transformed value for each of the plurality of sets or the respective determined maximum transformed value for each of the plurality of sets, wherein
the machine-implemented method is implemented by at least one processing device.

25 more elements

A machine-implemented method for performing weighted consistent sampling, the machine-implemented method comprising:

providing a consistent uniformly distributed non-negative random number for each of a plurality of original elements of a plurality of sets;
providing a respective weight to each of the plurality of original elements, the respective weight being indicative of a level of relevance;
applying a formula
h
x
←
a
-
(
1
-
h
⁡
(
x
)
)
1
w
⁡
(
x
)
b
,
where h(x) is one of the provided uniformly distributed non-negative random number representing an element x of a set, a and b are constants, w(x) is based on a weight associated with the element x, and hx is a transformed value;
and
determining similar ones of the plurality of sets based on at least one of the transformed values of each of the plurality of sets, wherein
the machine-implemented method is implemented by at least one processing device.

26 more elements

Dependencies are inferred from the claim text.

Efficient weighted consistent sampling

Life of this patent

Efficient weighted consistent sampling

Life of this patent

Abstract

Claims19