US6240409B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for detecting and summarizing document similarity within large document sets
Assignee: University of California
•
Filing: 1998-07-31
•
Granted: 2001-05-29
•
Expires: 2018-07-31
Abstract
Abstract A method and apparatus are disclosed for comparing an input or query file to a set of files to detect similarities and formatting the output comparison data are described. An input query file that can be segmented into multiple query file substrings is received. A query file substring is selected and used to search a storage area containing multiple ordered file substrings that were taken from previously analyzed files. If the selected query file substring matches any of the multiple ordered file substrings, match data relating to the match between the selected query file substring and the matching ordered file substring is stored in a temporary file. The matching ordered file substring and another ordered file substring are joined if the matching ordered file substring and the second ordered file substring are in a particular sequence and if the selected query file substring and a second query file substring are in the same particular sequence. If the matching ordered file substring and the second query file substring match, a coalesced matching ordered substring and a coalesced query file substring are formed that can be used to format output comparison data.
Inventors
- 👤 Alexander Aiken
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 20:54
CPC Classifications
G; G06; G06F; G06F40/00; G06F40/20; G06F40/279; G06F40/289; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90344; G06F40/10; G06F40/194; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934; Y10S707/99937; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
192 words
A method of comparing a query file to one or more stored files, the method comprising: receiving a query file having a plurality of query file substrings; selecting a first query file substring from the plurality of query file substrings; preprocessing the first query file substring thereby making the substring more suitable for searching in the storage area; searching a storage area storing a plurality of ordered file substrings for the first query file substring; storing match data relating to a match between the first query file substring and a first ordered file substring; and joining the first ordered file substring and a second ordered file substring if the first ordered file substring and the second ordered file substring are in a particular sequence and joining the first query file substring and a second query file substring if the first query file substring and the second query file substring are in the same particular sequences wherein the second ordered file substring and the second query file substring match, thereby forming a third coalesced ordered file substring and a third coalesced query file substring that can be used to format output comparison data.
Claim 2
Independent Claim
192 words
A method of comparing a query file to one or more stored files, the method comprising: receiving a query file having a plurality of query file substrings; selecting a first query file substring from the plurality of query file substrings; preprocessing the first query file substring thereby making the substring more suitable for searching in the storage area; searching a storage area storing a plurality of ordered file substrings for the first query file substring; storing match data relating to a match between the first query file substring and a first ordered file substring; and joining the first ordered file substring and a second ordered file substring if the first ordered file substring and the second ordered file substring are in a particular sequence and joining the first query file substring and a second query file substring if the first query file substring and the second query file substring are in the same particular sequences wherein the second ordered file substring and the second query file substring match, thereby forming a third coalesced ordered file substring and a third coalesced query file substring that can be used to format output comparison data.
Claim 3
Dependent Claim
27 words
A method as recited in claim 1 further comprising preprocessing the first query file substring thereby making the substring more suitable for searching in the storage area.
Claim 4
Dependent Claim
50 words
A method as recited in claim 1 further comprising deriving an identifier corresponding to the first query substring using a predetermined function and using the identifier to perform searches in the storage area and identify matches between the plurality of query file substrings and the plurality of ordered file substrings.
Claim 5
Dependent Claim
45 words
A method as recited in claim 1 further comprising determining whether the query file can be integrated with one or more groups of stored files by comparing the query file with a stored file from each of the one or more groups of stored files.
Claim 6
Dependent Claim
45 words
A method as recited in claim 4 further comprising qualifying a query file for integration with one or more groups of stored files by examining the number of matches between the plurality of query file substrings and ordered file substrings from a particular stored file.
Claim 7
Dependent Claim
41 words
A method as recited in claim 1 wherein the match data includes a plurality of query file substring positions paired with a plurality of corresponding ordered file substring positions, the corresponding ordered file substrings arranged in segments corresponding to stored files.
Claim 8
Dependent Claim
29 words
A method as recited in claim 1 wherein joining the first ordered file substring and the second ordered file substring further comprises eliminating overlaps between two ordered file substrings.
Claim 9
Dependent Claim
59 words
A method as recited in claim 7 further comprising segmenting the two ordered file substrings into three sub-segments including a first sub-segment formed from a first of the two ordered file substrings, a second sub-segment formed from an overlap between the two ordered file substrings, and a third sub-segment formed from a second of the two ordered file substrings.
Claim 10
Dependent Claim
66 words
A method as recited in claim 1 further comprising identifying a longest length match between a plurality of third coalesced ordered file substrings and a plurality of third coalesced query file substrings and removing third coalesced indexed file substrings and third coalesced query file substrings corresponding to the longest length match, whereby duplicate query file substrings and ordered file substrings do not effect output comparison data.
Claim 11
Dependent Claim
37 words
A method as recited in claim 9 further comprising repeating the identification and removal of the longest length match between the plurality of third coalesced ordered file substrings and the plurality of third coalesced query file substrings.
Claim 12
Dependent Claim
60 words
A method as recited in claim 10 further comprising assigning the longest length match a unique name thereby transforming the plurality of query file substrings into a simplified query file string and the plurality of ordered file substrings into a simplified file string, wherein the simplified query file string and the simplified file string include a plurality of unique names.
Claim 13
Dependent Claim
40 words
A method as recited in claim 11 further comprising assigning an indicator to each one of the plurality of unique names for display as output comparison data associated with the query file and one or more of the stored files.
Claim 14
Independent Claim
203 words
A system for comparing a query file to one or more stored files, the system comprising: a file segmenter for creating a plurality of query file substrings from a query file; a substring preprocessor for preprocessing the first query file substring thereby making the substring more suitable for searching in the storage area: a storage searcher for searching a storage area storing a plurality of ordered file substrings for a first query file substring; a data storer for storing match data relating to a match between the first query file substring and a first ordered file substring; and a substring coalescer for joining the first ordered file substring and a second ordered file substring if the first ordered file substring and the second ordered file substring are in a particular sequence and for joining the first query file substring and a second query file substring if the first query file substring and the second query file substring are in the same particular sequence wherein the second ordered file substring and the second query file substring match, the substring coalescer thereby forming a third coalesced ordered file substring and a third coalesced query file substring that can be used to format output comparison data.
Claim 15
Independent Claim
203 words
A system for comparing a query file to one or more stored files, the system comprising: a file segmenter for creating a plurality of query file substrings from a query file; a substring preprocessor for preprocessing the first query file substring thereby making the substring more suitable for searching in the storage area: a storage searcher for searching a storage area storing a plurality of ordered file substrings for a first query file substring; a data storer for storing match data relating to a match between the first query file substring and a first ordered file substring; and a substring coalescer for joining the first ordered file substring and a second ordered file substring if the first ordered file substring and the second ordered file substring are in a particular sequence and for joining the first query file substring and a second query file substring if the first query file substring and the second query file substring are in the same particular sequence wherein the second ordered file substring and the second query file substring match, the substring coalescer thereby forming a third coalesced ordered file substring and a third coalesced query file substring that can be used to format output comparison data.
Claim 16
Dependent Claim
224 words
A computer readable medium containing programmed instructions for comparing a query file to one or more stored files, the programmed instructions comprising: a computer code for receiving a query file having a plurality of query file substrings; a computer code for selecting a first query file substring from the plurality of query file sub strings; a computer code for preprocessing the first query file substring thereby making the substring more suitable for searching in the storage area a computer code for searching a storage area storing a plurality of ordered file substrings for the first query file substring; a computer code for storing match data relating to a match between the first query file substring and a first ordered file substring; and a computer code for joining the first ordered file substring and a second ordered file substring if the first ordered file substring and the second ordered file substring are in a particular sequence and for joining the first query file substring and a second query file substring if the first query file substring and the second query file substring are in the same particular sequence wherein the second ordered file substring and the second query file substring match, thereby forming a third coalesced ordered file substring and a third coalesced query file substring that can be used to format output comparison data.
Claim 17
Dependent Claim
224 words
A computer readable medium containing programmed instructions for comparing a query file to one or more stored files, the programmed instructions comprising: a computer code for receiving a query file having a plurality of query file substrings; a computer code for selecting a first query file substring from the plurality of query file sub strings; a computer code for preprocessing the first query file substring thereby making the substring more suitable for searching in the storage area a computer code for searching a storage area storing a plurality of ordered file substrings for the first query file substring; a computer code for storing match data relating to a match between the first query file substring and a first ordered file substring; and a computer code for joining the first ordered file substring and a second ordered file substring if the first ordered file substring and the second ordered file substring are in a particular sequence and for joining the first query file substring and a second query file substring if the first query file substring and the second query file substring are in the same particular sequence wherein the second ordered file substring and the second query file substring match, thereby forming a third coalesced ordered file substring and a third coalesced query file substring that can be used to format output comparison data.
References Cited (Backward Citations)
US5202986A
Cited
US5274805A
Cited
US5410671A
Cited
US5317742A
Cited
US5281967A
Cited
US5511159A
Cited
US5953006A
Cited
US5627748A
Cited
US5929421A
Cited
US5893134A
Cited
US5819300A
Cited
US5926555A
Cited
US5566329A
Cited
US5704060A
Cited
US5825830A
Cited
US5956724A
Cited
US5832520A
Cited
US6055538A
Cited
US6079047A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-05-28 | 2004-11-27 | 2005-05-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-05-28 | 2008-11-27 | 2009-05-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-05-28 | 2012-11-27 | 2013-05-29 | $7700.00 | Window Closed / Lapsed |