Efficient Parallel Block-Max WAND Algorithm

Rojas, O; Gil Costa V.; Marin M.

Abstract

Large Web search engines are complex systems that solve thousands of user queries per second on clusters of dedicated distributed memory processors. Processing each query involves executing a number of operations to get the answer presented to the user. The most expensive operation in running time is the calculation of the top-k documents that best match each query. In this paper we propose the parallelization of a state of the art document ranking algorithm called Block-Max WAND. We propose a 2-steps parallelization of the WAND algorithm in order to reduce inter-processor communication and running time cost. Multi-threading tailored to Block-MaxWAND is also proposed to exploit multi-core parallelism in each processor. The experimental results show that the proposed parallelization reduces execution time significantly as compared against current approaches used in search engines.

Más información

Título según WOS: Efficient Parallel Block-Max WAND Algorithm
Título de la Revista: Lecture Notes in Computer Science (LNCS)
Volumen: 8097
Editorial: Springer
Fecha de publicación: 2013
Página de inicio: 394
Página final: 405
Idioma: English
Notas: ISI