最小マップリデュースアルゴリズム

MapReduceは、ビッグデータ、すなわちテラバイトまたはそれ以上の規模の巨大なデータセットに対する支配的な並列計算パラダイムとなりました。理想的には、MapReduceシステムは参加するマシン間で高い負荷分散を達成し、各マシンでのスペース使用量、CPUおよびI/O時間、ネットワーク転送を最小限に抑えるべきです。これらの原則はMapReduceアルゴリズムの開発を導いてきましたが、前述の指標に対する厳しい制約を同時に強制することには限られた重点しか置かれていません。この記事では、最小アルゴリズムという概念を提示します。これは、小さな定数因子まで、複数の側面での最良の並列化を保証するアルゴリズムです。基本的なデータベース問題のセットに対する優雅な最小アルゴリズムの存在を示し、広範な実験によってその優れた性能を実証します。