Generating unweighted samples from weighted features
AssigneeMicrosoft Corporation
InventorsBernhard Haeupler, Kunal Talwar, Mark S. Manasse
Life of this patent
Estimating the term…
Abstract
Weighted features associated with a document are scaled using scales to generate a set of unweighted elements for each scale. A sketch is generated for each scale by sampling the unweighted elements generated for the scale. The scales are chosen based on a selected cutoff factor so that documents that have a similarity that is less than the cutoff factor might have no scales in common, while documents that have a similarity that is greater than the cutoff factor will have at sufficiently many but at least one scale in common. The similarity of these documents can be estimated using the sketches associated with each of the documents for the common scales.
Claims20
A method comprising:
- receiving a set of weighted features by a computing device, wherein the set of weighted features is associated with a first document;
- determining a plurality of scales for the set of weighted features by the computing device;
- for each scale of the plurality of scales, generating an unweighted sketch for the scale by the computing device;
- and
- associating the generated unweighted sketches and the plurality of scales with the first document by the computing device.
A method comprising:
- receiving a first document associated with a first plurality of unweighted sketches, and a first plurality of scales by a computing device;
- receiving a second document associated with a second plurality of unweighted sketches, and a second plurality of scales by the computing device;
- determining that there is not at least one scale in common between the first plurality of scales and the second plurality of scales;
- and
- in response to the determination, determining that the first document is not similar to the second document.
A system comprising:
- at least one computing device;
- and
- a similar document identifier adapted to:
- receive a plurality of documents, wherein each document is associated with weighted features;
- for each document:
- determine a plurality of scales for the weighted features associated with the document;
- for each scale of the plurality of scales, generated an unweighted sketch for the scale from the weighted features associated with the document;
- and
- associate the generated unweighted sketch and the plurality of scales with the document;
- receive an indicator of a first document and a second document from the plurality of documents;
- and
- calculate the similarity of the first document and the second documents using the generated unweighted sketches and the plurality of scales associated with each of the first document and the second document.
Dependencies are inferred from the claim text.