US6757675B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for indexing document content and content comparison with World Wide Web search service
Assignee: University of California, San Diego
•
Filing: 2003-02-12
•
Granted: 2004-06-29
•
Expires: 2023-02-12
Abstract
Abstract Methods and related systems for indexing the contents of documents for comparison with the contents of other documents to identify matching content. A method for comparing the contents of a query document to the content on the World Wide Web is set forth. The contents of a query document are indexed and compared to content from the World Wide Web which is continuously retrieved and indexed. The method for indexing may comprise selecting substrings from the document, hashing the substrings to generate a plurality of hash values having a known range of values, selecting certain hash values to save from the generated hash values, and sorting the saved hash values. Methods for selecting certain hash values to save are set forth.
Inventors
- 👤 Alex Aiken
- 👤 Saul Schleimer
- 👤 Joel Auslander
- 👤 Daniel Wilkerson
- 👤 Anthony Tomasic
- 👤 Steve Fink
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 21:37
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/95; G06F16/951; G06F16/30; G06F16/31; G06F16/316; G06F16/325; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
117 words
A method for comparing the contents of a query document to the content on the World Wide Web, the method comprising: (a) indexing the contents of a query document including; selecting substrings from a query document; hashing said substrings to generate a plurality of hash values having a known range of values; selecting hash values to save from said plurality of hash values having a known range of values including; dividing the plurality of hash values into a plurality of overlapping windows of hash values; applying a fitness criterion to the hash values in each window of said overlapping windows to select a fit hash for each window; and saving said selected fit hash for each window.
Claim 2
Independent Claim
117 words
A method for comparing the contents of a query document to the content on the World Wide Web, the method comprising: (a) indexing the contents of a query document including; selecting substrings from a query document; hashing said substrings to generate a plurality of hash values having a known range of values; selecting hash values to save from said plurality of hash values having a known range of values including; dividing the plurality of hash values into a plurality of overlapping windows of hash values; applying a fitness criterion to the hash values in each window of said overlapping windows to select a fit hash for each window; and saving said selected fit hash for each window.
Claim 3
Dependent Claim
43 words
The method of claim 1 including removing at least one of said selected fit hash for each window if the at least one of said selected fit hash that is removed is a duplicate occurrence of any fit hash previously selected for saving.
Claim 4
Dependent Claim
51 words
The method of claim 1 including: (b) retrieving content from the World Wide Web; (c) indexing said content from the World Wide Web; (d) comparing said World Wide Web index to said query document index; and (e) continuously repeating steps (b) through (d) for different content from the World Wide Web.
Claim 5
Dependent Claim
19 words
The method of claim 3 wherein indexing the contents of a query document includes sorting said selected hash values.
Claim 6
Dependent Claim
134 words
The method of claim 4 , wherein said step of sorting said selected hash values having a known range of values comprises: partitioning said plurality of hash values into a plurality of buckets, each bucket of said plurality of buckets containing a different subset of said known range of values; and sorting for each subset of said known range of values said hash values within all buckets containing the same subset of said known range of values by value using a radix sort. writing to a single file on a storage medium the hash values sorted by value for each subset of said known range of values; and concatenating the hash values sorted by value for each subset of said known range of values to form one list of hash values sorted by value.
Claim 7
Dependent Claim
71 words
The method of claim 4 , wherein said step of comparing said World Wide Web index to said query document index comprises: creating a memory structure which summarizes the selected hash values saved from a query document; and querying said memory structure to determine whether each selected hash value saved from the contents of the World Wide Web is not present in the selected hash values saved from a query document.
Claim 8
Dependent Claim
14 words
The method of claim 6 , wherein said memory structure is a signature file.
Claim 9
Independent Claim
91 words
The method of 7 , wherein said step of creating a signature file which summarizes the selected hash values saved from a query document comprises: creating a bit array in memory; initializing all bit positions in said bit array to a prescribed logical value; identifying bit positions in said bit array by applying a series of hash functions to each hash value in the selected hash values from the query document; and setting said identified bit positions in said bit array to the opposite value of said previously prescribed logical value.
Claim 10
Independent Claim
91 words
The method of 7 , wherein said step of creating a signature file which summarizes the selected hash values saved from a query document comprises: creating a bit array in memory; initializing all bit positions in said bit array to a prescribed logical value; identifying bit positions in said bit array by applying a series of hash functions to each hash value in the selected hash values from the query document; and setting said identified bit positions in said bit array to the opposite value of said previously prescribed logical value.
Claim 11
Dependent Claim
114 words
The method of claim 8 , wherein said step of querying said memory structure to determine whether each selected hash value saved from the contents of the World Wide Web is not present on said selected hash values from the query document comprises: identifying query bit positions in said bit array to query by applying said series of hash functions to each selected hash value saved from the contents of the World Wide Web; and determining whether each selected hash value saved from the contents of the World Wide Web is not in the selected hash values from the query document by the value of said identified query bit positions in said bit array.
Claim 12
Dependent Claim
36 words
The method of claim 4 , wherein said step of retrieving content from the World Wide Web comprises: receiving a set of URLs identified by a user; and retrieving the content from said set of URLs.
Claim 13
Dependent Claim
23 words
The method of claim 4 , wherein said step of retrieving content from the World Wide Web comprises using a web crawler algorithm.
Claim 14
Dependent Claim
30 words
The method of claim 4 , wherein said step of retrieving content from the World Wide Web further comprises identifying whether the retrieved content has been modified since previously retrieved.
Claim 15
Dependent Claim
29 words
The method of claim 12 , wherein said step of identifying whether the retrieved content has been modified since previously retrieved comprises calculating a checksum for each retrieved page.
Claim 16
Independent Claim
179 words
A method for comparing the contents of a query document to the content on the World Wide Web, the method comprising: (a) indexing the contents of a plurality of URLs from the World Wide Web including; selecting substrings from the contents of a plurality of URLs from the World Wide Web; hashing said substrings to generate a plurality of hash values having a known range of values; selecting hash values to save from said plurality of hash values having a known range of values including; dividing the plurality of hash values into a plurality of overlapping windows of hash values; applying a fitness criterion to the hash values in each window of said overlapping windows to select a fit hash for each window; and saving said selected fit hash for each window; and (b) storing said index of contents of a plurality of URLs from the World Wide Web on a plurality of servers; (c) indexing the contents of a query document; and (d) comparing said query document index to said index of contents of the World Wide Web.
Claim 17
Independent Claim
179 words
A method for comparing the contents of a query document to the content on the World Wide Web, the method comprising: (a) indexing the contents of a plurality of URLs from the World Wide Web including; selecting substrings from the contents of a plurality of URLs from the World Wide Web; hashing said substrings to generate a plurality of hash values having a known range of values; selecting hash values to save from said plurality of hash values having a known range of values including; dividing the plurality of hash values into a plurality of overlapping windows of hash values; applying a fitness criterion to the hash values in each window of said overlapping windows to select a fit hash for each window; and saving said selected fit hash for each window; and (b) storing said index of contents of a plurality of URLs from the World Wide Web on a plurality of servers; (c) indexing the contents of a query document; and (d) comparing said query document index to said index of contents of the World Wide Web.
Claim 18
Dependent Claim
43 words
The method of claim 14 including removing at least one of said selected fit hash for each window if the at least one of said selected fit hash that is removed is a duplicate occurrence of any fit hash previously selected for saving.
Claim 19
Dependent Claim
20 words
The method of claim 14 wherein indexing the contents of a plurality of URLs includes sorting said selected hash values.
Claim 20
Dependent Claim
134 words
The method of claim 16 , wherein said step of sorting said selected hash values having a known range of values comprises: partitioning said plurality of hash values into a plurality of buckets, each bucket of said plurality of buckets containing a different subset of said known range of values; and sorting for each subset of said known range of values said hash values within all buckets containing the same subset of said known range of values by value using a radix sort. writing to a single file on a storage medium the hash values sorted by value for each subset of said known range of values; and concatenating the hash values sorted by value for each subset of said known range of values to form one list of hash values sorted by value.
Claim 21
Dependent Claim
80 words
The method of claim 14 , wherein said step of comparing said query document index to said index of contents of the World Wide Web comprises: creating a memory structure which summarizes the selected hash values saved from the contents of a plurality of URLs; and querying said memory structure to determine whether each selected hash value from the contents of a query document not present in the selected hash values saved from the contents of a plurality of URLs.
Claim 22
Dependent Claim
14 words
The method of claim 18 , wherein said memory structure is a signature file.
Claim 23
Dependent Claim
100 words
The method of claim 19 , wherein said step of creating a signature file which summarizes the selected hash values from the contents of a plurality of URLs comprises: creating a bit array in memory; initializing all bit positions in said bit array to a prescribed logical value; identifying bit positions in said bit array by applying a series of hash functions to each hash value in the selected hash values saved from the contents of a plurality of URLs; and setting said identified bit positions in said bit array to the opposite value of said previously prescribed logical value.
Claim 24
Dependent Claim
99 words
The method of claim 20 , wherein said step of querying said memory structure to determine whether each selected hash value from a query document is not present on said selected hash values from the contents of a plurality of URLs comprises: identifying query bit positions in said bit array by applying said series of hash functions to each selected hash value saved from a query document; and determining whether each selected hash value saved from a query document is not in the selected hash values by the value of said identified query bit positions in said bit array.
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) | 2007-06-29 | 2007-12-29 | 2008-06-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-06-29 | 2011-12-29 | 2012-06-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-06-29 | 2015-12-29 | 2016-06-29 | $7700.00 | Window Closed / Lapsed |