さまざまな行の数値のペアを効率的に検索する

Question

N個の異なるユーザーがおり、これらのユーザーの所在地、正確にはこれらのレコードの正確なM個のレコードがあるとします。

ですから、「人1」が「人50」3回と同じ場所であることがわかります

1,50,299 
1,2,3,4,5,50,287 
1,50,299 

たとえば。 3行しかないので、ここではM = 3です。私の質問にはこれらの行のうちM個が与えられ、しきい値（つまり、人物AとBは同じ時間に閾値時間を超えています）があります。これらの共起を返す最も効率的な方法は何を示唆していますか？

これまでのところ、N行N列のテーブルを作成し、各行をループして、M行にN行のCoが発生するたびにテーブル（N、M）をインクリメントしました。明らかに、これはひどいアプローチであり、あなたがどのようにしているかに応じて0（n^2）からO（n^3）になります。任意のヒントをいただければ幸いです！

Answer 1

テーブルを作成する必要はありません。あなたの言語がそれを呼んでいるものをハッシュ/辞書/作成してください。そして、擬似コードで：あなたはサイズKの大きさのMセットを持っている場合は

answer = [] 
for S in sets: 
    for (i, j) in pairs from S: 
     count[(i,j)]++ 
     if threshold == count[(i,j)]: 
      answer.append((i,j)) 

実行している時間がO(M*K^2)になります。

big-Oを変更せずに、実際には交差するデータセットのリストをcountと平行に保つことができます。

さらに、同じアルゴリズムをmap-reduceを使用して分散して簡単に実装できます。カウントのためには、(i, j)のキーと1の値を出さなければなりません。あなたはそれらを数えます。実際にセットのリストを生成することは同様です。

Answer 2

あなたのケースの既知のコンセプトは、マーケットバスケットの分析です。この文脈では、異なるアルゴリズムが存在する。例えば、Apriori algorithmは、サイズ2のセットの特定のケースであなたのケースに使用できます。

さらに、これらのケースでは、特定のサポートと条件（あなたのケースではしきい値）をLSHとから使用して、association rules最小ハッシュも。

Answer 3

あなたはそれをスピードアップするために確率を使うことができます。各ペアを1/50の確率でチェックするだけです。それはあなたに50倍のスピードを与えます。

ペアをもう一度チェックするには、もう一度リスト全体を確認するか、賢い種類の作業を行うとさらに効率的にチェックすることができます。あなたが行くように逆インデックスの。例えば各人物の行インデックスを64ビット整数にエンコードする場合は、バイナリ検索/マージソートタイプの手法を使用して、比較する64ビット整数を調べ、ビット演算を使用して64ビット整数を比較して一致させることができます。ルックアップする他のものは、リバースインデックス、バイナリインデックス付き範囲ツリー/フェンウィックツリーです。