CPU /メモリに結合された大規模なグラフのための最善のデータ構造

Question

私は学問プロジェクトに取り組んでいます：大きな、重み付き有向グラフで最短経路を見つけるためのライブラリを書く。

仕様は、

• 例示的なデータセットは、ノード当たり5.68エッジの平均1500個の頂点のグラフです。仕様は最大20,000ノードまで変化します。

• また、私はCPU /メモリー境界の環境で働いています：Android。

• エッジの重みは自明ではなく、コストもかかりません。グラフの可変状態に依存します。

• オフラインで作業する必要があります。

私はいくつかの困難に直面：私は、グラフのデータを格納retriveし、更新するための効率的な方法を必要とする

• を。私は、Javaクラス、ヒープ上の大きなカスタムJavaオブジェクト、または何からのクエリでSQLiteオブジェクトを使用する必要がありますか？私はこれが最もパフォーマンス重視の側面だと思います。

• 私はある種の短い経路アルゴリズムを実装する効率的な方法が必要です。すべての重みが正の値なので、Dijikstraアルゴリズムを訪問先ノードのコンテナとしてArrayListを適用する必要がありますか？

• これはNDKを使用する良いケースですか？タスクはCPUを大量に消費しますが、メモリに頻繁にアクセスするので、私はそうは思わないが、私は貢献することができます。

• リソースは不足しており、RAMが不十分であり、ディスクが低速であり、CPUが貴重であることを常に忘れないでください。

何かアドバイスはありウェルカム、歓声:)私はいくつかのクラウド・コンピューティング・サービスをAQUIREとAndroidアプリがそれと通信できるようにすることをお勧めこれらの多くのノードに対して

Answer 1

。
AmazonのCloud上のHadoopのMapReduceについて、Mahoutなどの多くのグラフフレームワークがあり、それは本当に高速です。
さらにノードとエッジがある場合は、少なくとも非常に拡張性があります。