È possibile eseguire il pagerank senza l'intero set di dati?

Question

Scusate se è stupido ma stavo solo pensando che dovrei fare un tentativo. Supponiamo che io abbia un grafico enorme (ad esempio, 100 miliardi di nodi). Neo4J supporta 32 miliardi e altri supportano più o meno la stessa cosa, quindi dire che non posso avere l'intero set di dati in un database allo stesso tempo, posso eseguire pagerank su di esso se è un grafico diretto (nessun loop) e ogni serie di nodi connettono al prossimo set di nodi (quindi nessun nuovo collegamento verrà creato all'indietro, solo nuovi collegamenti verranno creati per nuovi insiemi di dati).

C'è un modo per prendere in qualche modo i punteggi dei pagerank precedenti e applicarli a nuovi set di dati (mi interessa solo il pagerank per il set di dati più recente ma ho bisogno del pagerank del set precedente per ricavare gli ultimi dati di set)?

Ha senso? Se è così, è possibile farlo?

Answer 1

È necessario calcolare l'autovettore principale di una matrice da 100 miliardi a 100 miliardi. A meno che non sia estremamente scarso, non è possibile installarlo all'interno della macchina. Quindi, hai bisogno di un modo per calcolare l'autovettore principale di una matrice quando puoi guardare solo una piccola parte della tua matrice alla volta.

I metodi iterativi per calcolare gli autovettori richiedono solo che vengano memorizzati alcuni vettori ad ogni iterazione (avranno ciascuno 100 miliardi di elementi). Quelli possono adattarsi alla tua macchina (con galleggianti di 4 byte avrai bisogno di circa 375 GB per vettore). Una volta che hai un vettore candidato di classifiche puoi (molto lentamente) applicare la tua matrice gigante leggendo la matrice in blocchi (dato che puoi guardare 32 miliardi di file alla volta avrai bisogno di poco più di 3 blocchi). Ripeti questo processo e avrai le basi del metodo di alimentazione che è quello che viene usato nel pagerank. cf http://www.ams.org/samplings/feature-column/fcarc-pagerank e http://en.wikipedia.org/wiki/Power_iteration

Naturalmente il fattore limitante qui è quante volte è necessario esaminare la matrice. Si scopre che memorizzando più di un vettore candidato e utilizzando alcuni algoritmi randomizzati è possibile ottenere una buona precisione con meno letture dei dati. Questo è un argomento di ricerca corrente nel mondo matematico applicato. Puoi trovare maggiori informazioni qui http://arxiv.org/abs/0909.4061, qui http://arxiv.org/abs/0909.4061, e qui http://arxiv.org/abs/0809.2274. C'è il codice disponibile qui: http://code.google.com/p/redsvd/ ma non puoi usare quello disponibile per le dimensioni dei dati di cui stai parlando.

Un altro modo per procedere è esaminare "svd incrementale" che potrebbe adattarsi meglio al tuo problema, ma è un po 'più complicato. Considerate questa nota: http://www.cs.usask.ca/~spiteri/CSDA-06T0909e.pdf e il forum: https://mathoverflow.net/questions/32158/distributed-incremental-svd