Efficient partitioning strategies for distributed Web crawling

José Exposto**, Joaquim Macedo*, António Pina*, José Rufino**, Albano Alves**

Universidade do Minho*
Departamento de Informática
4710-057 Braga, Portugal

Tel.: +351 253 604430
Fax.: +351 253 604471
E-mail: {macedo,pina} (at) di.uminho.pt

    Escola Superior de Tecnologia e Gestão**
Departamento de Informática e Comunicações
5300 Bragança, Portugal

Tel.: +351 273 313050
Fax.: +351 273 313051
E-mail: {exp,rufino,albano} (at) ipb.pt


This paper presents a multi-objective approach to Web space partitioning, aimed to improve distributed crawling efficiency. The investigation is supported by the construction of two different weighted graphs. The first is used to model the topological communication infrastructure between crawlers and Web servers and the second is used to represent the amount of link connections between servers’ pages. The values of the graph edges represent, respectively, computed RTTs and pages links between nodes. The two graphs are further combined, using a multi-objective partitioning algorithm, to support Web space partitioning and load allocation for an adaptable number of geographical distributed crawlers. Partitioning strategies were evaluated by varying the number of partitions (crawlers) to obtain merit figures for: i) download time, ii) exchange time and iii) relocation time. Evaluation has showed that our partitioning schemes outperform traditional hostname hash based counterparts in all evaluated metric, achieving on average 18% reduction for download time, 78% reduction for exchange time and 46% reduction for relocation time.

21st International Conference on Information Networking (ICOIN 2007), Estoril, Portugal, Jan 23-25, 2007