EFFICIENT WEIGHTED CONSISTENT SAMPLING

• US 20090192960A1
• Filed: 01/24/2008
• Published: 07/30/2009
• Est. Priority Date: 01/24/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chellapilla, Kumar Hemachandra, Charles, Denis Xavier
• Granted Patent: US 7,925,598 B2
• Time in Patent Office: Days
• US Class Current: 706/46
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04

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 w^th 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.

Claims

1. 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 by determining a w^th root of a value based on the respective consistent uniformly distributed random number, such that w is based on a weight assigned to the corresponding element;

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.

2. The machine-implemented method of claim 1, further comprising:

applying a hash function to each of the elements of the plurality of sets to provide each of the respective consistent uniformly distributed non-negative random numbers.

3. The machine-implemented method of claim 1, wherein the transforming of each respective consistent uniformly distributed non-negative random number to a transformed value further comprises:

transforming each respective consistent uniformly distributed non-negative random number according to a formula

$h_x\leftarrow <br><br>\frac{a-{\left(1-h<br><br>\left(x\right)\right)}^{\frac{1}{w<br><br>\left(x\right)}}}{b},$

where h(x) is a consistent uniformly distributed non-negative random number representing an element x of a set, a and b are constants, and w(x) is a weight assigned to the element x.

4. The machine-implemented method of claim 3, wherein:

the a and the b are equal to 1,

the respective minimum transformed value for each of the plurality of sets is determined, and

which of the plurality of sets are at least similar is determined based on the respective determined minimum transformed value for each of the plurality of sets.

5. The machine-implemented method of claim 1, further comprising:

determining a predetermined number of respective minimum transformed values for each of the plurality of sets or a predetermined number of respective maximum transformed values for each of the plurality of sets; and

determining which of the plurality of sets are near duplicates based on matches among the predetermined number of the respective determined minimum transformed values for each of the plurality of sets or the predetermined number of the respective determined maximum transformed values for each of the plurality of sets.

6. The machine-implemented method of claim 1, wherein:

each of the plurality of sets represents information pertaining to a different user, and

the machine-implemented method further comprises;

performing collaborative filtering by;

predicting a preference for the particular user based on a preference of a user corresponding to one of the plurality of sets similar to the set pertaining the particular user.

7. The machine-implemented method of claim 1, wherein:

each of the plurality of sets represents edge information pertaining to a different vertex of a graph,

each of the respective consistent uniformly distributed random numbers corresponds to an item of the edge information for a respective vertex of the graph, and

the machine-implemented method further comprises;

performing graph clustering by clustering ones of the plurality of vertices that are determined to be at least similar.

8. The machine-implemented method of claim 1, wherein:

each of the plurality of sets represents link information pertaining to a different node of a graph,

each of the respective consistent uniformly distributed random numbers corresponds to an item of the link information for a respective node of the graph, and

the machine-implemented method further comprises;

performing graph compression by compressing the graph based on the ones of the plurality of nodes that are determined to be at least similar.

9. A processing device comprising:

at least one processor; and

a memory connected to the at least one processor, the memory further comprising;

instructions for transforming, in only a single pass through original elements of a plurality of sets, respective consistent uniformly distributed non-negative random numbers, representing the original elements of the plurality of sets, to transformed values according to a formula

$h_x\leftarrow <br><br>\frac{a-{\left(1-h<br><br>\left(x\right)\right)}^{\frac{1}{w<br><br>\left(x\right)}}}{b},$

 

where h(x) is a consistent uniformly distributed non-negative random number representing an original element x of a set, a and b are constants, and w(x) is based on a weight assigned to the original element x, and

instructions for determining a similarity among a plurality of the sets based on a respective minimum transformed value of each of the plurality of sets or based on a respective maximum transformed value of each of the plurality of sets.

10. The processing device of claim 9, wherein the memory further comprises:

instructions for providing the respective consistent uniformly distributed non-negative random numbers by applying only one hash function to the original elements of the plurality of sets.

11. The processing device of claim 9, wherein:

each of the plurality of sets corresponds to a different document of a plurality of documents and each of the original elements of each of the plurality of sets corresponds to a respective word of a respective one of the plurality of documents, and

the memory further comprises;

instructions for assigning weights to the original elements, such that ones of the original elements corresponding to words related to a particular subject matter are assigned a weight indicating a higher level of relevance than others of the original elements.

12. The processing device of claim 11, wherein the weight indicating a higher level of relevance has a higher value than other weights having a lower level of relevance.

13. The processing device of claim 9, wherein:

each of the plurality of sets includes purchasing information with respect to a different user,

each of the original elements of a respective one of the plurality of sets represents historical purchasing information of a corresponding one of the different users, and

the memory further comprises;

instructions for predicting a desire of a particular user for a particular item based on ones of the plurality of sets determined to be similar to a set corresponding to the particular user, and

instructions for informing the particular user of the particular item.

14. 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\leftarrow <br><br>\frac{a-{\left(1-h<br><br>\left(x\right)\right)}^{\frac{1}{w<br><br>\left(x\right)}}}{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 h_x 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.

15. The machine-implemented method of claim 14, further comprising:

dividing the plurality of sets among a plurality of processors, each of the plurality of processors performing, in parallel, acts of claim 14 with respect to associated ones of the plurality of sets;

merging results of the plurality of processors with respect to the acts of claim 14; and

determining similar ones of the plurality of sets based on the merged results.

16. The machine-implemented method of claim 14, wherein:

each of the plurality of sets corresponds to a different document of a plurality of documents and each of the elements of each of the plurality of sets corresponds to a respective word of a respective one of the plurality of documents, and

the machine-implemented method further comprises;

determining near-duplicate ones of the plurality of documents based on the determined similar ones of the plurality of sets.

17. The machine-implemented method of claim 14, wherein:

a and b are equal to 1,

w(x) is the weight associated with the element x, and

the determining of similar ones of the plurality of sets based on at least one of the transformed values of each of the plurality of sets further comprises;

determining a match among a predetermined number of minimum ones of the transformed values of each of the plurality of sets.

18. The machine-implemented method of claim 14, wherein:

the providing of consistent uniformly distributed non-negative random numbers for each of a plurality of original elements of a plurality of sets further comprises;

applying only one hash to each of the plurality of original elements of the plurality of sets, the hash being a perfect hash.

19. The machine-implemented method of claim 14, wherein:

each of the plurality of sets represents link information pertaining to a different node of a graph,

each of the provided consistent uniformly distributed non-negative random numbers corresponds to an item of the link information for a respective node of the graph, and

the determining of similar ones of the plurality of sets is based on respective minimum or maximum ones of the transformed values of each of the plurality of sets, and

the machine-implemented method further comprises;

performing graph compression by compressing the graph based on the determined similar ones of the plurality of sets.

20. The machine-implemented method of claim 14, wherein:

the providing of consistent uniformly distributed non-negative random numbers for each of a plurality of original elements of a plurality of sets further comprises;

applying only one hash function to each of the plurality of original elements of the plurality of sets, the hash function being a perfect hash, and the method further comprises;

applying the formula,

$h_x\leftarrow <br><br>\frac{a-{\left(1-h<br><br>\left(x\right)\right)}^{\frac{1}{w<br><br>\left(x\right)}}}{b}$

to each of the original elements of the plurality of sets only once, where h(x) is the one hash function.