ALGORITHMS FOR PAGERANK SENSITIVITY DISSERTATION

PDF Publication Title:

ALGORITHMS FOR PAGERANK SENSITIVITY DISSERTATION ( algorithms-for-pagerank-sensitivity-dissertation )

Previous Page View | Next Page View | Return to Search List

Text from PDF Page: 158

138 6 ⋅ software The current libbvg does not yet support accessing vertices in the graph randomly. Some of the support for random access exists in an unfinished bvgraph_random_iterator structure. There is little left to the library beyond the two types above. Primarily, this follows because access to out-edges is sufficient to compute PageRank and other simple problems on the graph. In the next section, we discuss an optimized implementation of the power method for PageRank using these data structures. parallel extensions Beforegettingtothepowermethod,letusmen- tion that libbvg has a few extensions to work with the bvgraph data struc- tures in a multi-core environment. The idea is that each core will have its own computation thread and we can assign a contiguous set of nodes to that core. In the implementation, we assign a special nonzero iterator to each thread. These special iterators store their state so that they can begin iterating in the middle of the graph, which eliminates the problem with links copying their predecessors.21 6.5.2 The power method in libbvg In program 9, we present an implementation of the power method in libbvg. Many of the vector operations in the standard power method are gone. This particular code replaces them with a series of combined operations. So that we can understand how the optimizations work, we begin by repeating a simple implementation of the power method from program 2. We stripped the implementation down to the pure computational pieces (and removed all the convenience features). function [x flag reshist]=powerpr(P,a,v,tol,maxit,verbose) n=size(P,1); x=zeros(n,1)+v; delta=2; iter=0; while itertol y = a*(P’*x); w = 1-csum(y); y = y + w*v; delta = normdiff(x,y); x = y./csum(y); end In program 9, the vectors x and y must be initialized before the bvpr func- tion, and thus the first few lines of the Matlab implementation are irrelevant. The y = a*(P’*x) work is handled by the mult function. In addition to computing y, this function also computes eT y and dT x—both using compen- sated summation. Consequently, once the function returns, line 53 of bvpr computes w without any additional work. The next line performs the shift y = y + w*v and simultaneously computes csum(y). Line 56 normalizes y, computes the difference normdiff(x,y), and resets x. Line 57 extracts the compensated sum for delta and line 58 swaps the interpretation of x and y. Note that, before the swap, y held the newly normalized iterate and x was reset to 0. Thus, the program is ready for another iteration after the swap. In total, this approach utilizes two passes of the memory of x and y: the first in line 54 and the second in line 56. In contrast, the Matlab code uses 5 passes over the memory of x and y. Vectorized computations, such as the Matlab code, sometimes sacrifice some performance.22 21 See section 5.6.3 for more information about the performance of this technique with PageRank. 22 Furthermore, we also apply multi- threading to program 9 to take advan- tage of working on a multi-core system.

PDF Image | ALGORITHMS FOR PAGERANK SENSITIVITY DISSERTATION

PDF Search Title:

ALGORITHMS FOR PAGERANK SENSITIVITY DISSERTATION

Original File Name Searched:

gleich.pdf

DIY PDF Search: Google It | Yahoo | Bing

Cruise Ship Reviews | Luxury Resort | Jet | Yacht | and Travel Tech More Info

Cruising Review Topics and Articles More Info

Software based on Filemaker for the travel industry More Info

The Burgenstock Resort: Reviews on CruisingReview website... More Info

Resort Reviews: World Class resorts... More Info

The Riffelalp Resort: Reviews on CruisingReview website... More Info

CONTACT TEL: 608-238-6001 Email: greg@cruisingreview.com (Standard Web Page)