Patent US6711568B1 successfully refreshed from Google Patents.
US6711568B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for estimating coverage of web search engines
Assignee: R2 Solutions LLC
•
Filing: 2000-11-08
•
Granted: 2004-03-23
•
Expires: 2020-11-08
Abstract
Abstract A computerized method is used to estimate the relative coverage of Web search engines. Each search engine maintains an index of words of pages located at specific URL addresses in a network. The method generates a random query. The random query is a logical combination of words found in a subset of the pages. The random query is submitted to a first search engine. In response a set of URLs of pages matching the query are received. Each URL identifies a page indexed by the first search engine that satisfies the random query. A particular URL identifying a sample page is randomly selected. A strong query corresponding to the sample page is generated, and the strong query is submitted to a second search engine. Result information received in response to the strong query is compared to determine if the second search engine has indexed the sample page, or a page substantially similar to the sample page. This procedure is repeated to gather statistical data which is used to estimate the relative sizes and amount of overlap of search engines.
Inventors
- 👤 Krishna Asur Bharat
- 👤 Andrei Zary Broder
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 21:58
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/95; G06F16/951; G06F16/953; G06F16/9532; G06F16/9538; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934; Y10S707/99935; Y10S707/99936
Claims Analysis
Total Claims: 52
Claim 1
Independent Claim
216 words
A computerized method for comparing search engine indices and estimating coverage of at least one search engine, each search engine maintaining an index of words of pages located at specific addresses in a network, wherein the estimate of coverage indicates the relative sizes of the indices of the first and second search engine, and the relative amount of overlap between the first and second search engine, comprising: generating a random query, the random query being a logical combination of words found in a lexicon of words; submitting the random query to the first search engine; receiving a set of URLs in response to the random query; randomly selecting a particular URL identifying a sample page; generating a strong query for the sample page; submitting the strong query to a second search engine; comparing result information received in response to the strong query to determine if the second search engine has indexed the sample page; and estimating the relative sizes of the indices of the first and second search engines by dividing a fraction of a first set of pages sampled from the second search engine that are contained in the first search engine by a fraction of a second set of pages sampled from the first search engine that are contained in the second search engine.
Claim 2
Dependent Claim
216 words
A computerized method for comparing search engine indices and estimating coverage of at least one search engine, each search engine maintaining an index of words of pages located at specific addresses in a network, wherein the estimate of coverage indicates the relative sizes of the indices of the first and second search engine, and the relative amount of overlap between the first and second search engine, comprising: generating a random query, the random query being a logical combination of words found in a lexicon of words; submitting the random query to the first search engine; receiving a set of URLs in response to the random query; randomly selecting a particular URL identifying a sample page; generating a strong query for the sample page; submitting the strong query to a second search engine; comparing result information received in response to the strong query to determine if the second search engine has indexed the sample page; and estimating the relative sizes of the indices of the first and second search engines by dividing a fraction of a first set of pages sampled from the second search engine that are contained in the first search engine by a fraction of a second set of pages sampled from the first search engine that are contained in the second search engine.
Claim 3
Dependent Claim
46 words
The method of claim 1 wherein the relative amount of overlap of the indices of the first and second search engine is estimated by computing a fraction of a set of pages sampled from the second search engine that are combined in the first search engine.
Claim 4
Dependent Claim
19 words
The method of claim 1 wherein the content of the lexicon of words is expressed in a particular language.
Claim 5
Dependent Claim
20 words
The method of claim 1 wherein the content of the braining set of pages relates to a particular context domain.
Claim 6
Dependent Claim
35 words
The method of claim 1 wherein the lexicon of words is constructed from a training set of pages, and wherein the training set of pages represents pages of interest for which coverage is being estimated.
Claim 7
Dependent Claim
32 words
The method of claim 1 wherein the lexicon of words is constructed from a training set of pages, and the method further comprises determining the frequencies of unique words in the lexicon.
Claim 8
Dependent Claim
20 words
The method of claim 6 wherein the random query combines random words selected from the lexicon with a logical operator.
Claim 9
Dependent Claim
13 words
The method of claim 6 wherein the random query is a disjunctive query.
Claim 10
Dependent Claim
25 words
The method of claim 8 wherein the disjunctive query combines a set of words using OR operators, the set of words having a predetermined size.
Claim 11
Dependent Claim
18 words
The method of claim 9 wherein the words of the set have relative frequencies that are substantially similar.
Claim 12
Dependent Claim
22 words
The method of claim 6 wherein the random query is a conjunctive query combining a pair of words and an AND operator.
Claim 13
Dependent Claim
64 words
The method of claim 11 further including: sorting the words in the lexicon according to the frequencies of the words; and establishing an upper frequency threshold and a lower frequency threshold so that when words equidistant from the upper and lower thresholds are combined in the conjunctive query, the set of addresses is less than or equal to a predetermined maximum number of members.
Claim 14
Dependent Claim
24 words
The computer program product of claim 6 wherein the random query is a conjunctive query combining a pair of words and an AND operator.
Claim 15
Dependent Claim
69 words
The computer program product of claim 13 wherein the process further includes: sorting the words in the lexicon according to the frequencies of the words; and establishing an upper frequency threshold and a lower frequency threshold so that when words equidistant from the upper and lower thresholds are combined in the conjunctive query, the set of addresses is less than or equal to a predetermined maximum number of members.
Claim 16
Dependent Claim
45 words
The method of claim 1 wherein the network is the World Wide Web and further including: fetching the URL from the first search engine; fetching a corresponding page from the World Wide Web; and constructing the strong query to be representative of the sample page.
Claim 17
Dependent Claim
19 words
The method of claim 15 wherein the strong query is a disjunction of a first and second conjunctive query.
Claim 18
Dependent Claim
19 words
The method of claim 1 wherein the result information includes URLs of pages indexed by the second search engine.
Claim 19
Dependent Claim
25 words
The method of claim 17 wherein the URLs of the pages indexed and the particular address identifying the sample pages are normalized before the comparing.
Claim 20
Dependent Claim
30 words
The method of claim 17 wherein the result information being compared is the content of the sample page, and the content of the pages indexed by the second search engine.
Claim 21
Dependent Claim
12 words
The method of claim 17 wherein the result information includes host names.
Claim 22
Dependent Claim
15 words
The method of claim 1 wherein dynamic and impoverished pages are discarded before the comparing.
Claim 23
Dependent Claim
15 words
The method of claim 1 wherein privileged access is provided to the first search engine.
Claim 24
Dependent Claim
171 words
A computerized method for comparing search engine indices and estimating coverage of at least one search engine, each search engine maintaining an index of words of pages located at specific addresses in a network, comprising: generating a random query, the random query being a logical combination of words found in a lexicon of words; submitting the random query to the first search engine; receiving a set of URLs in response to the random query; randomly selecting a particular URL identifying a sample page; generating a strong query for the sample page; submitting the strong query to a second search engine; and comparing result information received in response to the strong query to determine if the second search engine has indexed the sample page; wherein ranking bias and query bias are compensated, the ranking bias being compensated by comparing result information for any page indexed by the second search engine that is responsive to the strong query, the query bias being compensated by probabilistically selecting the particular address identifying the sample page.
Claim 25
Dependent Claim
171 words
A computerized method for comparing search engine indices and estimating coverage of at least one search engine, each search engine maintaining an index of words of pages located at specific addresses in a network, comprising: generating a random query, the random query being a logical combination of words found in a lexicon of words; submitting the random query to the first search engine; receiving a set of URLs in response to the random query; randomly selecting a particular URL identifying a sample page; generating a strong query for the sample page; submitting the strong query to a second search engine; and comparing result information received in response to the strong query to determine if the second search engine has indexed the sample page; wherein ranking bias and query bias are compensated, the ranking bias being compensated by comparing result information for any page indexed by the second search engine that is responsive to the strong query, the query bias being compensated by probabilistically selecting the particular address identifying the sample page.
Claim 26
Dependent Claim
237 words
A computer program product readable by a computing system and encoding a computer program of instructions for executing a computer process for comparing search engine indices and estimating coverage of at least one search engine, each search engine maintaining an index of words of pages located at specific addresses in a network, wherein the estimate of coverage indicates the relative sizes of the indices of the first and second search engine, and the relative amount of overlap between the first and second search engine, said computer process comprising: generating a random query, the random query being a logical combination of words found in a lexicon of words; submitting the random query to the first search engine; receiving a set of URLs in response to the random query; randomly selecting a particular URL identifying a sample page; generating a strong query for the sample page; submitting the strong query to a second search engine; comparing result information received in response to the strong query to determine if the second search engine has indexed the sample page; and estimating the relative sizes of the indices of the first and second search engines by dividing a fraction of a first set of pages sampled from the second search engine that are contained in the first search engine by a fraction of a second set of pages sampled from the first search engine that are contained in the second search engine.
Claim 27
Dependent Claim
237 words
A computer program product readable by a computing system and encoding a computer program of instructions for executing a computer process for comparing search engine indices and estimating coverage of at least one search engine, each search engine maintaining an index of words of pages located at specific addresses in a network, wherein the estimate of coverage indicates the relative sizes of the indices of the first and second search engine, and the relative amount of overlap between the first and second search engine, said computer process comprising: generating a random query, the random query being a logical combination of words found in a lexicon of words; submitting the random query to the first search engine; receiving a set of URLs in response to the random query; randomly selecting a particular URL identifying a sample page; generating a strong query for the sample page; submitting the strong query to a second search engine; comparing result information received in response to the strong query to determine if the second search engine has indexed the sample page; and estimating the relative sizes of the indices of the first and second search engines by dividing a fraction of a first set of pages sampled from the second search engine that are contained in the first search engine by a fraction of a second set of pages sampled from the first search engine that are contained in the second search engine.
Claim 28
Dependent Claim
52 words
The computer program product of claim 24 wherein the relative amount of overlap of the indices of the first and second search engine is estimated by the computer process by computing a fraction of a set of pages sampled from the second search engine that are combined in the first search engine.
Claim 29
Dependent Claim
21 words
The computer program product of claim 24 wherein the content of the lexicon of words is expressed in a particular language.
Claim 30
Dependent Claim
22 words
The computer program product of claim 24 wherein the content of the braining set of pages relates to a particular context domain.
Claim 31
Dependent Claim
37 words
The computer program product of claim 24 wherein the lexicon of words is based on a training set of pages, and wherein the training set of pages represents pages of interest for which coverage is being estimated.
Claim 32
Dependent Claim
34 words
The computer program product of claim 24 wherein the lexicon of words is based on a training set of pages, and the process further comprises determining the frequencies of unique words in the lexicon.
Claim 33
Dependent Claim
22 words
The computer program product of claim 29 wherein the random query combines random words selected from the lexicon with a logical operator.
Claim 34
Dependent Claim
15 words
The computer program product of claim 29 wherein the random query is a disjunctive query.
Claim 35
Dependent Claim
27 words
The computer program product of claim 31 wherein the disjunctive query combines a set of words using OR operators, the set of words having a predetermined size.
Claim 36
Dependent Claim
20 words
The computer program product of claim 32 wherein the words of the set have relative frequencies that are substantially similar.
Claim 37
Dependent Claim
49 words
The computer program product of claim 24 wherein the network is the World Wide Web and the process further including: fetching the URL from the first search engine; fetching a corresponding page from the World Wide Web; and constructing the strong query to be representative of the sample page.
Claim 38
Dependent Claim
21 words
The computer program product of claim 34 wherein the strong query is a disjunction of a first and second conjunctive query.
Claim 39
Dependent Claim
21 words
The computer program product of claim 24 wherein the result information includes URLs of pages indexed by the second search engine.
Claim 40
Dependent Claim
27 words
The computer program product of claim 36 wherein the URLs of the pages indexed and the particular address identifying the sample pages are normalized before the comparing.
Claim 41
Dependent Claim
35 words
The computer program product of claim 36 wherein the result information being compared by the process is the content of the sample page, and the content of the pages indexed by the second search engine.
Claim 42
Dependent Claim
14 words
The computer program product of claim 36 wherein the result information includes host names.
Claim 43
Dependent Claim
18 words
The computer program product of claim 24 wherein the process discards dynamic and impoverished pages before the comparing.
Claim 44
Dependent Claim
20 words
The computer program product of claim 24 wherein privileged access is provided to the first search engine during the process.
Claim 45
Dependent Claim
193 words
A computer program product readable by a computing system and encoding a computer program of instructions for executing a computer process for comparing search engine indices and estimating coverage of at least one search engine, each search engine associated with an index of words of pages located at specific addresses in a network, said computer process comprising: generating a random query, the random query being a logical combination of words found in a lexicon of words; submitting the random query to the first search engine; receiving a set of URLs in response to the random query; randomly selecting a particular URL identifying a sample page; generating a strong query for the sample page; submitting the strong query to a second search engine; and comparing result information received in response to the strong query to determine if the second search engine has indexed the sample page; wherein ranking bias and query bias are compensated, the ranking bias being compensated by comparing result information for any page indexed by the second search engine that is responsive to the strong query, the query bias being compensated by probabilistically selecting the particular address identifying the sample page.
Claim 46
Dependent Claim
193 words
A computer program product readable by a computing system and encoding a computer program of instructions for executing a computer process for comparing search engine indices and estimating coverage of at least one search engine, each search engine associated with an index of words of pages located at specific addresses in a network, said computer process comprising: generating a random query, the random query being a logical combination of words found in a lexicon of words; submitting the random query to the first search engine; receiving a set of URLs in response to the random query; randomly selecting a particular URL identifying a sample page; generating a strong query for the sample page; submitting the strong query to a second search engine; and comparing result information received in response to the strong query to determine if the second search engine has indexed the sample page; wherein ranking bias and query bias are compensated, the ranking bias being compensated by comparing result information for any page indexed by the second search engine that is responsive to the strong query, the query bias being compensated by probabilistically selecting the particular address identifying the sample page.
Claim 47
Independent Claim
249 words
A system for comparing search engine indices and estimating coverage of at least one search engine, each search engine associated with an index of words of pages located at specific addresses in a network, wherein the estimate of coverage indicates the relative sizes of the indices of the first and second search engine, and the relative amount of overlap between the first and second search engine, comprising: a processor for generating a random query, the random query being a logical combination of words found in a lexicon of words; a communications device for submitting the random query to the first search engine; the communications device further for receiving a set of URLs in response to the random query; the processor further for randomly selecting a particular URL identifying a sample page; the processor further for generating a strong query for the sample page; the communications device further for submitting the strong query to a second search engine; the processor further for comparing result information received in response to the strong query to determine if the second search engine has indexed the sample page; and the processor further for estimating the relative sizes of the indices of the first and second search engines by dividing a fraction of a first set of pages sampled from the second search engine that are contained in the first search engine by a fraction of a second set of pages sampled from the first search engine that are contained in the second search engine.
Claim 48
Independent Claim
249 words
A system for comparing search engine indices and estimating coverage of at least one search engine, each search engine associated with an index of words of pages located at specific addresses in a network, wherein the estimate of coverage indicates the relative sizes of the indices of the first and second search engine, and the relative amount of overlap between the first and second search engine, comprising: a processor for generating a random query, the random query being a logical combination of words found in a lexicon of words; a communications device for submitting the random query to the first search engine; the communications device further for receiving a set of URLs in response to the random query; the processor further for randomly selecting a particular URL identifying a sample page; the processor further for generating a strong query for the sample page; the communications device further for submitting the strong query to a second search engine; the processor further for comparing result information received in response to the strong query to determine if the second search engine has indexed the sample page; and the processor further for estimating the relative sizes of the indices of the first and second search engines by dividing a fraction of a first set of pages sampled from the second search engine that are contained in the first search engine by a fraction of a second set of pages sampled from the first search engine that are contained in the second search engine.
Claim 49
Independent Claim
141 words
A method for comparing search engine indices, comprising: generating an initial query; submitting the initial query to a first search engine; receiving a set of URLs in response to the initial query; selecting a particular URL identifying a sample page; generating a strong query for the sample page; submitting the strong query to a second search engine; comparing result information received in response to the strong query to determine if the second search engine has indexed the sample page; and estimating the relative sizes of the indices of the first and second search engines by dividing a fraction of a first set of pages sampled from the second search engine that are contained in the first search engine by a fraction of a second set of pages sampled from the first search engine that are contained in the second search engine.
Claim 50
Independent Claim
141 words
A method for comparing search engine indices, comprising: generating an initial query; submitting the initial query to a first search engine; receiving a set of URLs in response to the initial query; selecting a particular URL identifying a sample page; generating a strong query for the sample page; submitting the strong query to a second search engine; comparing result information received in response to the strong query to determine if the second search engine has indexed the sample page; and estimating the relative sizes of the indices of the first and second search engines by dividing a fraction of a first set of pages sampled from the second search engine that are contained in the first search engine by a fraction of a second set of pages sampled from the first search engine that are contained in the second search engine.
Claim 51
Independent Claim
128 words
A method for comparing search engine indices, comprising: generating an initial query; submitting the initial query to a first search engine; receiving a set of URLs in response to the initial query; selecting a particular URL identifying a sample page; generating a strong query for the sample page; submitting the strong query to a second search engine; and comparing result information received in response to the strong query to determine if the second search engine has indexed the sample page; wherein ranking bias and query bias are compensated, the ranking bias being compensated by comparing result information for any page indexed by the second search engine that is responsive to the strong query, the query bias being compensated by probabilistically selecting the particular address identifying the sample page.
Claim 52
Independent Claim
128 words
A method for comparing search engine indices, comprising: generating an initial query; submitting the initial query to a first search engine; receiving a set of URLs in response to the initial query; selecting a particular URL identifying a sample page; generating a strong query for the sample page; submitting the strong query to a second search engine; and comparing result information received in response to the strong query to determine if the second search engine has indexed the sample page; wherein ranking bias and query bias are compensated, the ranking bias being compensated by comparing result information for any page indexed by the second search engine that is responsive to the strong query, the query bias being compensated by probabilistically selecting the particular address identifying the sample page.
References Cited (Backward Citations)
US5701469A
Cited
US5911139A
Cited
US5913215A
Cited
US5926812A
Cited
US5864863A
Cited
US5842206A
Cited
US5873080A
Cited
US5873079A
Cited
US6285999B1
Cited
US6539373B1
Cited
US5933822A
Cited
US6094657A
Cited
US5848410A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-03-23 | 2007-09-22 | 2008-03-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-03-23 | 2011-09-22 | 2012-03-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-03-23 | 2015-09-22 | 2016-03-23 | $7700.00 | Window Closed / Lapsed |