パス ナビゲーション グラフが必要なプロジェクトに取り組んでいます。
問題の説明: プロジェクトのコンテキストを示すために、サンプル UI はhttp://bl.ocks.org/mbostock/4063570のように なると予想されます。違いは、サイト ナビゲーション用であることです。私の問題は、バックエンドでデータを処理することです。
ユーザー パス A->B->C->D->E の場合、事前に計算したデータ形式は次のようになります。
Origin:Start:End:Level
A A B L1
A B C L2
A C D L3
A D E L4
さて、何百万ものオリジンを持つこのようなレコードが何百万もあると仮定すると、それらをグループ化し、サイズを集約してサイズの降順で並べ替え、上位 10 を取得できます。したがって、各オリジン、開始、およびレベルについて、それぞれ 10 個のレコードが必要です。したがって、4 レベルのグラフの場合、グラフ内の特定の開始ノードに対して 10.. 10^2.. 10^3.. 10^4 になります。
本当の問題: ソート後のトップ 10 では、不要な L3 と L4 をすべて取り除くことはできません。特定の起点に対して、L1 の終わりは L2 の開始点である必要があり、L2 の終了点は L3 の開始点である必要があります。このため、多くの L2 開始が L1 終了に属さず、レベルが上がるにつれて増加するという多くの記録があります。図：
A A B L1
A B C L2
A F G L2 <-- this comes in top 10 after aggregation, but start is not the end of L1 (B in this case)
試したこと: 上位 10 をソートしてスライスした後、各レベルで数百万のレコードを 1 つずつ自己結合します。レベルは 10 あります。それは計算上本当に高価です。
私が探しているもの: 一般的で安価な Map-reduce ソリューション。火傷の文脈でそれを得ることができればより良い.