Method for determining the resemblance of documents

• US 5,909,677 A
• Filed: 06/18/1996
• Issued: 06/01/1999
• Est. Priority Date: 06/18/1996
• Status: Expired due to Term

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Broder, Andrei Zary, Nelson, Charles Gregory
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US08/665,709
• Time in Patent Office: 1,078 Days
• Field of Search: 707/3, 707/6, 707/1, 707/203, 707/201
• US Class Current: 1/1
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

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.

Claims

1. 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.

2. 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.

3. The method as defined in claim 1, wherein the first sketch and the second sketch are fixed in size.

4. 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.

5. 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.

6. The method as defined in claim 5, wherein the first memory and the second memory are the same memory.

7. 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.

8. The method as defined in claim 7, wherein the first representation and the second representation are fixed in size.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. The system as defined in claim 15, wherein the first representation and the second representation are fixed in size.

17. 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.

18. 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.

19. 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.

20. 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.

21. 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.

22. 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.

23. 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.

24. The article of manufacture as defined in claim 23, wherein the first representation and the second representation are fixed in size.

25. 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.

26. 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.

27. 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.

28. 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.

29. 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.

30. 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.