Paralel ağ tarayıcıları için sayfa atama yöntemleri

ABSTRACTPAGE-TO-PROCESSOR ASSIGNMENT TECHNIQUESFOR PARALLEL CRAWLERSAta Tü rkuM.S. in Computer EngineeringSupervisor: Prof. Dr. Cevdet AykanatSeptember, 2004In less than a decade, the World Wide Web has evolved from a research projectto a cultural phenomena effective in almost every facet of our society. The increasein the popularity and usage of the Web enforced an increase in the efficiency ofinformation retrieval techniques used over the net. Crawling is among such tech-niques and is used by search engines, web portals, and web caches. A crawler is aprogram which downloads and stores web pages, generally to feed a search engineor a web repository. In order to be of use for its target applications, a crawlermust download huge amounts of data in a reasonable amount of time. Gener-ally, the high download rates required for efficient crawling cannot be achievedby single-processor systems. Thus, existing large-scale applications use multipleparallel processors to solve the crawling problem. Apart from the classical paral-lelization issues such as load balancing and minimization of the communicationoverhead, parallel crawling poses problems such as overlap avoidance and earlyretrieval of high quality pages. This thesis addresses parallelization of the crawl-ing task, and its major contribution is mainly on partitioning/page-to-processorassignment techniques applied in parallel crawlers. We propose two new page-to-processor assignment techniques based on graph and hypergraph partitioning,which respectively minimize the total communication volume and the number ofmessages, while balancing the storage load and page download requests of proces-sors. We implemented the proposed models, and our theoretic approaches havebeen supported with empirical findings. We also implemented an efficient parallelcrawler which uses the proposed models.Keywords: Parallel crawling, graph partitioning, hypergraph partitioning, pageassignment.iii