1

比較的小さな互いに素なグラフを多数含むグラフ データセットがあります。特定の検索条件に一致する一連の頂点から到達可能なすべての頂点を見つける必要があります。次のクエリを使用します。

FOR startnode IN nodes
    FILTER startnode._key IN [...set of values...]
    FOR node IN 0..100000 OUTBOUND startnode edges
        COLLECT k = node._key
        RETURN k

クエリは正しい結果を返しますが、非常に低速です。これは、Arango が実際に同じサブグラフを何度もトラバースすることになるためです。たとえば、次のサブグラフがあるとします。

a -> b -> c -> d -> e

フィルター条件によって頂点 a と c が選択されると、Arango は a と c から始まる 2 つの独立したトラバーサルを実行することになります。これらのトラバーサルの両方で頂点 d と e を訪問するため、時間が無駄になります。異なるトラバーサル間で頂点の一意性がチェックされないため、uniqueVertices オプションを追加しても役に立ちません。

パフォーマンスへの影響を確認するために、追加のルート ドキュメントを作成し、そこからフィルターで見つかったすべてのドキュメントへのリンクを追加しました。

FOR startnode IN nodes
    FILTER startnode._key IN [...set of values...]
    INSERT { _from: 'fakeVertices/0', _to: startnode._id } IN fakeEdges

次のクエリは、同じ結果を生成しながら、元のクエリよりも 4 倍速く実行されます。

FOR node IN 1..1000000 OUTBOUND 'fakeVertices/0' edges, fakeEdges
    OPTIONS { uniqueVertices: 'global', bfs: true }
    COLLECT k = node._key
    RETURN k

残念ながら、作成にはさらに時間がかかるため、すべてのクエリに対して偽の頂点/エッジを作成することはできません。

私の質問は次のとおりです。Arango は、特定のクエリですべてのトラバーサルでアクセスされた頂点の一意性を保証する方法を提供しますか? そうでない場合、上記の問題を解決するためのより良い方法はありますか?

4

1 に答える 1

2

私が理解していることから、これがuniqueVerticesオプションの目的ですが、ステートメントの反復ごとに、その開始ノードFOR ...からのトラバーサルで頂点が一意であると見なされます。ステートメント内の他のノードで発生した他のトラバーサルについては知りません。毎回多くの頂点をトラバースするように見えますが、これは新しい開始ノードごとに発生します。FOR ...

これを壁に投げつけて貼り付くかどうかを確認するだけですOPTIONSが、元のクエリに追加して 2 つのクエリを組み合わせるとどうなるでしょうか。

FOR startnode IN nodes
    FILTER startnode._key IN [...set of values...]
    FOR node IN 0..100000 OUTBOUND startnode edges
        OPTIONS { uniqueVertices: 'global', bfs: true }
        COLLECT k = node._key
        RETURN k

また、エッジ コレクションを指定する代わりに、名前付きグラフを強くお勧めします。はるかに柔軟であるだけでなく、最短経路の計算も使用できるため、ここで役立つ場合があります。

于 2020-06-11T23:22:38.977 に答える