【正文】 eb a process known as crawling or SPIDERing. The basic algorithm is （a） Fetch a page （b） Parse it to extract all linked URLs （c） For all the URLs not seen before repeat （a）–（c） Crawling typically starts from a set of seed URLs made up of URLs obtained by other means as described above and/or made up of URLs collected during previous crawls. Sometimes crawls are started from a single well connected page or a directory such as but in this case a relatively large portion of the web estimated at over 20% is never reached. See[ 9] for a discussion of the graph structure of the web that leads to this phenomenon. If we view web pages as nodes in a graph and hyperlinks as directed edges among these nodes then crawling bees a process known in mathematical circles as graph traversal. Various strategies for graph traversal differ in their choice of which node among the nodes not yet explored to explore next. Two standard strategies for graph traversal are Depth First Search DFS and Breadth First Search BFS – they are easy to implement and taught in many introductory algorithms classes. See for instance [34]. However crawling the web is not a trivial programming exercise but a serious algorithmic and system design challenge because of the following two factors. 1. The web is very large. Currently Google [20] claims to have indexed over 3 billion pages. Various studies 3 27 28 have indicated that historically the web has doubled every 912 months. 2. Web pages are changing rapidly. If “change” means “any change” then about 40% of all web pages change weekly [12]. Even if we consider only pages that change by a third or more about 7% of all web pages change weekly [17]. These two factors imply that to obtain a reasonably fresh and 679 plete snapshot of the web a search engine must crawl at least 100 million pages per step a must be executed about 1000 times per second and them ember ship test in step c must be done well over ten thousand times per second against a set of URLs that is too large to store in main memory. In addition crawlers typically use a distributed architecture to crawl more pages in parallel which further plicates the membership test: it is possible that the membership question can only be answered by a peer node not locally. A crucial way to speed up the membership test is to cache a dynamic subset of the “seen” URLs in main memory. The main goal of this paper is to investigate in depth several URL caching techniques for web crawling. We examined four practical techniques: random replacement static cache LRU and CLOCK and pared them against two theoretical limits: clairvoyant caching and infinite cache when run again stat race of a web crawl that issued over one billion HTTP requests. We found that simple caching techniques are extremely effective even at relatively small cache sizes such as 50,000 entries and show how these caches can be implemented very efficiently. The paper is organized as follows: Section 2 discusses the various crawling solutions proposed in the literature and how caching fits in their model. Section 3 presents an introduction to caching techniques and describes several theoretical and practical algorithms for caching. We implemented these algorithms under the experimental setup described in Section 4. The results of our simulations are depicted and discussed in Section 5 and our remendations for practical algorithms and data structures for URL caching are presented in Section 6. Section 7 contains our conclusions and directions for further research.2. CRAWLING Web crawlers are almost as old as the web itself and numerous crawling systems have been described in the literature. In this section we present a brief survey of these crawlers in historical order and then discuss why most of these crawlers could benefit from URL caching. The crawler used by the Internet Archive 10 employs multiple crawling processes each of which performs an exhaustive crawl of 64 hosts at a time. The crawling processes save nonlocal URLs to disk at the end of a crawl a batch job adds these URLs to the perhost seed sets of the next crawl. The original Google crawler described in[ 7] implements the different crawler ponents as different processes. A single URL server process maintains the set of URLs to download crawling processes fetch pages indexing processes extract words and links and URL resolver processes convert relative into absolute URLs which are then fed to the URL Server. The various processes municate via the file system. For the experiments described in this paper we used the Mercator web crawler[22 ,29]. Mercator uses a set of independent municating web crawler crawler process is responsible for a subset of all web servers the assignment of URLs to crawler processes is based on a hash of the URL’s host ponent. A crawler that discovers an URL for which it is not responsible sends this URL via TCP to the crawler that is responsible for it batching URLs together to minimize TCP describe Mercator in more detail in Section 4. Cho and GarciaMolina’s crawler 13 is similar to Mercator. The system is posed of multiple independent municating web crawler processes called“Cprocs”. Cho and GarciaMolina consider different schemes for partitioning the URL space including URLbased assigning an URL to a Cproc based on a hash of the entire URL sitebased assigning an URL to a Cproc based on a hash of the URL’s host part and hierarchical (assigning an URL to a Cproc based on some property of the URL such as its toplevel domain). The Web Fountain crawler[16] is also posed of a set of independent municating crawling processes the “ants”. An ant that discovers an URL for which it is not responsible sends this URL to a dedicated process the “controller”which forwards the URL to the appropriate ant. Ubi Crawler (formerly known as Trovatore) [4,5] is again posed of multiple independent municating web crawler processes. It also