DAG = grafico aciclico diretto; radici = vertici senza bordi in entrata.Database di grafici che utilizzano la località
Ho un DAG più grande della RAM disponibile, quindi ho bisogno di un database grafico basato su disco per lavorare con esso.
Il mio DAG è poco profondo: ho miliardi di nodi radice, ma da ciascun nodo sono raggiungibili solo decine di nodi.
Inoltre non è ben collegato: la maggior parte dei nodi ha solo un bordo in entrata. Quindi per ogni coppia di nodi radice i sottografi di solito hanno pochissimi nodi in comune.
Quindi il mio DAG può essere considerato come un grande numero di piccoli alberi, solo alcuni dei quali si intersecano.
Ho bisogno di eseguire le seguenti query sul mio DAG in grandi quantità: dato un nodo radice, ottenere tutti i nodi raggiungibili da esso.
Può essere pensato come una query batch: date alcune migliaia di nodi radice, restituire tutti i nodi raggiungibili da lì.
Per quanto ne so, esistono algoritmi per migliorare la posizione di archiviazione su disco per i grafici. Tre esempi sono:
- http://ceur-ws.org/Vol-733/paper_pacher.pdf
- http://www.cs.ox.ac.uk/dan.olteanu/papers/g-store.pdf
- http://graphlab.org/files/osdi2012-kyrola-blelloch-guestrin.pdf
Sembra inoltre ci sono più anziani database del grafico generazione che non utilizzano grafico località. per esempio un popolare database grafico Neo4j:
http://www.ibm.com/developerworks/library/os-giraph/
Neo4j basa su metodi di accesso ai dati per i grafici senza considerare dati frazione, e l'elaborazione di grafici comporta principalmente dati casuali accesso. Per i grafici di grandi dimensioni che non possono essere archiviati in memoria, l'accesso casuale al disco diventa un collo di bottiglia per le prestazioni.
La mia domanda è: ci sono database grafici adatti al mio carico di lavoro?
Il supporto per Win64 e la possibilità di lavorare con il database da qualcosa di diverso da Java è un vantaggio.