java - Javaでのグラフのスペース効率の良い表現?

Question

ノードがペアでラベル付けされ（現在これには String[] を使用）、他のノードに任意にリンクできる無向グラフが必要です。タイプ Hashtable から始めました。これは私にとって十分なスペース効率ではないことがわかりました.60,000ノード程度（最終的にはその数をはるかに超える）にするつもりです.

メモリ効率を高めるために、この種のグラフをどのように実装すればよいですか? 代わりに、ある種のリレーショナル データベースを検討する必要がありますか?

Answer 1

スペース効率が優先される場合は、グラフ操作の時間効率を犠牲にして、ハッシュテーブルを廃止できます (ノードのラベル付きリンクを格納するために使用していると思います)。配列に切り替えるだけで、グラフ操作でラベル値を比較するコストが発生します。

public class Node {
    private Links[] links;

    // ... the ops ...

    public static final class Link {
        String label;
        Node   target;
    }
}

メモリ使用量をさらに絞り込み、ラベルのスペースが限られている場合 (つまり、ラベルは特定のノードに対して一意ではありません。たとえば、「親」は何度も発生するラベルです)、フライウェイト パターンLabelごとにカスタム クラスを使用することを検討してください。のインスタンスを複製しないでください。String

Answer 2

あなたの主な関心事は、シリアル化されたときのディスク上のサイズですか、それともメモリ内のサイズですか?

メモリ内のサイズが気になる場合、および各ノードを同時にメモリ内に保持する必要がない場合は、db4o での透過的なアクティブ化などを使用して、ある種の遅延読み込みを使用することを検討することをお勧めします。

Answer 3

継続的なスケーラビリティが必要な場合は、Neo4Jなどの既存のグラフデータベースの使用を検討してください。このデータベースは、記述したはるかに大きなグラフ（数百万または数十億の関係）を処理できます。約2500万ノードのグラフに使用しましたが、良い結果が得られました。