How/where to run the algorithm on large dataset?

I would like to run the PageRank algorithm on graph with 4 000 000 nodes and around 45 000 000 edges.

Currently I use neo4j graph databse and classic relational database (postgres) and for software projects I mostly use C# and Java.

Does anyone know what would be the best way to perform a PageRank computation on such graph? Is there any way to modify the PageRank algorithm in order to run it at home computer or server (48GB RAM) or is there any useful cloud service to push the data along the algorithm and retrieve the results?

At this stage the project is at the research stage so in case of using cloud service if possible, would like to use such provider that doesn’t require much administration and service setup, but instead focus just on running the algorith once and get the results without much overhead administration work.

The nice thing about the PageRank algorithm is that it can be solved iteratively in a distributed way, within the MapReduce framework. However, the working data for Pagerank on ~5M nodes and ~50M edges should fit perfectly well in 4GB ram, never mind 48GB….

Specifically, you don’t need to store all data for each web page in memory — instead, you should digest your input database so that the working data for the PageRank solver refers to nodes by index. Even with no particular effort at optimization, each node should take no more than 32 bytes, and each edge no more than 16 bytes, for in-memory space of less than 1GB.

A demonstration example for this kind of datastructure, in C++/STL:

std::vector<float> old_rank, new_rank;  // rankings for each node
std::vector<int> end_edge;  // index after final edge for each node
std::vector<int> edge_dest;  // destination node index for each edge
std::vector<float> edge_weight;  // fractional weight for each edge

...

void pagerank_iteration(float base_value, float scale_value) {
    new_rank.fill(0.0);
    int edge = 0;  // loop variable:  current edge index
    for(int node=0; node<first_edge.size(); ++node) {  // loop over nodes
        while(edge < end_edge[node]) { // loop over edges of current node
            int dest_node = edge_dest[edge];
            new_rank[dest_node] += edge_weight[edge] * old_rank[node];
            ++edge;
        }
    }
    assert(edge == edge_dest.size());

    for(int node=0; node<new_rank.size(); ++node) {  // add scale/offset
        new_rank[node] = base_value + scale_value * new_rank[node];
    }
}

Running on a single PC is easier than running it on a cloud service, because you don’t need to use a network-capable framework (although it might be a good idea to keep that possibility in mind). The relatively small sizes you are describing can be solved easily with an ad-hoc single-threaded algorithm, and you can either use Hadoop locally or roll your own MapReduce using threads or inter-process communication if you want more cores.

It will depend on how much data you are actually working with (how big is a node?), but typically code like this really benefits from running as close to the data as possible. It should certainly be possible to run this on a high-end home computer (something with lots of RAM and some SSDs), or you could potentially set up a small cluster (say 3-4 machines) with a gigabit switch. Sorry, I don’t know enough about the actual PageRank algorithm to give any specifics, but I have run Hadoop jobs on my home machine with a quad-core CPU and 8G of RAM (not an uncommon class of machines these days).

For such a big project, it will be very costly to utilize cloud based service. As you are using Java, I would recommend that you have a look at Hadoop Using more then home computer/server you will be able to get the results.

You can use some kind of clustering technique (eg MapReduce), but with this small size of data, you absolutely don’t need to use clustering.

With this size of data, you should be able to do it all in memory. Assuming a naive approach:

15 mb – Scores from the previous iteration (4,000,000 32 bit floats)
15 mb – Scores from the next iteration (4,000,000 32 bit floats)
190 mb – Web Graph, assuming a naive graph structure of {num outlinks, outlink 1, outlink 2, … outlink n} made of 32 bit ints, the graph would fit in 45,000,000 * 32 bits + 4,000,000 * 32 bits,

About 250 mb. The naive approach would look something like this:

 N <- size of graph
 c <- dampening factor

 source_scores[N] <- array of floats, initalised to 1 / N.
 dest_scores[N] <- array of floats

 repeat until convergence {
    for all n up to N { dest_scores[n] = 0 }

    for all source,dest links {
        dest_scores[dest] += source_scores[source] / num_outlinks of source
    }

    for all n up to N {
        dest_scores[n] = c * dest_scores[n] + (1 - c)/N
    }

    copy dest_scores to source_scores
 }

“But I also have this other graph that WONT fit in memory!”

For in-memory pagerank computation on any size graph, check out this paper. It describes a multi-pass (per single pagerank iteration) technique that allows you to complete pagerank in memory, assuming stream access to the graph and scores from previous iterations.

It requires that you hold the current scores in memory. With 4,000,000 nodes, and assuming 32 bit floats, you’re looking at about 15 megabytes of data, plus any array overhead. Your 48 gig server will be fine for this (and it will also be fine for the naive approach, see below).

You’ll want a nice small representation of the graph that allows you to read it in in a stream. Since you’re using Java, check out the WebGraph compression framework. It is described in detail in this paper. For a graph of 118,000,000 nodes and 1,000,000,000 links they quote a compression of 3.08 bits per link, which is amazing.

Note that there’s also a C++ implementation of the WebGraph compression framework also available at that link, but it is MUCH SLOWER, mostly because it’s a word for word port of the Java code, rather than a C++ implementation of the compression algorithm.

Using this approach, I had Java code for pagerank that achieved convergence in just under an hour on a single 2007-era desktop with 2 gig of ram, over an 80,000,000 node web graph. The C++ code for the same ran in about two hours (due to the speed differences in the compression implementation).

Let me know if you need any help.

Filed under: softwareengineering - @ 01:32

Thẻ: algorithms, cloud-computing, large-scale-project

Thiết kế website giá rẻ

Danh mục