Карта Сокращение алгоритмов на терабайтах данных?

Question

Этот вопрос не имеет ни одного «правильного» ответа.

Я заинтересован в запуске Map Сократите алгоритмы, на кластере, на терабайтах данных.

Я хочу узнать больше о времени работы указанных алгоритмов.

Какие книги следует читать?

Я не заинтересован в настройке карты Уменьшение кластеров или выполнение стандартных алгоритмов. Я хочу строгое теоретическое лечение или время работы.

EDIT: проблема заключается не в том, что карта уменьшает время изменения изменений. Проблема заключается в том, что большинство алгоритмов не распределяют хорошо, чтобы преобразовать структуры сокращения. Меня интересуют алгоритмы, которые работают на карте, уменьшают рамки.

Answer 1

Технически, в анализе времени выполнения MapReduce нет реального различия по сравнению со стандартными алгоритмами. MapReduce по-прежнему является алгоритмом, как и любой другой (или, в частности, класс алгоритмов, которые происходят в несколько этапов, с определенным взаимодействие между этими шагами).

Время выполнения задания MapReduce по-прежнему будет масштабироваться, как прогнозируется обычный алгоритмический анализ, когда вы учитываете разделение задач на нескольких машинах, а затем находите максимальное индивидуальное машинное время, необходимое для каждого шага.

То есть, если у вас есть задача, для которой требуются операции M-карты и операции сокращения R, работающие на N машинах, и вы ожидаете, что средняя операция карты займет время и среднее время работы r, тогда вы Ожидаемое время выполнения: ceil(M/N)*m + ceil(R/N)*r Время выполнения всех заданий.

Прогнозирование значений для M, R, m и r - все, что может быть выполнено при нормальном анализе любого алгоритма, который вы подключаете к MapReduce.

Answer 2

Есть только две книги, которые я знаю, что опубликованы, но есть еще в работах:

Pro hadoop и Hadoop: The Definitive Guide

Из них Pro Hadoop является больше начинающих книги, в то время как Окончательное руководство предназначено для тех, кто знает, что такое Hadoop.

У меня есть The Definitive Guide и думаю, что это отличная книга. Он содержит хорошие технические подробности о том, как работает HDFS, а также охватывает ряд смежных тем, таких как MapReduce, Pig, Hive, HBase и т. Д. Следует также отметить, что эта книга была написана Томом Уайтом, который участвовал в развитие Hadoop на время, и теперь работает на cloudera.

Что касается анализа алгоритмов на Hadoop, вы можете взглянуть на тестеры сортировки TeraByte. Yahoo сделали запись о том, как Hadoop выполняет для этого конкретного теста: TeraByte Sort on Apache Hadoop. Эта статья была написана в 2008 году.

Более подробную информацию о результатах за 2009 год можно найти here.

Answer 3

Существует отличная книга об алгоритмах интеллектуального анализа данных, применяемых к модели MapReduce.

Она была написана два Стэнфордский профессурой и, если можно бесплатно:

http://infolab.stanford.edu/~ullman/mmds.html