Archiviare grafici molto grandi su algoritmi di partizionamento del grafico su disco/streaming?

Question

Supponiamo di avere un grande grafo non orientato, non ponderato (a partire da centinaia di milioni di vertici, ~ 10 spigoli per vertice), non distribuito ed elaborato solo da un singolo thread e che voglio fare ricerche di ampiezza su di esso . Mi aspetto che siano legati all'I/O, quindi ho bisogno di un layout di pagina del disco buono per BFS, lo spazio su disco non è un problema. Le ricerche possono iniziare su ogni vertice con uguale probabilità. Intuitivamente ciò significa minimizzare il numero di spigoli tra i vertici su diverse pagine del disco, che è un problema di partizionamento del grafico.

Il grafico stesso sembra uno spaghetto, pensiamo a un insieme casuale di punti casualmente interconnessi, con qualche pregiudizio verso i bordi più corti.

Il problema è, in che modo un grafico di partizione è così grande? I partitori di grafici disponibili che ho trovato funzionano con grafici che si adattano solo alla memoria. Non sono riuscito a trovare descrizioni o implementazioni di algoritmi di partizionamento di grafici in streaming.

O, forse c'è un'alternativa al grafico di partizionamento per ottenere un layout del disco che funzioni bene con BFS?

In questo momento, come approssimazione, utilizzo il fatto che i vertici hanno coordinate spaziali ad essi collegate e posizionano i vertici su disco in ordine di Hilbert. In questo modo i vertici spazialmente vicini si posizionano sulla stessa pagina, ma la presenza o l'assenza di spigoli tra di essi viene completamente ignorata. Posso fare di meglio?

In alternativa, posso dividere il grafico in pezzi usando l'ordine di ordinamento Hilbert per i vertici, suddividere i sottografi, ricucirli e accettare un partizionamento insufficiente sulle cuciture.

Alcune cose che hanno esaminato già:

1. How to store a large directed unweighted graph with billions of nodes and vertices
2. http://neo4j.org/ - ho trovato informazioni a zero su come fa a fare il grafico di layout su disco

implementazioni partizionamento (a meno che io sono errato, tutti devono inserire il grafico nella memoria):

1. http://glaros.dtc.umn.edu/gkhome/views/metis
2. http://www.sandia.gov/~bahendr/chaco.html
3. http://staffweb.cms.gre.ac.uk/~c.walshaw/jostle/
4. http://www.cerfacs.fr/algor/Softs/MESHPART/

EDIT: informazioni su come i grafici assomiglia e che BFS può iniziare ovunque. MODIFICA: idea sul partizionamento sottotitoli

Answer 1

Nessun algoritmo ha realmente bisogno di "adattarsi alla memoria" - è sempre possibile inserire e ritirare le cose quando necessario. Ma si vuole evitare che il calcolo scenda irragionevolmente a lungo - e il partizionamento globale del grafico nel caso generico è un problema NP-completo, che è "irragionevolmente lungo" per la maggior parte dei problemi che non si adattano nemmeno alla memoria.

Fortunatamente, si desidera effettuare ricerche in ampiezza, il che significa che si desidera un formato in cui l'ampiezza è il calcolo semplice. Non conosco nessuno algoritmo che faccia ciò, ma puoi costruire il tuo layout in larghezza se sei disposto a consentire un po 'di spazio su disco extra.

Se i bordi non sono distorti verso le interazioni locali, la districatura del grafico sarà difficile. Se sono distorti verso interazioni locali, allora suggerisco un algoritmo come il seguente:

• Scegli un insieme casuale di vertici come punti di partenza da tutto il set di dati.
• Per ciascun vertice, raccogliere tutti i vertici adiacenti (effettua una scansione attraverso il set di dati).
• Per ogni serie di vertici vicini raccogliere l'insieme di vicini di casa e classificarli in base a quanti lati si collegano a essi. Se non si dispone di spazio in una pagina per archiviarli tutti, mantenere i vertici più connessi. Se hai spazio per salvarli tutti, potresti voler eliminare quelli meno utili (ad esempio se la frazione di bordi mantenuti all'interno di una pagina/frazione di vertici che necessitano di un rapporto di memoria scende "troppo bassa" - dove "troppo basso" dipenderà da quanta ampiezza le tue ricerche hanno veramente bisogno e se puoi fare qualsiasi potatura e così via - quindi non includere quelle nelle vicinanze
• Ripeti il ​​processo di raccolta e classifica dei vicini fino a quando il tuo quartiere non è pieno (ad esempio riempie alcune dimensioni della pagina che ti si addice), quindi controlla le ripetizioni tra le partenze scelte a caso.Se hai un piccolo numero di vertici che appaiono in entrambi, rimuovili da uno o dall'altro, se si rompono meno spigoli. il numero di vertici che appaiono in entrambi, mantiene il vicinato con il rapporto migliore (vertici nel vicinato/bordo rotto) e allontana l'altro.

Ora ci sono alcuni quartieri locali che sono approssimativamente localmente ottimali in quanto le ricerche di ampiezza tendono a cadere all'interno. Se la ricerca in ampiezza elimina le filiali improduttive in modo abbastanza efficace, probabilmente è abbastanza buona. In caso contrario, probabilmente vorrai raggruppare i quartieri adiacenti.

Se non è necessario che i quartieri adiacenti si raggruppino troppo, si mettono da parte i vertici raggruppati in quartieri e si ripete il processo sui dati rimanenti finché non vengono considerati tutti i vertici. Si cambia ogni identificatore di vertice in (vertice, quartiere) e il gioco è fatto: quando si seguono i bordi, si conosce esattamente quale pagina si deve afferrare e la maggior parte di essi sarà chiusa data la costruzione.

Se hai bisogno di quartieri adiacenti, dovrai tenere traccia dei tuoi quartieri in crescita. Ripeti il ​​processo precedente (scegli a caso, coltivi i quartieri), ma ora classifica i vicini per il numero di bordi che soddisfano entro il quartiere e quale frazione dei loro bordi che lasciano il quartiere si trovano in un gruppo esistente. Potresti aver bisogno di fattori di ponderazione, ma qualcosa come

score = (# edges within) - (# neighborhoods outside) - (# neighborhoodless edges outside) 

probabilmente farebbe il trucco.

Ora, questo è non a livello globale o anche a livello locale ottimale, ma questo o qualcosa di molto simile si deve dare una struttura ben localmente collegata, e dovrebbe permettere di produrre un set di copertura di quartieri che hanno relativamente alta interconnettività.

Anche in questo caso, dipende dal fatto che i rami delle prugne per la ricerca della larghezza siano o no. Se lo fa, la cosa economica da fare è massimizzare l'interconnettività locale. Se la cosa da fare non è minimizzare la connettività esterna - e in tal caso, suggerirei di raccogliere i set di ampiezza fino a una certa dimensione e di salvarli (con la duplicazione ai bordi dei set - voi Non sono gravemente limitato dallo spazio del disco rigido, vero?).

Answer 2

Si potrebbe voler guardare HDF5. Nonostante H sia per Hierarchical, può archiviare grafici, controllare la documentazione sotto la parola chiave 'Gruppi' ed è progettato per dataset di grandi dimensioni. Se capisco correttamente, i 'file' HDF5 possono essere distribuiti su più 'o' file '. Ora, HDF5 è solo una struttura dati, oltre a un set di librerie per le manipolazioni di livello basso e alto della struttura dati. In cima alla mia testa non ho idea di algoritmi di partizionamento grafico in streaming, ma aderisco all'idea che se si ottiene la struttura dei dati gli algoritmi giusti diventano più facili da implementare.

Cosa sai già del mega-grafico? Divide in modo naturale sottografi densi che a loro volta sono scarsamente connessi?Un tipo topologico del grafico sarebbe una base migliore per l'archiviazione su disco rispetto all'ordinamento spaziale esistente?

In mancanza di risposte nitide a tali domande, forse basta mordere il punto e leggere il grafico più volte per costruire le partizioni, nel qual caso si desidera solo l'I/O più veloce che è possibile gestire e il layout sofisticato delle partizioni sui nodi è bello ma non altrettanto importante. Se è possibile partizionare il grafico in sottografi che hanno anch'essi dei bordi singoli sugli altri sotto-grafici, è forse possibile rendere il problema più trattabile.

Si desidera un layout buono per BFS, ma BFS viene generalmente applicato agli alberi. Il tuo grafico ha una radice unica da cui iniziare tutti i BFS? In caso contrario, il layout per BFS da un vertice non sarà ottimale per BFS da un altro vertice.

Answer 3

Controllare questo post del blog:

"ricerca grafico in ampiezza con una mappa-ridurre algoritmo iterativo"

http://www.johnandcailin.com/blog/cailin/breadth-first-graph-search-using-iterative-map-reduce-algorithm