Struttura enorme del grafico

Question

Sto sviluppando un'applicazione in cui ho bisogno di una struttura per rappresentare un enorme grafico (tra 1000000 e 6000000 nodi e 100 o 600 spigoli per nodo) in memoria. La rappresentazione dei bordi conterrà alcuni attributi della relazione.

Ho provato una rappresentazione della mappa di memoria, array, dizionari e stringhe per rappresentare quella struttura in memoria, ma questi si bloccano sempre a causa del limite di memoria.

Mi piacerebbe avere un consiglio su come posso rappresentare questo, o qualcosa di simile.

A proposito, sto usando python.

Answer 1

1. Se questo è 100-600 bordi/nodo, allora si parla di 3,6 miliardi di bordi.
2. Perché questo deve essere tutto in memoria?
3. Puoi mostrarci le strutture che stai utilizzando attualmente?
4. Quanta memoria sono abbiamo permesso (qual è il limite di memoria si sta colpendo?)

Se l'unica ragione per cui avete bisogno di questo in memoria è perché è necessario essere in grado di leggere e scrivere in fretta, poi usa un database I database leggono e scrivono estremamente velocemente, spesso possono leggere senza andare sul disco.

Answer 2

Sembra che ci siano pochi margini considerando la quantità di nodi, il che suggerisce che la maggior parte dei nodi non è strettamente necessaria. Quindi, invece di memorizzare effettivamente tutti i nodi, perché non utilizzare una struttura sparsa e inserirli solo quando sono in uso? Questo dovrebbe essere abbastanza facile da fare con un dizionario; basta non inserire il nodo fino a quando non lo usi per un bordo.

I bordi possono essere memorizzati utilizzando un adjacency list sui nodi.

Naturalmente, questo si applica solo se si intendono veramente 100-600 nodi in totale. Se intendi per nodo, questa è una storia completamente diversa.

Answer 3

dubito che sarete in grado di utilizzare una struttura di memoria a meno che non si dispone di una grande quantità di memoria a disposizione:

Si supponga che si sta parlando di circa 600 archi orientati da ogni nodo, con un nodo di essere 4-byte (tasto intero) e un bordo diretto come JUST i tasti del nodo di destinazione (4 byte ciascuno).

Dai dati grezzi su ciascun nodo è 4 + 600 * 4 = 2404 byte x = 6.000.000 sopra 14.4GB

Questo è senza altre spese generali o dati aggiuntivi nei nodi (o bordi).

Answer 4

Sembra che sia necessario un database e un iteratore sui risultati. Quindi non dovresti tenere tutto in memoria allo stesso tempo, ma puoi sempre accedervi.

Answer 5

Se si decide di utilizzare una sorta di database dopo tutto, suggerisco di guardare neo4j e le sue associazioni Python. È un database grafico in grado di gestire grafici di grandi dimensioni. Ecco un presentation da PyCon di quest'anno.

Answer 6

Supponendo che vuoi dire 600 per nodo, si potrebbe provare qualcosa di simile:

import os.path 
import cPickle 
class LazyGraph: 
    def __init__(self,folder): 
     self.folder = folder 

    def get_node(self,id): 
     f = open(os.path.join(self.folder,str(id)),'rb') 
     node = cPickle.load(f) 
     f.close() # just being paranoid 
     return node 

    def set_node(self,id,node): 
     f = open(os.path.join(self.folder,str(id)),'wb') 
     cPickle.dump(node,f,-1) # use highest protocol 
     f.close() # just being paranoid 

Utilizzare array (o array NumPy) per contenere gli ID dei nodi attuali, in quanto sono più veloci.

Nota, questo sarà molto molto lento.

È possibile utilizzare il threading per pre-scaricare i nodi (presumendo che tu abbia saputo in quale ordine li stavi elaborando), ma non sarà divertente.

Answer 7

A seconda delle risorse hardware disponibili, un dato in memoria per un grafico di queste dimensioni è probabilmente fuori questione. Due le possibili opzioni da un grafico specifico punto di vista DB sono:

• Neo4j - sostiene di gestire facilmente miliardi di nodi e il suo stato in sviluppo da molto tempo.
• FlockDB - appena rilasciato da Twitter questo è un database grafico distribuito.

Dal momento che si utilizza Python, hai guardato Networkx? Fino a che punto hai caricato un grafico di queste dimensioni se l'hai guardato per interesse?

Answer 8

Il pacchetto scipy.sparse.csgraph può essere in grado di gestire questo: 5 milioni di nodi * 100 bordi in media 500 milioni di coppie, a 8 byte per coppia (due ID interi) è solo circa 4 GB. Penso che csgraph usi la compressione quindi userà meno memoria di quella; questo potrebbe funzionare sul tuo laptop.

csgraph non ha tante funzioni di networkx ma utilizza meno memoria.