Measuring document similarity by inferring evolution of documents through reuse of passage sequences

1. A method, comprising:

selecting a collection of documents which include a first set of passages;

constructing a passage-sequence model based on the first set of passages, wherein the passage-sequence model is a hidden Markov model (HMM), wherein constructing the passage-sequence model involves determining transition probabilities between states of the HMM based on a sequential relationship associated with the first set of passages;

receiving a new document which includes a second set of passages; and

determining a sequence of operations associated with the new document in relation to the collection of documents based on the constructed passage-sequence model.

2. The method of claim 1 , further comprising estimating a similarity between the new document and at least one document within the collection based on the determined sequence of operations.

3. The method of claim 1 , wherein the method further comprises generating fingerprints for the first set of passages, and wherein at least one fingerprint corresponds to a state of the HMM.

4. The method of claim 3 , further comprising generating fingerprints for the second set of passages, wherein the fingerprints for the second set of passages correspond to an observation sequence of the HMM.

5. The method of claim 4 , further comprising calculating passage similarities by comparing the fingerprints of the second set of passages with the fingerprints of the first set of passages.

6. The method of claim 5 , further comprising determining emission probabilities for the HMM based on the calculated passage similarities.

7. The method of claim 6 , further comprising setting an emission probability for an additional state, which corresponds to creation of a new passage, based on a maximum emission probability of other states belonging to the HMM.

8. The method of claim 3 , wherein the fingerprints of the first set of passages include two-dimensional visual fingerprints.

9. The method of claim 1 , wherein determining the sequence of operations involves applying a Viterbi algorithm to the HMM.

10. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method, the method comprising:

selecting a collection of documents which includes a first set of passages;

constructing a passage-sequence model based on the first set of passages, wherein the passage-sequence model is a hidden Markov model (HMM), wherein constructing the passage-sequence model involves determining transition probabilities between states of the HMM based on a sequential relationship associated with the first set of passages;

receiving a new document which includes a second set of passages; and

determining a sequence of operations associated with the new document in relation to the collection of documents based on the constructed passage-sequence model.

11. The computer-readable storage medium of claim 10 , wherein the method further comprises estimating a similarity between the new document and at least one document within the collection based on the determined sequence of operations.

12. The computer-readable storage medium of claim 10 , wherein the method further comprises generating fingerprints for the first set of passages, and wherein at least one fingerprint corresponds to a state of the HMM.

13. The computer-readable storage medium of claim 12 , wherein the method further comprises generating fingerprints for the second set of passages, and wherein the fingerprints for the second set of passages correspond to an observation sequence of the HMM.

14. The computer-readable storage medium of claim 13 , wherein the method further comprises calculating passage similarities by comparing the fingerprints of the second set of passages with the fingerprints of the first set of passages.

15. The computer-readable storage medium of claim 14 , wherein the method further comprises determining emission probabilities for the HMM based on the calculated passage similarities.

16. The computer-readable storage medium of claim 15 , wherein the method further comprises setting an emission probability for an additional state, which corresponds to creation of a new passage, based on a maximum emission probability of other states belonging to the HMM.

17. The computer-readable storage medium of claim 12 , wherein the fingerprints of the first set of passages include two-dimensional visual fingerprints.

18. The computer-readable storage medium of claim 10 , wherein determining the sequence of operations involves applying a Viterbi algorithm to the HMM.

19. A system, comprising:

a selection mechanism configured to select a collection of documents which includes a first set of passages;

a passage-sequence model construction mechanism configured to construct a passage-sequence model based on the first set of passages, wherein the passage-sequence model is a hidden Markov model (HMM), wherein the passage-sequence model construction mechanism is further configured to determine transition probabilities between states of the HMM based on a sequential relationship associated with the first set of passages;

a receiving mechanism configured to receive a new document which includes a second set of passages; and

a determination mechanism configured to determine a sequence of operations associated with the new document in relation to the collection of documents based on the constructed passage-sequence model.

20. The system of claim 19 , further comprising a similarity-estimation mechanism configured to estimate a similarity between the new document and at least one document within the collection based on the determined sequence of operations.

21. The system of claim 19 , wherein the HMM includes a number of states corresponding to the first set of passages and an additional state corresponding to creation of a new passage.