DAG = gerichteter azyklischer Graph; roots = Vertices ohne eingehende Kanten.Graphendatenbanken mit Lokalität
Ich habe eine DAG größer als verfügbaren RAM, so dass ich eine Festplatte-basierte Graph-Datenbank benötigt, um damit zu arbeiten.
Meine DAG ist flach: Ich habe Milliarden von Wurzelknoten, aber von jedem Knoten sind nur Dutzende von Knoten erreichbar.
Es ist auch nicht gut verbunden: Die Mehrheit der Knoten haben nur eine eingehende Flanke. Daher haben für einige Wurzelknoten erreichbare Untergraphen normalerweise nur sehr wenige gemeinsame Knoten.
So kann meine DAG als eine große Anzahl von kleinen Bäumen gedacht werden, von denen nur wenige sich schneiden.
Ich muss die folgenden Abfragen auf meine DAG in Massenzahlen durchführen: Bei einem Root-Knoten, erhalten Sie alle Knoten von ihm erreichbar.
Es kann als eine Batch-Abfrage gedacht werden: gegeben einige tausend Wurzelknoten, zurück alle Knoten von dort erreichbar.
Soweit ich weiß, gibt es Algorithmen zur Verbesserung der Festplattenspeicherort für Graphen. Drei Beispiele sind:
- 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
Es scheint auch, es gibt ältere Generation Graph-Datenbanken, die nicht Graph Ort nutzen. zum Beispiel ein beliebtes Neo4j Graph-Datenbank:
http://www.ibm.com/developerworks/library/os-giraph/
Neo4j basiert auf Datenzugriffsmethoden für Graphen ohne Datenlokalität unter Berücksichtigung, und die Verarbeitung von Graphen bringt meist Zufallsdaten Zugang. Bei großen Grafiken, die nicht im Speicher abgelegt werden können, wird der Zugriff auf den Zufallsdatenträger zu einem Leistungsengpass.
Meine Frage ist: Gibt es Graphen-Datenbanken, die für meine Arbeitslast gut geeignet sind?
Unterstützung für Win64 und eine Möglichkeit, mit der Datenbank von etwas anderem als Java zu arbeiten, ist ein Plus.