breadth-first-ricerca su enormi grafico con poca RAM

Question

Al momento ho un grafico che ha circa 10 milioni di nodi e 35 milioni di bordi . Per ora il grafo completo viene caricato in memoria all'avvio del programma. Questo richiede un paio di minuti (è Java dopo tutto) e ha bisogno di circa mezzo gigabyte di RAM. Per ora gira su un computer con un processore dual core e 4 gigabyte di RAM.

Quando il grafico viene cercato tramite un breadth-first-cercare gli aumenti di utilizzo della memoria ad un picco di un gigabyte e ci vogliono dieci secondi in media.

Vorrei distribuire il programma su un paio di computer. La funzionalità a parte la ricerca del grafico ci vuole molto poche risorse. Il mio sistema di destinazione è molto in miniatura e ha solo 512 MB di RAM.

Qualche suggerimento su come implementare un metodo (probabilmente utilizzando un database) per cercare quel grafico senza consumare troppa memoria? Il programma è inattivo la maggior parte del tempo in quanto accede a un dispositivo hardware, in modo che il percorso-scoperta potrebbe prendere circa 5 minuti max per il grafico citato ...

Grazie per ogni pensiero gettati nella mia direzione.

UPDATE:

Neo4j . Qualcuno sa se sarebbe adatto per questo tipo di grafico humongous?

Answer 1

La tua domanda è un po 'vago, ma in generale, una buona strategia che segue per lo più ampiezza primi semantica utilizzando la stessa quantità di memoria come ricerca in profondità è iterativo Approfondimento . L'idea è di fare una ricerca in profondità limitata a 1 livello in un primo momento; se fallisce per trovare una soluzione, iniziare da zero e limitarla a 2 livelli; se non funziona, provare a 3 livelli, e così via.

Questo può sembrare un po 'ridondante in un primo momento, ma dal momento che si sta facendo una ricerca in profondità, è mantenere molti meno nodi in memoria, e cercare sempre di un livello meno di una ricerca in ampiezza semplice. Dal momento che la quantità di nodi in un livello cresce in modo esponenziale, sui grafici più grandi, è molto probabile che il risparmio che un ultimo ulteriore livello paga per aver tentato tutti i livelli precedenti in modo ridondante.

Answer 2

Direi che Neo4j è sicuramente un buon modo per andare quando si dispone di un grafico di dimensioni decenti come questo. Non solo sono dotati di algoritmi BFS avrete anche voi persistere dati su disco, riducendo così il tempo di start-up.

Check this out on highscalability.com: Neo4j - Un database grafico che prende il buttox

Ho usato Neo4j e la loro documentazione è molto buono, e forniscono alcune belle esempi di iniziare, che in realtà si prendono pochi minuti per andare avanti.

Controllare il loro - Primi passi in 10 minuti guida

Answer 3

Neo4j memorizza i dati nel database come grafico, diventa persistente ed è possibile accedere utilizzando il grafico Traversal Api (BFS, DBS, A * Dijkstra ...), o Utilizzo linguaggio di query Cypher.