Come / dove eseguire l'algoritmo su un set di dati di grandi dimensioni?

La cosa bella dell'algoritmo PageRank è che può essere risolto iterativamente in modo distribuito, all'interno di MapReduce framework. Tuttavia, i dati di lavoro di Pagerank su ~ 5 M nodi e ~ 50 M di bordi dovrebbero adattarsi perfettamente alla RAM da 4 GB, non importa 48 GB ....

In particolare, non è necessario memorizzare tutti i dati per ciascuna pagina Web in memoria, ma è necessario digerire il database di input in modo che i dati di lavoro per il risolutore PageRank si riferiscano ai nodi per indice. Anche con nessuno sforzo particolare all'ottimizzazione, ogni nodo non dovrebbe richiedere più di 32 byte e ogni margine non più di 16 byte, per spazio in memoria inferiore a 1 GB.

Un esempio dimostrativo per questo tipo di infrastruttura dati, 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];
    }
}

L'esecuzione su un singolo PC è più semplice che eseguirla su un servizio cloud, perché non è necessario utilizzare un framework di rete (anche se potrebbe essere una buona idea tenere a mente questa possibilità). Le dimensioni relativamente piccole che stai descrivendo possono essere risolte facilmente con un algoritmo ad-thread singolo e puoi utilizzare Hadoop localmente o tira il tuo MapReduce usando thread o comunicazioni tra processi se vuoi più core.

Dipenderà dalla quantità di dati con cui stai effettivamente lavorando (quanto è grande un nodo?), ma in genere codice come questo trarrà vantaggio dall'esecuzione il più vicino possibile ai dati. Dovrebbe essere certamente possibile eseguirlo su un computer di casa di fascia alta (qualcosa con molta RAM e alcuni SSD), oppure potresti configurare un piccolo cluster (ad esempio 3-4 macchine) con uno switch gigabit. Scusa, non ne so abbastanza sull'algoritmo PageRank per fornire alcun dettaglio specifico, ma ho eseguito i lavori Hadoop sulla mia macchina domestica con una CPU quad-core e 8G di RAM (non una classe di macchine non comune al giorno d'oggi).

Per un progetto così grande, sarà molto costoso utilizzare servizi basati su cloud. Poiché stai usando Java, ti consiglio di dare un'occhiata a Hadoop usando più computer / server di casa che sarai in grado di ottenere i risultati.

Puoi poter utilizzare una specie di tecnica di clustering (ad es. MapReduce), ma con questa piccola dimensione di dati, assolutamente non è necessario utilizzare il clustering .

Con questa dimensione di dati, dovresti essere in grado di farlo tutto in memoria. Supponendo un approccio ingenuo:

• 15 mb - Punteggi della precedente iterazione (4.000.000 di 32 bit in virgola mobile)
• 15 mb - Punteggi dalla prossima iterazione (4.000.000 float 32 bit)
• 190 mb - Web Graph, assumendo una struttura grafica naive di {num outlinks, outlink 1, outlink 2, ... outlink n} fatti di 32 bit ints, il grafico si adatterebbe in 45.000.000 * 32 bit + 4.000.000 * 32 bit,

Circa 250 mb. L'approccio ingenuo sarebbe simile a questo:

 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
 }

"Ma ho anche questo altro grafico che WONT si adatta alla memoria!"

Per il calcolo del pagerank in memoria su qualsiasi grafico di dimensione, controlla questo documento . Descrive una tecnica multi-pass (per singola pagina di iterazione) che consente di completare il pagerank in memoria, assumendo l'accesso al flusso al grafico e ai punteggi delle iterazioni precedenti.

Richiede di mantenere i punteggi correnti in memoria. Con 4.000.000 di nodi e supponendo float a 32 bit, si osservano circa 15 megabyte di dati, oltre a qualsiasi sovraccarico di array. Il tuo server da 48 GB andrà bene per questo (e andrà bene anche per l'approccio ingenuo, vedi sotto).

Avrai una bella piccola rappresentazione del grafico che ti consentirà di leggerlo in uno stream. Poiché stai utilizzando Java, consulta il framework di compressione WebGraph . È descritto dettagliatamente in questo documento . Per un grafico di 118.000.000 di nodi e 1.000.000.000 di link, si cita una compressione di 3.08 bit per collegamento, il che è sorprendente.

Si noti che esiste anche un'implementazione C ++ del framework di compressione WebGraph disponibile a quel link, ma è MUCH SLOWER, principalmente perché è una parola per parola porta del codice Java, piuttosto che un'implementazione C ++ dell'algoritmo di compressione.

Utilizzando questo approccio, ho avuto il codice Java per pagerank che ha raggiunto la convergenza in poco meno di un'ora su un singolo desktop dell'era 2007 con 2 gig di ram, su un grafico Web di 80.000.000 di nodi. Il codice C ++ per lo stesso è durato circa due ore (a causa delle differenze di velocità nell'implementazione della compressione).

Fammi sapere se hai bisogno di aiuto.