PDF Publication Title:
Text from PDF Page: 174
152 6 ⋅ software With the exception of mst_prim, the gaimc functions are roughly 2-4 times slower than their MatlabBGL counterparts. At the moment, we don’t understand why the dfs function is faster in gaimc or why the mst_prim routine has dramatically different performance. Exploring these differences is a task for the future. 6.5 libbvg and bvgraph’s in matlab The final software package that we discuss in this chapter is libbvg and its Matlab counterpart bvgraph. All the source code and examples for these paired packages are online at the LaunchPad open-source hosting repository, https://launchpad.net/libbvg.19 Both of these packages work with web graphs, which are graphs formed by hyper-linking relationships on the world wide web. These graphs are extremely large—the complete network has over one trillion nodes [Alpert and Hajaj, 2008]—and subsets often have more than one hundred million nodes. Although gigantic, the network and its subsets have considerable structure. Both libbvg and bvgraph provide an interface for web graphs compressed in the Boldi-Vigna (BV) scheme [Boldi and Vigna, 2005]. With this scheme, web graphs often use fewer than three bits per link. Standard graph storage techniques need more than four bytes per link.20 The Boldi-Vigna compres- sion scheme exploits two empirically observed properties of web graphs to obtain such remarkable compression rates. First, when the URLs of each node are ordered lexicographically, then the link distances (∣i − j∣ where i and j are the indices of the URLs of the link) follow a power-law. Boldi and Vigna designed a special coding scheme to compress these power-law distributed numbers. Second, many URLs within a site repeat the same links. Allow- ing nodes to “copy” links from previous nodes (within a limited window of previous nodes) allows them to compress these structures. Together, these techniques are incredibly effective and stable—they have compressed web graphs collected between 2001 and 2007 at nearly the same rate (three bits per edge). The only problem with their compression scheme is that it makes random access to the out-edges of a node less efficient than sequential (or streaming) access. This occurs because the desired out-edges may reside in a node that copies its links from a previous node, which also copies its links from a previ- ous node, and so on. To combat the “infinite” copying, the implementation imposes an optional limit on the maximum copy depth. 19 We anticipate migrating them to the github system soon. 20 This estimate assumes that graphs are stored with compressed sparse row arrays with 32-bit indices (four bytes) and without any compres- sion.PDF 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 (Standard Web Page)