1

100k ノードと 500k エッジを持つ有向グラフがあるとしましょう。それらから 15k ノードは「重要」です。1 つの特定のノードから始まる 100 個の最も近い「重要な」ノードを見つける必要があります。

開始ノードから他のすべてのノードまでの距離を見つける Dijkstra アルゴリズムを C# で実装しました。次に、「重要な」ノードを距離でソートし、最初に 100 を返します。これには約 1 秒かかります。

ここで、サーバー側 (Linux) で同じことを行う必要があり、おそらく多くの同時クエリと異なる開始ノードを使用します。私は node4j グラフ データベースを試しました。開発者と相談した後、10 ～ 20 秒で同じことを行うソリューションが得られました (実際、長さ制限なしでパスを計算すると、約 10 分かかります)。neo4j はすべての最短経路を保存し、私の C# 実装は距離のみを保存するため、非常に時間がかかります。neo4j で高速化する唯一のオプションは、自明ではない拡張機能を作成することです。

質問は次のとおりです。Linuxサーバーにインストールでき、そのようなクエリを高速に実行できるグラフデータベース（非商用）はありますか？ウィキペディアのリストからすべてのグラフ データベースをチェックしましたが、適切なものは見つかりませんでした。

もう 1 つのオプションは、Java で同じアルゴリズムを実装し、グラフの共有コピーを保存し (どのように?)、これらのクエリに応答するサービス (Tomcat?) を作成することです。しかし、私は何か準備ができているほうがいいです...

4

2 に答える 2

2

これを行うための Neo4j 拡張機能を作成することは、あなたが考えるほど悪くはありません。

例については、こちらを参照してください: http://maxdemarzi.com/2012/11/26/extending-neo4j/

そして、これは A* アルゴリズムを使用して「カスタム」パスファインディングを行います: http://maxdemarzi.com/2012/11/27/pathfinding-with-neo4j-unmanaged-extensions/

于 2013-03-28T04:47:02.670 に答える
1

これは、@MaxDeMarzi が提供した回答への賛辞として意図されています...

あなたのC＃実装は、（1）開始ノードから他のすべてのノードまでの距離を見つける、（2）「重要な」ノードを距離でソートする、（3）最初に100を返す、と述べています。

効率を改善するために、代わりにこのようなことをすることができますか?

top = 100

次に、Dijkstra が新しいノードへの最短パスを見つけるたびに:

if (isImportant(node)) resultSet.add(node,distance)
if (resultSet.size() >= top) return resultSet

これにより、興味のないノードへのパスが見つからなくなります

于 2013-03-28T10:26:36.730 に答える