# US 7,610,267 B2 · Unsupervised, automated web host dynamicity detection, dead link detection and prerequisite page discovery for search indexed web pages

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

- Number: US 7,610,267 B2
- Document ID: US7610267B2
- Status: Granted
- Kind: B2
- Application number: 11/203,832
- Filed: 2005-08-13
- Published: 2006-12-28
- Granted: 2009-10-27
- Earliest claimed: 2005-06-28
- Assignees: Yahoo! Inc.
- Inventors: Parashuram Kulkarni; Thejas Madhavan Nair; Binu Raj
- Web page: https://patentgrep.com/patent/US7610267B2

## CPC

- G06F 16/951: Indexing; Web crawling techniques
- G06F 16/953: Querying, e.g. by the use of web search engines
- G06F 16/958: Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking
- Y10S 707/99932: Access augmentation or optimizing
- Y10S 707/99933: Query processing, i.e. searching
- 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

Automated crawling of page links associated with a site domain that was previously crawled involves computing the dynamicity of a site based on totals of continuous dead links, live links and/or prerequisite pages encountered while crawling page links corresponding to the site. The degree to which links are crawled is optimized based on the dynamicity of the site. Some pages require that another particular page (i.e., a prerequisite page) is retrieved from the host prior to retrieving a given page, e.g., so that the prerequisite page can set a cookie. Prerequisite pages are determined based on stored information about pages that were retrieved, during a previous crawl, prior to retrieving a page. Prerequisite pages are identified to a search system so that when a user clicks on the URL for the page, the request is redirected to the prerequisite page to set the cookie appropriately.

## Claims

### Claim 1

A computer-implemented method comprising:
retrieving, from a site host, pages associated with the site, wherein the pages contain content;
determining how dynamic the content of the site is, based on the degree to which the content of the retrieved pages changed since a previous crawl of the site;
if the content of the site is determined dynamic, in relation to a corresponding threshold, then continuing retrieving, from the site host, pages associated with the site; and
if the content of the site is determined not dynamic, in relation to the corresponding threshold, then not retrieving, from the site host, a subset of pages associated with the domain;
wherein determining how dynamic the content of the site is comprises maintaining a count of the number of continuous pages for which a same prerequisite page must be retrieved to retrieve the continuous pages;
wherein retrieving a first page of the continuous pages without first retrieving the same prerequisite page causes a link to the first page to appear as a dead link but retrieving the first page after retrieving the same prerequisite page causes the link to the first page to appear as an alive link;
wherein retrieving the same prerequisite page causes information required for retrieving the first page to be retrieved from the site host;
wherein the method is performed by one or more computing devices comprising one or more processors.

### Claim 2 (depends on 1)

The method of claim 1,
wherein determining how dynamic the content of the site is comprises maintaining a count of the number of continuous dead links encountered; and
wherein not retrieving a subset of pages comprises indicating that each link corresponding to a page from the subset of pages is a dead link, without actually retrieving the page from the site host.

### Claim 3 (depends on 1)

The method of claim 1,
wherein determining how dynamic the content of the site is comprises maintaining a count of the number of continuous alive links encountered; and
wherein not retrieving a subset of pages comprises indicating that each link corresponding to a page from the subset of pages is an alive link, without actually retrieving the page from the site host.

### Claim 4 (depends on 1)

The method of claim 1,
wherein not retrieving a subset of pages comprises indicating that each page from the subset of pages requires the same prerequisite page to be retrieved to retrieve the page, without actually retrieving the page from the site host.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
determining whether a link to a page is dead or alive by
retrieving, from crawler storage, indexable words that were found in the page corresponding to the link during a previous crawl of the page;
retrieving the current version of the page;
determining how many of the indexable words match words in the current version of the page; and
if a ratio of matched words in the current version of the page over the number of indexable words exceeds a certain value, then mark the link corresponding to the page as an alive link, else mark the link corresponding to the page as a dead link.

### Claim 6 (depends on 5)

The method of claim 5, wherein retrieving the current version of the page includes:
retrieving, from crawler storage, information that indicates whether retrieving the page requires use of an HTTP POST method;
if the HTTP POST method is required, then
retrieving, from crawler storage, post data corresponding to the page which was used to retrieve the page during a previous crawl; and
retrieving the page by transmitting the post data via an HTTP POST request.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
in response to determining that a link to a page is dead,
retrieving, from crawler storage, information that indicates whether or not retrieving the page requires setting request information by retrieving a prerequisite page, wherein the information identifies one or more ancestor pages that were retrieved prior to retrieving the page during a previous crawl and the order in which the one or more ancestor pages were retrieved;
if the page requires setting request information by retrieving a prerequisite page, then
(a) retrieving a first ancestor page, wherein the first ancestor page is the ancestor page that was retrieved immediately prior to retrieving the page during the previous crawl;
(b) after performing step (a), retrieving the page;
(c) determining whether the page is dead or alive;
(d) if the page is alive, then determining that the first ancestor page is a prerequisite page for the page; and
(e) if the page is dead, then retrieving a second ancestor page, wherein the second ancestor page is the ancestor page that was retrieved immediately prior to retrieving the first ancestor page during the previous crawl, and repeating steps (b), (c) and (d) for the second ancestor page and, if necessary, repeating step (e) for the next ancestor page in the order.

### Claim 8 (depends on 7)

The method of claim 7, further comprising:
storing, in a search system, an identifier of the prerequisite page for the page; and
in response to a user request for the page, wherein the request is made by using a link to the page from search results from the search system,
directing a request to the prerequisite page based on the stored identifier of the prerequisite page; and
then directing a request to the page.

### Claim 9 (depends on 7)

The method of claim 7, further comprising:
determining whether a link to a page is dead or alive by
retrieving, from crawler storage, indexable words that were found in the page corresponding to the link during a previous crawl of the page;
retrieving the current version of the page;
determining how many of the indexable words match words in the current version of the page; and
if a ratio of matched words in the current version of the page over the number of indexable words exceeds a certain value, then mark the link corresponding to the page as an alive link, else mark the link corresponding to the page as a dead link.

### Claim 10 (depends on 1)

The method of claim 1, wherein the step of retrieving pages comprises concurrently retrieving pages associated with multiple site domains, and wherein retrieving pages for each site domain is performed by a single respective processing thread that does not retrieve pages for any other site domain.

### Claim 11

A volatile or non-volatile machine-readable medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform:
retrieving, from a site host, pages associated with the site, wherein the pages contain content;
determining how dynamic the content of the site is, based on the degree to which the content of the retrieved pages changed since a previous crawl of the site;
if the content of the site is determined dynamic, in relation to a corresponding threshold, then continuing retrieving, from the site host, pages associated with the site; and
if the content of the site is determined not dynamic, in relation to the corresponding threshold, then not retrieving, from the site host, a subset of pages associated with the domain;
wherein determining how dynamic the content of the site is comprises maintaining a count of the number of continuous pages for which a same particular prerequisite page must be retrieved to retrieve the continuous pages;
wherein retrieving a first page of the continuous pages without first retrieving the same prerequisite page causes a link to the first page to appear as a dead link but retrieving the first page after retrieving the same prerequisite page causes the link to the first page to appear as an alive link;
wherein retrieving the same prerequisite page causes information required for retrieving the first page to be retrieved from the site host;
wherein the method is performed by one or more computing devices comprising one or more processors.

### Claim 12 (depends on 11)

A volatile or non-volatile machine-readable medium storing one or more sequences of instructions of claim 11 which, when executed by one or more processors, causes the one or more processors to further perform:
wherein determining how dynamic the content of the site is comprises maintaining a count of the number of continuous dead links encountered; and
wherein not retrieving a subset of pages comprises indicating that each link corresponding to a page from the subset of pages is a dead link, without actually retrieving the page from the site host.

### Claim 13 (depends on 11)

A volatile or non-volatile machine-readable medium storing one or more sequences of instructions of claim 11 which, when executed by one or more processors, causes the one or more processors to further perform:
wherein determining how dynamic the content of the site is comprises maintaining a count of the number of continuous alive links encountered; and
wherein not retrieving a subset of pages comprises indicating that each link corresponding to a page from the subset of pages is an alive link, without actually retrieving the page from the site host.

### Claim 14 (depends on 11)

A volatile or non-volatile machine-readable medium storing one or more sequences of instructions of claim 11 which, when executed by one or more processors, causes the one or more processors to further perform:
wherein not retrieving a subset of pages comprises indicating that each page from the subset of pages requires the same prerequisite page to be retrieved to retrieve the page, without actually retrieving the page from the site host.

### Claim 15 (depends on 11)

A volatile or non-volatile machine-readable medium storing one or more sequences of instructions of claim 11 which, when executed by one or more processors, causes the one or more processors to further perform:
determining whether a link to a page is dead or alive by retrieving, from crawler storage, indexable words that were found in the page corresponding to the link during a previous crawl of the page;
retrieving the current version of the page;
determining how many of the indexable words match words in the current version of the page; and
if a ratio of matched words in the current version of the page over the number of indexable words exceeds a certain value, then mark the link corresponding to the page as an alive link, else mark the link corresponding to the page as a dead link.

### Claim 16 (depends on 15)

A volatile or non-volatile machine-readable medium storing one or more sequences of instructions of claim 15 which, when executed by one or more processors, causes the one or more processors to further perform:
retrieving, from crawler storage, information that indicates whether retrieving the page requires use of an HTTP POST method;
if the HTTP POST method is required, then
retrieving, from crawler storage, post data corresponding to the page which was used to retrieve the page during a previous crawl; and
retrieving the page by transmitting the post data via an HTTP POST request.

### Claim 17 (depends on 11)

A volatile or non-volatile machine-readable medium storing one or more sequences of instructions of claim 11 which, when executed by one or more processors, causes the one or more processors to further perform:
in response to determining that a link to a page is dead, retrieving, from crawler storage, information that indicates whether or not retrieving the page requires setting request information by retrieving a prerequisite page, wherein the information identifies one or more ancestor pages that were retrieved prior to retrieving the page during a previous crawl and the order in which the one or more ancestor pages were retrieved;
if the page requires setting request information by retrieving a prerequisite page, then
(a) retrieving a first ancestor page, wherein the first ancestor page is the ancestor page that was retrieved immediately prior to retrieving the page during the previous crawl;
(b) after performing step (a), retrieving the page;
(c) determining whether the page is dead or alive;
(d) if the page is alive, then determining that the first ancestor page is a prerequisite page for the page; and
(e) if the page is dead, then retrieving a second ancestor page, wherein the second ancestor page is the ancestor page that was retrieved immediately prior to retrieving the first ancestor page during the previous crawl, and repeating steps (b), (c) and (d) for the second ancestor page and, if necessary, repeating step (e) for the next ancestor page in the order.

### Claim 18 (depends on 17)

A volatile or non-volatile machine-readable medium storing one or more sequences of instructions of claim 17 which, when executed by one or more processors, causes the one or more processors to further perform:
storing, in a search system, an identifier of the prerequisite page for the page; and in response to a user request for the page, wherein the request is made by using a link to the page from search results from the search system, directing a request to the prerequisite page based on the stored identifier of the prerequisite page; and
then directing a request to the page.

### Claim 19 (depends on 17)

A volatile or non-volatile machine-readable medium storing one or more sequences of instructions of claim 17 which, when executed by one or more processors, causes the one or more processors to further perform:
determining whether a link to a page is dead or alive by retrieving, from crawler storage, indexable words that were found in the page corresponding to the link during a previous crawl of the page;
retrieving the current version of the page;
determining how many of the indexable words match words in the current version of the page; and
if a ratio of matched words in the current version of the page over the number of indexable words exceeds a certain value, then mark the link corresponding to the page as an alive link, else mark the link corresponding to the page as a dead link.

### Claim 20

A computer-implemented method for determining a prerequisite page for a page while checking, in an automated manner, page links associated with a site domain that was previously crawled, the method comprising:
retrieving, from crawler storage, information that indicates whether or not retrieving the page requires setting request information by retrieving a prerequisite page, wherein the information identifies one or more ancestor pages that were retrieved prior to retrieving the page during a previous crawl and the order in which the one or more ancestor pages were retrieved, and wherein retrieving the prerequisite page causes information required for retrieving the page to be retrieved;
if the page requires setting request information by retrieving a prerequisite page, then
(a) retrieving a first ancestor page, wherein the first ancestor page is the ancestor page that was retrieved immediately prior to retrieving the page during the previous crawl;
(b) after performing step (a), retrieving the page;
(c) determining whether the page is dead or alive;
(d) if the page is alive, then determining that the first ancestor page is a prerequisite page for the page; and
(e) if the page is dead, then retrieving a second ancestor page, wherein the second ancestor page is the ancestor page that was retrieved immediately prior to retrieving the first ancestor page during the previous crawl, and repeating steps (b), (c) and (d) for the second ancestor page and, if necessary, repeating step (e) for the next ancestor page in the order;
wherein the method is performed by one or more computing devices comprising one or more processors.

### Claim 21 (depends on 20)

The method of claim 20, further comprising:
storing, in a search system, an identifier of the prerequisite page for the page; and
in response to a user request for the page, wherein the request is made by using a link to the page from search results from the search system,
directing a request to the prerequisite page based on the stored identifier of the prerequisite page.

### Claim 22 (depends on 21)

The method of claim 21, further comprising:
after directing the request to the prerequisite page, directing a request to the page.

### Claim 23 (depends on 22)

A volatile or non-volatile machine-readable medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 22.

### Claim 24 (depends on 21)

A volatile or non-volatile machine-readable medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 21.

### Claim 25 (depends on 20)

A volatile or non-volatile machine-readable medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 20.

### Claim 26

A computer-implemented method comprising:
retrieving, from a site host, pages associated with the site, wherein the pages contain content;
determining how dynamic the content of the site is, based on a count of the number of continuous pages for which a same prerequisite page must be retrieved to retrieve the continuous pages, wherein the count is reset upon retrieval of a different prerequisite page;
if the content of the site is determined dynamic, in relation to a corresponding threshold, then continuing retrieving, from the site host, pages associated with the site; and
if the content of the site is determined not dynamic, in relation to the corresponding threshold, then not retrieving, from the site host, a subset of pages associated with the domain;
wherein retrieving a first page of the continuous pages without first retrieving the same prerequisite page causes a link to the first page to appear as a dead link but retrieving the first page after retrieving the same prerequisite page causes the link to the first page to appear as an alive link;
wherein retrieving the same prerequisite page causes information required for retrieving the first page to be retrieved from the site host;
wherein the method is performed by one or more computing devices comprising one or more processors.