8

私の目的は、道路網の最短経路アルゴリズムを作成することです。

現在、私のアーキテクチャは次のようなものです。PostGIS 対応の PostgreSQL データベースにすべてのデータを保存しています。100,000 のエッジ (ウェイ) を持つテーブルで 3 秒未満しかかからない 1 つを実行しSELECT * FROM ways、その後、既にメモリに存在するグラフに (Java、Ruby、または何かベースの) 最短パス アルゴリズムを適用します。2 番目の操作は、100,000 個のエッジを持つグラフで約 1.5 秒かかる場合があります。

したがって、次のものが必要です。

  • データベースからすべてのウェイをメモリにロードしてグラフを作成するのに 2 ～ 3 秒かかります (ノードはウェイ (エッジ) を持つ 1 つのテーブルに格納されます)。
  • すでにメモリ内にあるグラフの最短パスを計算するには、1 ～ 1.5 秒かかります。

これは、pgRouting が行うことと非常によく似ています (私の知る限り、C Boost を使用してグラフをメモリに保存します)。ただし、pgRouting は、同じデータセットで最短パスを計算するのに合計で約 2 秒かかります (はい、高速ですが、これは私にとってはブラック ボックスなので、独自のものが必要です)。

しかし最近、Graph データベースと Neo4j について知りました。彼らのサイトでは、「数百万の道路とウェイポイントのグラフでこれらの計算を1秒未満の速度で実行できるため、多くの場合、K / Vストアを使用してインデックスを事前計算する通常のアプローチを放棄して、ライブ条件に適応し、高度にパーソナライズされた動的な空間サービスを構築する可能性を備えたクリティカル パスにルーティングを配置します。」

質問は次のとおりです。グラフ データベースは、特定の問題で高速になりますか?

問題には次の特性があります。

  • データベースは 1 つのテーブル (ウェイ) で構成されます。
  • データベースへの唯一のクエリは、すべてのウェイをメモリに取得することです (グラフを作成するため)。
  • スケーラビリティは必要ありません。つまり、グラフが大きくならない可能性があります。
4

4 に答える 4

3

グラフ データベースのブレークスルーは、パフォーマンスだけでなく、コンセプトに関するものです。ルーティング アルゴリズムは、単一のリレーショナル グラフ(つまり、リンクがすべて同じタイプのグラフ) を処理しますが、グラフ データベースでは、複数のリレーショナル グラフがあります。

これにより、特定の種類のエッジのみを取るノード間の最短パスを計算したり、別の種類のエッジを回避したりできます。

詳細については、グラフ db の背後にある代数とパイプの概念について読む必要があります。

グラフ データベースから始めるには、thinkerpopプロジェクトを強くお勧めします。

于 2013-04-11T12:21:00.343 に答える
3

Neo4j などのグラフ データベースを使用している場合は、車輪を再発明する必要はありません。これには多くの最短経路アルゴリズムが組み込まれており、特定の道路、一方通行、道路のスコアなどで速度制限を考慮する必要がある場合に備えて、複雑さを処理できるように設計されています。回、または100回。合計計算時間を 100,000 ウェイで 3 秒と考えると、1M ウェイでは数分、Neo4j では応答はミリ秒になります。

于 2013-01-23T03:19:43.307 に答える
1

私は「グラフ」データベースの経験はありませんが、あなたの質問から判断すると、いくつかのことを念頭に置いています。

まず、簡単な答えは「そのようなグラフデータベースを作成し、ソリューションとのパフォーマンス比較を行う」です。メモリ使用量、実行時間（速度）、CPU使用率、および/またはその他のメトリックを測定できます。それはあなたの決定をするのに十分なデータをあなたに提供するでしょう。

私の他のアドバイスはあなたの方法を修正することです。説明した3つの問題プロパティ（1つのテーブル、すべてのパスのロード、スケーラビリティの必要なし）は、現在のドメインには適用されますが、グラフデータベースのドメインには適用されません。これはまったく異なるプログラミングパラダイムであり、これらの特別な種類のデータベースのドメインに合わせてメソッドを調整および適合させる必要がある場合があります。非標準環境（グラフデータベースなど）で標準アプローチを適用している場合、パフォーマンスやその他の種類の比較を行うのは不合理です。

要約：問題をグラフデータベースの用語に変換し、それに応じてモデル化します。その後、2つのソリューションのパフォーマンスを比較します。

私の賭けは、グラフデータベースに合わせて問題を適切に翻訳およびモデル化したと仮定すると、パフォーマンスが向上することです。「store-read-sort」の従来のアプローチは単純ですが、積極的に最適化しない限り、それほど効果的ではありません。

于 2011-08-01T11:19:14.627 に答える
0

グラフ データベースはおそらく、最初はすべてのデータをメモリにロードしませんが、時間の経過とともに、優れたデータベースは非常に大きなデータセットを処理するように設計されているためです。ただし、データがそこにあると、グラフ データベースは、リレーショナル データベースがリンクを走査するよりも少ない作業を行う必要があります。これは、B ツリー インデックスと (場合によっては) 結合テーブルを使用するのではなく、ID を使用して関連オブジェクトに直接アクセスできるためです。したがって、ノードとエッジがキャッシュされると、より高速になります。

于 2011-08-05T22:12:31.027 に答える