Back to results
US 8,266,134 B1Granted
Distributed crawling of hyperlinked documents
AssigneeGoogle Inc.
InventorsJeffrey A. Dean, Craig Silverstein, Benedict Gomes, Sanjay Ghemawat
Life of this patent
Estimating the term…
Abstract
Techniques for crawling hyperlinked documents are provided. Hyperlinked documents to be crawled are grouped by host and the host to be crawled next is selected according to a stall time of the host. The stall time can indicate the earliest time that the host should be crawled and the stall times can be a predetermined amount of time, vary by host and be adjusted according to actual retrieval times from the host.
Claims17
A computer-implemented method comprising:
- receiving, by one or more processors, a plurality of links to hyperlinked documents to be crawled;
- grouping, by one or more processors, the plurality of links to hyperlinked documents by host, each of the plurality of links being associated with one of a plurality of hosts;
- grouping, by one or more processors, hosts into buckets, by storing host identifiers, associated with the plurality of hosts, in the buckets, according to a number of links to hyperlinked documents to be crawled at each host;
- sorting, by one or more processors, the hosts in each bucket based on a stall time of each host, the stall time of each host indicating an earliest time that each host should be crawled;
- crawling, by one or more processors, a link to a first hyperlinked document from a host in a bucket based on a stall time associated with the host;
- determining, by one or more processors, a time to obtain the first hyperlinked document from the host;
- adjusting, by one or more processors, the stall time based on the determined time to obtain the first hyperlinked document from the host, a load factor associated with the host, and a current time;
- moving, by one or more processors, the host from the bucket to another bucket that includes hosts with fewer links to hyperlinked documents to be crawled;
- and
- crawling, by one or more processors, a link to a second hyperlinked document based on the adjusted stall time.
7 more elements
A system comprising:
- a plurality of link managers, at least partially implemented in hardware, to:
- receive links to hyperlinked documents to be crawled, and
- provide the links to the hyperlinked documents in response to requests;
- and
- a link server, at least partially implemented in hardware, to:
- send the requests for links to the hyperlinked documents to the plurality of link managers,
- receive the links to the hyperlinked documents from the plurality of link managers,
- group the links to the hyperlinked documents by host, each of the links to the hyperlinked documents being associated with one of a plurality of hosts,
- group the plurality of hosts into buckets, by storing host identifiers, associated with the plurality of hosts, in the buckets according to a number of links to hyperlinked documents to be crawled at each host,
- sort the hosts in each bucket based on a stall time of each associated host, the stall time of each host indicating an earliest time that each host should be crawled,
- select a host from one of the buckets to crawl next according to the stall time of the host, and
- crawl a hyperlinked document from the selected host using a link to the hyperlinked document.
9 more elements
A non-transitory computer-readable medium including instructions for execution by one or more processors, the instructions comprising:
- one or more instructions that, when executed by the one or more processors, cause that one or more processors to:
- receive a plurality of links to hyperlinked documents to be crawled;
- group the plurality of links to hyperlinked documents by host, each of the plurality of links being associated with one of a plurality of hosts;
- group hosts into buckets, by storing host identifiers, associated with the plurality of hosts, in the buckets, according to a number of links to hyperlinked documents to be crawled at each host;
- sort the hosts in each bucket based on a stall time of each host, the stall time of each host indicating an earliest time that each host should be crawled;
- crawl a link to a first hyperlinked document from a host in a bucket based on a stall time associated with the host;
- determine a time to obtain the first hyperlinked document from the host;
- adjust the stall time based on the determined time to obtain the first hyperlinked document from the host, a load factor associated with the host, and a current time;
- move the host from the bucket to another bucket that includes hosts with fewer links to hyperlinked documents to be crawled;
- and
- crawl a link to a second hyperlinked document based on the adjusted stall time.
8 more elements
Dependencies are inferred from the claim text.