Bilkent University
Department of Computer Engineering

---

S E M I N A R

 

Page-to-Processor Assignment Techniques for Parallel Crawlers

Ata Türk

Master Thesis Presentation

Supervisor: Prof. Dr. Cevdet Aykanat

In less than a decade, the World Wide Web has evolved from a research project to a cultural phenomena effective in almost every facet of our society. The increase in the popularity and usage of the Web enforced an increase in the efficiency of information retrieval techniques used over the net. Crawling is among such techniques and is used by search engines, web portals, and web caches. A crawler is a program which downloads and stores web pages, generally to feed a search engine or a web repository. In order to be of use for its target applications, a crawler must download huge amounts of data in a reasonable amount of time. Generally, the high download rates required for efficient crawling cannot be achieved by single processor systems. Thus, existing large-scale applications use multiple parallel processors to address the crawling problem. Apart from the classical parallelization issues such as load balancing and minimization of the communication volume/number, parallel crawling poses problems such as overlap avoidance and early retrieval of high quality pages. This thesis addresses parallelization of the crawling task and its major contribution is mainly on partitioning/page-to-processor assignment techniques applied in parallel crawlers. We propose two new page-to-processor assignment techniques based on graph and hypergraph partitioning, which minimize the total communication volume and the number of communication messages, while balancing the storage load and page download requests of processors. We implemented the proposed models, and our theoretic approaches have been supported with empirical findings. We also implemented an efficient parallel crawler using the proposed models.

DATE: September 10, 2004, Friday @ 14:00
PLACE: EA-502