0

互いに近い2GBのデータセット内のすべてのレコードを見つけるために、マップ削減プログラムを実装しようとしています(各レコードとその隣接のようなものが出力されるはずです)。近いとは、ユークリッド距離を意味します。データセットでは、各レコードに x 座標と y 座標があります。誰かがこれを行うための直感を教えてくれませんか。マップは各レコードを発行する必要があり、reduce は入力されたリスト内の各エントリに対して単純に double for ループを実行して隣人を見つけることができますが、実装が非常に遅いため、これに対するより良い解決策はありますか? 前もって感謝します。

map(rid,r):
 emit(key,r)

reduce(key,lst=[r1,r2....]):
 for elm1 in lst:
  for elm2 in lst:
   if elm2 is in range of elm1:
    process(elm1,elm2)

プロセス関数は単に elm2 を隣人として配置するか、elm1 を mongodb データベースに配置します。私のmongodbデータベースの各レコードは次のように構成されています

レコード 'R' | レコード 'R' の隣接リスト

4

1 に答える 1

1

バケット内のレコードにインデックスを付けることで、実装を高速化できる場合があります。すべてのレコードがグリッド [0,100] x [0, 100] にあるとします。99 個の x-バケット [0, 1), [1, 2), ... [99, 100] と 99 個の y-バケットを作成します。所定のレコード [x1, y1] と距離 d について、x バケット [x1 - d - 1] から [x1 + d + 1] と y バケット [y1 - d - 1] から [ y1 + d + 1]、THEN は、結果セットのポイントに対して [x1, y1] のユークリッド距離をテストします。

于 2013-04-09T01:03:10.163 に答える