特定の目的地に最も近い n 個の目的地をすばやく見つけ、n 個の目的地の nxn 距離行列を計算し、2 つ以上の目的地間の距離に関連する他のいくつかの操作を実行できるようにする必要があります。
私は、グラフ DB が MySQL データベースと比較してはるかに優れたパフォーマンスを提供することを学びました。私のアプリケーションは PHP で書かれています。
SO 私の質問は - PHP アプリケーションで Graph DB を使用することは可能ですか? はいの場合、どれが最良のオプションであり、オープンソースであり、このデータをグラフ DB に保存する方法と、どのようにアクセスするかです。
前もって感謝します。
Neo4jは非常に堅牢なグラフ DB であり、柔軟な (少し複雑な場合でも) ライセンスも備えています。Blueprints API を実装しており、PHP を含むほぼすべての言語から簡単に使用できます。また、REST APIもあり、柔軟性に優れており、PHP から使用する良い例が少なくとも1 つあります。
持っているデータに応じて、保存する方法はいくつかあります。
ポイントがすでに特定のパスを介して互いに接続されている「ルート」データがある場合 (つまり、あるポイントから別のポイントに直接ジャンプすることはできません)、各ポイントをノードにして、その間の接続を作成するだけです。ルート内のポイントはノード間のエッジであり、それらのエッジのプロパティとして距離があります。これにより、古典的な「巡回セールスマン」のような問題のようなグラフが得られます。ノード間の距離の計算は、重み付けされた幅優先検索を実行するだけの問題です (最短経路が必要であると仮定します)。
データセットを使用して場所を移動できる場合は、完全に接続されたグラフが作成されています。明らかに、これは大量のデータであり、宛先を追加すると 2 次的に増加しますが、グラフ DB はおそらくリレーショナル DB よりもこれを処理するのに適しています。距離を保存するには、グラフにノードを追加するときに、そのプロパティの 1 つとして事前に計算された距離を使用して、既存の各ノードにエッジも追加します。次に、ノードのペア間の距離を取得するには、単純にそれらの間のエッジを見つけて、その距離プロパティを取得します。
ただし、完全に接続されたノードが多数ある場合は、それらのノードの座標を保存し、必要に応じて距離を計算し、必要に応じて結果をキャッシュして高速化する方がよいでしょう。
最後に、Blueprints API とそのスタック内の他のツール ( GremlinやRexterなど) を使用すると、互換性のあるグラフ データベースをスワップ イン/アウトできるはずです。 Cassandra / Hadoopクラスター上でTitanを使用するようなものです。
実際には、データベースについてはインデックスほどではありません。私はMongoDBの地理空間インデックスと検索（ドキュメントDB）を使用しました。これは、指定された座標に最も近い複数の要素を見つけるために設計された地理インデックスを備えており、良好な結果が得られます。それでも-単純なクエリ（最も近いものを見つける）のみを実行し、インデックスがRAMに収まらない場合は少し遅くなります（座標を含む8mlnの場所でgeonames DBを使用し、VMでクエリごとに0.005〜2.5を取得しました- 1. hddオーバーヘッド2.おそらくインデックスがRAMに収まりませんでした）。
はい、グラフ データベースは、MySQL や Postgres の拡張機能よりも優れたパフォーマンスを提供します。非常に洗練されたものの1 つはOrientDBです。バイナリ プロトコルを使用する PHPのベータ実装と、トランスポート層としてHTTP を使用する別の実装があります。
コード例については、Alessandro ( odino.orgから)がDijkstra のアルゴリズムの実装と、それを OrientDB で使用して都市間の最小距離を見つける方法の完全な説明を書きました。