0

ポイントからの距離が最も短い巨大なデータセットから k 個のオブジェクトを見つける mapReduce ジョブを作成しています。

私のマッパーでは、そのデータ ブロックの最小距離を持つ k オブジェクトのみを報告したいと考えています。このように、キーが距離で、値が object_id であるデータのブロックごとに k 中間 (キー、値) があります。したがって、私の reducer() では、k 個の最低値を簡単に処理して要約できます。

マッパー クラスの 1 つのデータ ブロックのポイントからの距離が最も短い k オブジェクトの中間のキーと値のペアのみをレポートする方法が思い浮かびませんか?

そのデータ ブロック内のすべての入力データの (distance,obj_id) を中間のキーと値のペアとして返し、レデューサー クラスでそれを減らして同じ結果を得ることができることを私は知っています。しかし、k << (各データ ブロック内のデータ数) と、すべてではなく k 個の中間キー値のみを報告することで、データ転送/シャッフルの量を大幅に削減できます。

どんな助けでも大歓迎です

ありがとう

4

1 に答える 1

2

k が小さい (この数のオブジェクトをメモリに収めることができる) と仮定すると、これは十分に簡単なはずです。

  • 計算された距離 (float/double?) と object_id (Text?) の 2 つのインスタンス変数を含むラッパー/コンテナー オブジェクトを作成します。
  • 値の固定セットを維持する方法はいくつかありますが、この例では (ラッパー オブジェクト タイプの) TreeSet を使用します。
  • ラッパー オブジェクトが Comparable インターフェイスを実装していることを確認するか、または TreeSet が順序を決定するために使用できる Comparator 実装を作成します。実装は最初に距離インスタンス変数を比較し、それらが同じ場合はオブジェクト ID を比較する必要があります (これは興味深い質問につながります - 最小の 10 個の値を保持したいが、距離が最も小さい値が 20 個ある場合、どの 10 個を保持したいですか?)
  • マッパーで値を処理するときに距離値を計算し、ツリーセットのサイズが K より小さいか、距離がセットのテール値の距離よりも小さい場合は、この距離と obj_id のペアを追加します (新しいインスタンスを作成するかのいずれか)。セットのサイズが k より小さい場合はラッパーの
  • マッパーの cleanup メソッドで、値のツリー セットを一度に 1 つずつ出力します。
于 2012-07-24T01:25:43.320 に答える