Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Computational Science, Engineering & Technology Series
DEVELOPMENTS AND APPLICATIONS IN ENGINEERING COMPUTATIONAL TECHNOLOGY
Edited by: B.H.V. Topping, J.M. Adam, F.J. Pallarés, R. Bru and M.L. Romero
Fast PageRank Computation for Web Information Retrieval by Parallel Generalized Approximate Inverse Preconditioning
G.A. Gravvanis1, K.M. Giannoutakis1 and N.D. Iatridis2
1Department of Electrical and Computer Engineering, School of Engineering, Democritus University of Thrace, Xanthi, Greece
G.A. Gravvanis, K.M. Giannoutakis, N.D. Iatridis, "Fast PageRank Computation for Web Information Retrieval by Parallel Generalized Approximate Inverse Preconditioning", in B.H.V. Topping, J.M. Adam, F.J. Pallarés, R. Bru and M.L. Romero, (Editors), "Developments and Applications in Engineering Computational Technology", Saxe-Coburg Publications, Stirlingshire, UK, Chapter 14, pp 307-335, 2010. doi:10.4203/csets.26.14
Keywords: web information retrieval, Markov chains, linear systems, parallel approximate inverses, parallel preconditioned conjugate gradient method, multiprocessor systems, OpenMP.
PageRank is considered as a "fair" algorithm for computing the importance of web sites. The World Wide Web is considered as a huge graph, where the web pages are the nodes and the hyperlinks between them are the edges. The ranking value is a factor of the number of external links that point to the web page, and it is classified to a scale from 0 to 1 [1-4]. The computation of the PageRank factor for a set of web pages is a demanding process, and the need for a fast and efficient algorithm is of great importance [2,3,5].
The purpose of this paper is the study and the efficient computation of the PageRank web information retrieval ranking. This index is based on a Markov modeling of the web. More specifically the defined Markov chain is a random walk over the graph, which consists of sites and links between them in the web. The transition matrix has to be appropriately adjusted in order to have an ergodic chain, and the index computation is based on the solution of a linear system of algebraic equations [1-4].
Explicit approximate inverse preconditioning methods have been extensively used for efficiently solving sparse linear systems on multiprocessor systems . The effectiveness of explicit approximate inverse preconditioning schemes relies on the use of efficient preconditioners that are close approximants to the coefficient matrix and are fast to compute in parallel [5-8].
New parallel computational techniques are proposed for the construction of the explicit approximate inverse and the explicit preconditioned conjugate gradient methods, for multiprocessor systems [5,6,9].
For the parallel construction of the approximate inverse preconditioner an anti-diagonal computational pattern has been used in order to overcome the data dependencies of the inverse [5,6,9]. Additionally, a "fish bone" computational approach is introduced, with respect to the antidiagonal data dependency pattern, where cyclic distribution of the processors has been used, in order to increase the granularity and overcome the parallelization overheads [5,9]. The inherently parallel linear operations between vectors and matrices involved in the explicit preconditioned conjugate gradient schemes exhibit significant amounts of loop-level parallelism that can lead to high performance gain on shared address space systems [5,9].
Finally, numerical results for the performance of the explicit approximate inverse and explicit preconditioned methods for the computation of the web informational retrieval ranking, on uniprocessor and multiprocessor computer systems are presented. The implementation issues of the proposed algorithms are also discussed using OpenMP for multiprocessor systems.
purchase the full-text of this chapter (price £20)