PDF Publication Title:
Text from PDF Page: 175
Efficient access to large graphs is a powerful experimental tool for algo- rithms like PageRank. In the remainder of this section, we describe the two libraries and how they let us compute on enormous graphs with limited re- sources. 6.5.1 libbvg In libbvg, we provide a C99 interface for web graphs compressed in the Boldi-Vigna scheme. The library enables both in-core and out-of-core access to these graphs and intends to mirror the Java WebGraph framework [Vigna, 2008]. The following program uses the library to extract the degree for each node in a graph and store them in the array degs: bvgraph g = {0}; bvgraph_load(&g, graphfilename, strlen(graphfilename), -1); /* load out-of-core */ bvgraph_iterator iter; unsigned int deg; double *degs = malloc(sizeof(double)*g.n); int rval = bvgraph_nonzero_iterator(&g, &iter); for (; bvgraph_iterator_valid(&iter); bvgraph_iterator_next(&iter)) { bvgraph_iterator_outedges(&iter, NULL, °); *(degs++) = (double)deg; } bvgraph_iterator_free(&iter); The two types bvgraph and bvgraph_iterator encompass most of the func- tionality of the library. The bvgraph type stores the data about the graph and the bvgraph_iterator type sequentially accesses vertices and their edges. 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 Before getting to the power method, let us mention that libbvg has a few extensions to work with the bvgraph data structures 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 21 See section 5.6.3 for more infor- mation about the performance of this technique with PageRank. 6.5 ⋅ libbvg and bvgraph’s in matlab 153PDF Image | Instagram Cheat Sheet
PDF Search Title:
Instagram Cheat SheetOriginal File Name Searched:
pagerank-sensitivity-thesis-online.pdfDIY 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 | RSS | AMP |