次の問題を効率的に処理するための特定のデータ構造/アルゴリズムを知っている人はいますか?
Aセットとセットのセットが与えられた場合、S = {X,Y,Z..}A と S のすべてのセットの間の交差のサイズを計算したいと思います。それらのほとんどが互いに素ではない、つまり共有数であるという事実を利用します。
例: と が与えられたA = {1,2...10}場合、X = {1,3,4,5,7}と、、 、およびの交点を計算し、結果を合計する 方Y = {2,4,5,7,9,10}が効率的です。AX intersect YAX - X intersect YAY - X intersect Y
実際の例としては、テキストの一部を共有する大量のドキュメント セットでキーワードの出現回数を見つけることができます (合計ではなく、ドキュメントごとです)。
Map-Reduce との唯一の違いは、ドキュメントがテキストの一部を共有し、それらの部分を 1 回だけ解析する必要があることです。
これが助けになる場合、私が現在問題について推論している方法は、ノードが重なり合っている領域であり、そのO(n)トラバーサルが A と S のすべての要素の間の交差のサイズを与えるグラフ/ツリーです。私が直面している問題使用するノードの最適なセットを見つける方法です。しかし、それに対する既製のソリューションがすでにあるかもしれません。