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 [6]. 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.

[1]

P. Berkhin, "A Survey on PageRank Computing", Internet Mathematics, 2(1), 73-120, 2005. doi:10.1080/15427951.2005.10129098

[2]

A.N. Langville, C.D. Meyer, "Google's PageRank and Beyond: The Science of Search Engine Rankings", Princeton University Press, 2006.

[3]

A.N. Langville, C.D. Meyer, "A Survey of Eigenvector Methods for Web Information Retrieval", SIAM Review, 47(1), 135–161, 2005. doi:10.1137/S0036144503424786

[4]

A.N. Langville, C.D. Meyer, "Deeper inside PageRank", Internet Math., 1(3), 335-380, 2004. doi:10.1080/15427951.2004.10129091

[5]

G.A. Gravvanis, "High Performance Inverse Preconditioning", Archives of Computational Methods in Engineering 16(1), 77-108, 2009. doi:10.1007/s11831-008-9026-x

[6]

G.A. Gravvanis, "On the solution of boundary value problems by using fast generalized approximate inverse banded matrix techniques", The Journal of Supercomputing, 25(2), 119-129, 2003. doi:10.1023/A:1023936410006

[7]

G.A. Gravvanis, "Explicit Approximate Inverse Preconditioning Techniques", Archives of Computational Methods in Engineering, 9(4), 371-402, 2002. doi:10.1007/BF03041466

[8]

G.A. Gravvanis, "Approximate inverse banded matrix techniques", Engineering Computations, 16(3), 337-346, 1999. doi:10.1108/02644409910266485

[9]

K.M. Giannoutakis, G.A. Gravvanis, "High performance finite element approximate inverse preconditioning", Applied Mathematics and Computation, 201, 293-304, 2008. doi:10.1016/j.amc.2007.12.023

purchase the full-text of this chapter (price £20)

go to the previous chapter
go to the next chapter
return to the table of contents
return to the book description
purchase this book (price £98 +P&P)