US5909677A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for determining the resemblance of documents
Assignee: AltaVista Co
•
Filing: 1996-06-18
•
Granted: 1999-06-01
•
Expires: 2016-06-18
Abstract
Abstract A method for facilitating the comparison of two computerized documents. The method includes loading a first document into a random access memory (RAM), loading a second document into the RAM, reducing the first document into a first sequence of tokens, reducing the second document into a second sequence of tokens, converting the first set of tokens to a first (multi)set of shingles, converting the second set of tokens to a second (multi)set of shingles, determining a first sketch of the first (multi)set of shingles, determining a second sketch of the second (multi)set of shingles, and comparing the first sketch and the second sketch. The sketches have a fixed size, independent of the size of the documents. The resemblance of two documents is provided using a sketch of each document. The sketches may be computed fairly fast and given two sketches the resemblance of the corresponding documents can be computed in linear time in the size of the sketches.
Inventors
- 👤 Andrei Zary Broder
- 👤 Charles Gregory Nelson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 03:18
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/35; G06F16/355; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99951; Y10S707/99952; Y10S707/99953
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
118 words
A method of determining the resemblance of a plurality of documents comprising the steps of: reducing a first of the plurality of documents into a first sequence of tokens; reducing a second of the plurality of documents into a second sequence of tokens; converting the first sequence of tokens to a first set of shingles; converting the second sequence of tokens to a second set of shingles; determining a first sketch of the first document from the first set of shingles; determining a second sketch of the second document from the second set of shingles; and comparing the first sketch and the second sketch so as to determine the resemblance between the first document and the second document.
Claim 2
Independent Claim
118 words
A method of determining the resemblance of a plurality of documents comprising the steps of: reducing a first of the plurality of documents into a first sequence of tokens; reducing a second of the plurality of documents into a second sequence of tokens; converting the first sequence of tokens to a first set of shingles; converting the second sequence of tokens to a second set of shingles; determining a first sketch of the first document from the first set of shingles; determining a second sketch of the second document from the second set of shingles; and comparing the first sketch and the second sketch so as to determine the resemblance between the first document and the second document.
Claim 3
Dependent Claim
35 words
The method as defined in claim 1, wherein the first sketch includes less than all of the first set of shingles, and the second sketch includes less than all of the second set of shingles.
Claim 4
Dependent Claim
19 words
The method as defined in claim 1, wherein the first sketch and the second sketch are fixed in size.
Claim 5
Dependent Claim
39 words
The method as defined in claim 3, further comprising the step of: computing the resemblance between the first document and the second document in linear time corresponding to the fixed size of the first sketch and the second sketch.
Claim 6
Dependent Claim
53 words
The method as defined in claim 1, further comprising the steps of: storing the first document in a first memory prior to reducing the first document into the first sequence of tokens; and storing the second document in a second memory prior to reducing the second document into the second sequence of tokens.
Claim 7
Dependent Claim
19 words
The method as defined in claim 5, wherein the first memory and the second memory are the same memory.
Claim 8
Independent Claim
103 words
A method for determining the resemblance of a plurality of documents each including a respective plurality of elements, the method comprising the steps of: generating a first representation of a first of the plurality of documents, the first representation including at least one proper subset of the elements of the first document; generating a second representation of a second of the plurality of documents, the second representation including at least one proper subset of the elements of the second document; and comparing the first representation and the second representation so as to determine the resemblance between the first document and the second document.
Claim 9
Independent Claim
103 words
A method for determining the resemblance of a plurality of documents each including a respective plurality of elements, the method comprising the steps of: generating a first representation of a first of the plurality of documents, the first representation including at least one proper subset of the elements of the first document; generating a second representation of a second of the plurality of documents, the second representation including at least one proper subset of the elements of the second document; and comparing the first representation and the second representation so as to determine the resemblance between the first document and the second document.
Claim 10
Dependent Claim
19 words
The method as defined in claim 7, wherein the first representation and the second representation are fixed in size.
Claim 11
Dependent Claim
39 words
The method as defined in claim 8, further comprising the step of: computing the resemblance between the first document and the second document in linear time corresponding to the fixed size of the first representation and the second representation.
Claim 12
Dependent Claim
41 words
The method as defined in claim 7, wherein the first document has a first size, and wherein the step of generating the first representation includes generating the first representation in linear time corresponding to the first size of the first document.
Claim 13
Dependent Claim
45 words
The method as defined in claim 7, wherein the second document has a second size, and wherein the step of generating the second representation includes generating the second representation of the second document in linear time corresponding to the second size of the second document.
Claim 14
Dependent Claim
33 words
The method as defined in claim 7, wherein the at least one subset of the elements of the first document is at least one random subset of the elements of the first document.
Claim 15
Dependent Claim
33 words
The method as defined in claim 7, wherein the at least one subset of the elements of the second document is at least one random subset of the elements of the second document.
Claim 16
Dependent Claim
54 words
The method as defined in claim 7, further comprising the steps of: storing the first representation as a first ordered list; and storing the second representation as a second ordered list; wherein the step of comparing the first representation and the second representation includes merging the first ordered list and the second ordered list.
Claim 17
Independent Claim
124 words
A system for determining the resemblance of a plurality of documents each including a respective plurality of elements, the system comprising: at least one memory for storing the plurality of documents; and at least one processor coupled to the at least one memory configured to: generate a first representation of a first of the plurality of documents, the first representation including at least one proper subset of the elements of the first document; generate a second representation of a second of the plurality of documents, the second representation including at least one proper subset of the elements of the second document; and compare the first representation and the second representation so as to determine the resemblance between the first document and the second document.
Claim 18
Independent Claim
124 words
A system for determining the resemblance of a plurality of documents each including a respective plurality of elements, the system comprising: at least one memory for storing the plurality of documents; and at least one processor coupled to the at least one memory configured to: generate a first representation of a first of the plurality of documents, the first representation including at least one proper subset of the elements of the first document; generate a second representation of a second of the plurality of documents, the second representation including at least one proper subset of the elements of the second document; and compare the first representation and the second representation so as to determine the resemblance between the first document and the second document.
Claim 19
Dependent Claim
19 words
The system as defined in claim 15, wherein the first representation and the second representation are fixed in size.
Claim 20
Dependent Claim
44 words
The system as defined in claim 16, wherein the at least one processor is further configured to: compute the resemblance between the first document and the second document in linear time corresponding to the fixed size of the first representation and the second representation.
Claim 21
Dependent Claim
47 words
The system as defined in claim 15, wherein the first document has a first size, and wherein the at least one processor is further configured to generate the first representation by generating the first representation in linear time corresponding to the first size of the first document.
Claim 22
Dependent Claim
47 words
The system as defined in claim 15, wherein the second document has a second size, and wherein the at least one processor is further configured to generate the second representation by generating the second representation in linear time corresponding to the second size of the second document.
Claim 23
Dependent Claim
33 words
The system as defined in claim 15, wherein the at least one subset of the elements of the first document is at least one random subset of the elements of the first document.
Claim 24
Dependent Claim
33 words
The system as defined in claim 15, wherein the at least one subset of the elements of the second document is at least one random subset of the elements of the second document.
Claim 25
Dependent Claim
63 words
The system as defined in claim 15, wherein the at least one memory is configured to: store the first representation as a first ordered list; and store the second representation as a second ordered list; wherein the at least one processor is configured to compare the first representation and the second representation by merging the first ordered list and the second ordered list.
Claim 26
Dependent Claim
151 words
An article of manufacture for determining the resemblance of a plurality of documents each including a respective plurality of elements, the article of manufacture comprising: a computer readable storage medium; and computer programming stored on the storage medium; wherein the stored computer programming is configured to be readable from the computer readable storage medium by at least one computer and thereby cause the at least one computer to operate so as to: generate a first representation of a first of the plurality of documents, the first representation including at least one proper subset of the elements of the first document; generate a second representation of a second of the plurality of documents, the second representation including at least one proper subset of the elements of the second document; and compare the first representation and the second representation so as to determine the resemblance between the first document and the second document.
Claim 27
Dependent Claim
151 words
An article of manufacture for determining the resemblance of a plurality of documents each including a respective plurality of elements, the article of manufacture comprising: a computer readable storage medium; and computer programming stored on the storage medium; wherein the stored computer programming is configured to be readable from the computer readable storage medium by at least one computer and thereby cause the at least one computer to operate so as to: generate a first representation of a first of the plurality of documents, the first representation including at least one proper subset of the elements of the first document; generate a second representation of a second of the plurality of documents, the second representation including at least one proper subset of the elements of the second document; and compare the first representation and the second representation so as to determine the resemblance between the first document and the second document.
Claim 28
Dependent Claim
21 words
The article of manufacture as defined in claim 23, wherein the first representation and the second representation are fixed in size.
Claim 29
Dependent Claim
48 words
The article of manufacture as defined in claim 24, further causing the at least one computer to operate so as to: compute the resemblance between the first document and the second document in linear time corresponding to the fixed size of the first representation and the second representation.
Claim 30
Dependent Claim
46 words
The article of manufacture as defined in claim 23, wherein the first document has a first size, and further causing the at least one computer to operate so as to: generate the first representation in linear time corresponding to the first size of the first document.
Claim 31
Dependent Claim
46 words
The article of manufacture as defined in claim 23, wherein the second document has a second size, and further causing the at least one computer to operate so as to: generate the second representation in linear time corresponding to the second size of the second document.
Claim 32
Dependent Claim
35 words
The article of manufacture as defined in claim 23, wherein the at least one subset of the elements of the first document is at least one random subset of the elements of the first document.
Claim 33
Dependent Claim
35 words
The article of manufacture as defined in claim 23, wherein the at least one subset of the elements of the second document is at least one random subset of the elements of the second document.
Claim 34
Dependent Claim
59 words
The article of manufacture as defined in claim 23, further causing the at least one computer to operate so as to: store the first representation as a first ordered list; store the second representation as a second ordered list; and comparing the first representation and the second representation by merging the first ordered list and the second ordered list.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-05-31 | 2002-11-30 | 2003-06-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-05-31 | 2006-11-30 | 2007-06-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-05-31 | 2010-11-30 | 2011-06-01 | $7700.00 | Window Closed / Lapsed |