Asynchronous Computation of PageRank computation in an interactive multithreading environment

Abstract

Numerical Linear Algebra has become almost indispensable in Web
Information Retrieval.

In this presentation we suggest that the asynchronous computation model
is an attractive paradigm for organizing concurrent computations
spanning data on Web scale. This suggestion is supported by
experiments which highlight some interesting characteristics of this
model as applied to 'page ranking' methods.

After an introduction on asynchronous computing in general and 'page
ranking' in particular, we present results from the asynchronous
compution of PageRank using typical combinations of execution units
(processes, threads) and communication mechanisms (message passing,
shared memory). Sound convergence properties predicted by theory are
numerically verified and interesting patterns of behavior are
unveiled. Our experiments were performed on Jylab, an evolving
environment enabling interactive multithreading and multiprocessing
computations. This work is supported by a Pythagoras-EPEAEK-II grant 
and is conducted in collaboration with Daniel Szyld.