# US 2010/0169329 A1 · System for similar document detection

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0169329 A1
- Document ID: US20100169329A1
- Status: Published application
- Kind: A1
- Application number: 12/643,662
- Filed: 2009-12-21
- Published: 2010-07-01
- Earliest claimed: 2000-07-31
- Assignees: Alion Science and Technology Corporation
- Inventors: Ophir FRIEDER; Abdur R. Chowdhury
- Web page: https://patentgrep.com/patent/US20100169329A1

## CPC

- G06F 16/3346: {using probabilistic model}
- Y10S 707/99948: Application of database or data structure, e.g. distributed, multimedia, or image
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## Abstract

A document is compared to the documents in a document collection using a hash algorithm and collection statistics to detect if the document is similar to any of the documents in the document collection.

## Claims

### Claim at position 1

1-42. (canceled)

### Claim 43

A method for detecting similar documents comprising:
obtaining a document;
filtering the document to eliminate tokens and obtain a filtered document containing remaining tokens, the tokens being eliminated based on grammatical components;
sorting the filtered document to reorder the tokens according to a predetermined ranking;
generating a single tuple for the filtered document;
comparing the tuple for the filtered document with a document storage structure comprising a plurality of tuples, each tuple in the plurality of tuples representing one of a plurality of documents; and
determining if the tuple for the filtered document is clustered with another tuple in the document storage structure, thereby detecting if the document is similar to another document represented by the another tuple in the document storage structure.

### Claim 44 (depends on 43)

A method as in claim 43, wherein the filtering comprises parsing the document, and wherein the filtered document comprises a token stream, the token stream comprising a plurality of tokens.

### Claim 45 (depends on 44)

A method as in claim 44, wherein the filtering further comprises retaining a token in the token stream as a retained token according to at least one token threshold.

### Claim 46 (depends on 45)

A method as in claim 45, wherein the filtering further comprises reordering the retained tokens in the token stream to obtain a reordered token stream.

### Claim 47 (depends on 43)

A method as in claim 43, wherein the filtering comprises retaining a token in the token stream as a retained token according to at least one token threshold; and
the determining the hash value for the filtered document comprises determining the hash value by processing individually each retained token in the token stream.

### Claim 48 (depends on 44)

A method as in claim 44, wherein the filtering comprises:
determining a score for each token in the token stream;
comparing the score for each token to a first token threshold; and
modifying the token stream by removing each token having a score not satisfying the first token threshold and retaining each token as a retained token having a score satisfying the first token threshold.

### Claim 49 (depends on 48)

A method as in claim 48, wherein the filtering further comprises:
comparing the score for each retained token to a second token threshold; and
modifying the token stream by removing each retained token having a score not satisfying the second token threshold and retaining each retained token having a score satisfying the second token threshold.

### Claim 50 (depends on 44)

A method as in claim 44, wherein the filtering further comprises removing from the token stream at least one token corresponding to a stop word.

### Claim 51 (depends on 44)

A method as in claim 44, wherein the filtering further comprises removing a token from the token stream if the token is a duplicate of another token in the token stream.

### Claim 52 (depends on 44)

A method as in claim 44, wherein the filtering further comprises removing a token from the token stream based on collection statistics and at least one token threshold.

### Claim 53 (depends on 44)

A method as in claim 44, wherein the filtering comprises removing at least one token from the token stream.

### Claim 54 (depends on 43)

A method as in claim 43, wherein the filtering comprises removing formatting from the document.

### Claim 55 (depends on 43)

A method as in claim 43, wherein the filtering uses collection statistics for filtering the document.

### Claim 56 (depends on 55)

A method as in claim 55, wherein the collection statistics pertain to the plurality of documents.

### Claim 57 (depends on 43)

A method as claimed in claim 43, wherein
the method further comprises determining a document identifier for the filtered document and a single hash value for the filtered document,
the tuple comprises the document identifier for the filtered document and the hash value for the filtered document, and
each tuple in the plurality of tuples comprising a document identifier and a hash value.

### Claim 58 (depends on 43)

A method as claimed in claim 43, wherein filtration is based on parts of speech.

### Claim 59 (depends on 43)

A method as claimed in claim 43, wherein filtration removes frequently occurring terms.

### Claim 60 (depends on 43)

A method as claimed in claim 43, wherein filtration removes infrequently occurring terms.

### Claim 61 (depends on 43)

A method as claimed in claim 43, wherein filtration eliminates words having an occurrence frequency that falls within a pre-determined frequency range.

### Claim 62 (depends on 57)

A method as in claim 57, wherein the determining the hash value for the filtered document comprises using a hash algorithm to determine the hash value, the hash algorithm having an approximately even distribution of hash values.

### Claim 63 (depends on 57)

A method as in claim 57, wherein the determining the hash value for the filtered document comprises using a standard hash algorithm to determine the hash value.

### Claim 64 (depends on 57)

A method as in claim 57, wherein the determining the hash value for the filtered document comprises using a secure hash algorithm to determine the hash value.

### Claim 65 (depends on 57)

A method as in claim 57, wherein the determining the hash value for the filtered document comprises using hash algorithm SHA-1 to determine the hash value.

### Claim 66 (depends on 57)

A method as in claim 57, wherein the document storage structure comprises a hash table.

### Claim 67 (depends on 43)

A method as in claim 43, wherein the document storage structure comprises a tree.

### Claim 68 (depends on 67)

A method as in claim 67, wherein the tree comprises a binary tree.

### Claim 69 (depends on 68)

A method as in claim 68, wherein the binary tree comprises a binary balanced tree.

### Claim 70 (depends on 43)

A method as in claim 43, wherein the document storage structure comprises a hash table and at least one tree.

### Claim 71 (depends on 43)

A method as in claim 43, wherein the comprises inserting the tuple into the document storage structure.

### Claim 72 (depends on 57)

A method as in claim 57, wherein the document storage structure comprises a hash table, the hash table comprising a plurality of bins, each bin of the hash table comprising at least one tuple of the plurality of tuples, and
wherein the determining if the tuple is clustered with another tuple comprises determining if the tuple is co-located with another tuple at a bin of the hash table.

### Claim 73 (depends on 43)

A method as in claim 43, wherein the document storage structure comprises a tree, the tree comprising a plurality of branches, each bucket of the tree comprising at least one tuple of the plurality of tuples, and
wherein the determining if the tuple is clustered with another tuple comprises
determining if the tuple is co-located with another tuple in a bucket of the tree.

### Claim 74

An apparatus for detecting similar documents comprising: means for obtaining a document;
means for parsing the document to remove formatting and to obtain a token stream, the token stream comprising a plurality of tokens;
means for retaining only retained tokens in the token stream by using at least one token threshold;
means for reordering the retained tokens to obtain an arranged token stream;
means for processing in turn each retained token in the arranged token stream using a hash algorithm to obtain a single hash value for the document;
means for generating a document identifier for the document;
means for forming a single tuple for the document, the tuple comprising the document identifier for the document and the hash value for the document;
means for inserting the tuple for the document into a document storage tree, the document storage tree comprising a plurality of tuples, each tuple located at a bucket of the document storage tree, each tuple in the plurality of tuples representing one of a plurality of documents, each tuple in the plurality of tuples comprising a document identifier and a hash value; and
means for determining if the tuple for the document is co-located with another tuple at a same bucket in the document storage tree, thereby detecting if the document is similar to another document represented by the another tuple in the document storage tree.

### Claim 75 (depends on 45)

A method as in claim 45, wherein the token threshold represents tokens that are frequently used in the document collection.

### Claim 76 (depends on 75)

A method as in claim 75, wherein frequently used is determined by inverted document frequency scores.

### Claim 77 (depends on 45)

A method as in claim 45, wherein the token threshold represents tokens that are infrequently used in the document collection.

### Claim 78 (depends on 77)

A method as in claim 77, wherein frequently used is determined by inverted document frequency scores.

### Claim 79 (depends on 45)

A method as in claim 45, wherein upper and lower bound token thresholds represent tokens that are within a range of frequency of use in the document collection.

### Claim 80 (depends on 79)

A method as in claim 79, wherein frequency of use is determined by inverted document frequency scores.
