-1

かなり大きなデータ セットが 2 つあるとします。1 つ目は「Base」と呼ばれ、2 億行のタブ区切り行が含まれ、2 つ目は 1000 万行の同様のデータがタブ区切り行である「MatchSet」と呼ばれます。

次に、Match(row1, row2) という任意の関数もあり、Match() には基本的に、row1 (MatchSet から) を見て、それを row2 (Base から) と比較し、何らかの方法で類似しているかどうかを判断するためのヒューリスティックが含まれているとします。 .

Match() で実装されたルールがカスタムで複雑なルールであり、単純な文字列の一致ではなく、独自のメソッドが含まれているとしましょう。今のところ、Match(row1,row2) は疑似コードで記述されているため、別の言語での実装は問題ではありません (ただし、現在は C++ で実装されています)。

線形モデル、つまり 1 つの巨大なプロセッサで実行されるプログラムでは、MatchSet から各行を読み取り、Base から各行を読み取り、Match() を使用して一方を他方と比較し、一致統計を書き出します。たとえば、MatchSet からの X レコードは強い一致、MatchSet からの Y レコードは弱い一致、MatchSet からの Z レコードは一致しないなどをキャプチャできます。また、検査のために、強い/弱い/非値を別のファイルに書き込みます。別名、ある種のネストされたループ:

for each row1 in MatchSet
{
    for each row2 in Base
    {
        var type = Match(row1,row2);
        switch(type)
        {
            //do something based on type
        }
    }
}

これらの比較をバッチ ジョブとして短時間で実行する方法として、Hadoop ストリーミングを検討し始めました。ただし、このタイプの問題のマップ削減パラダイムについて理解するのに少し苦労しています。

この時点で、hadoop から単一の入力を取得し、マッピング関数を使用してデータをクランチし、結果を出力して削減する方法をかなり明確に理解しています。ただし、2 セットのレコードを比較する「入れ子になったループ」アプローチは、私を少し混乱させます。

私が解決策に最も近いのは、基本的に、2億個のレコード間で1,000万個のレコードを並行して比較する必要があるため、2億/ nノード*ノードあたり1,000万回の反復です。それはこれを行うための最も効率的な方法ですか？

4

3 に答える 3

0

これは古い質問ですが、単一のストリーム ジョブが 200M * 10M の Match() 計算を行うと仮定すると、提案されたソリューションは正しいです。(200M / N) * 10M の計算の N バッチを実行することにより、N 倍の速度向上を達成しました。マップ フェーズで計算を行い、結果をしきい値処理して、Strong/Weak/No Match reducer に調整することで、結果を収集して出力用に別のファイルにすることができます。

追加の最適化を利用できる場合は、単一ストリーム バージョンと並列バージョンの両方に適用したいと考えています。例には、200M * 10M 未満の計算を行う必要があるようにするためのブロックや、10M の一致セットのアルゴリズムの定数部分の事前計算が含まれます。

于 2013-09-16T16:19:25.527 に答える
0

Section 3.5 - Relational Joins論文「Data-Intensive Text Processing with MapReduce 」を確認してください。詳しくは書いていませんが、参考になれば幸いです。

于 2011-11-28T16:07:15.410 に答える