Как выбрать случайные (небольшие) выборки данных с помощью Map / Reduce?

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

Псевдокод: 

for each row 
  if row matches condition
    put the row.id in the bucket if the bucket is not already large enough

Вы делали что-нибудь подобное? Есть ли какой-нибудь известный алгоритм?

Образец, содержащий последовательные строки, также достаточно хорош.

Спасибо.

3 9
hadoop mapreduce random-sample hbase

3 ответа:

Подход Карла работает просто отлично, но мы можем значительно уменьшить объем данных, производимых картографами.

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

В установочной части каждого картографа создайте приоритетную очередь ; a куча Fibonnacci - хороший выбор для этого. Мы будем использовать поплавки в качестве приоритетов; если у вас есть огромное количество данных, дубли могут быть более подходящими, чтобы избежать связей. Для каждой строки, которая соответствует вашему условию, вставьте эту строку в очередь приоритетов с произвольно выбранной точкой с плавающей точкой между 0 и 1 в качестве приоритета. Если у вас есть более K вещей в вашей очереди, удалите самый ценный элемент (это противоречит терминологии стандартного Fibonnacci куча).

Наконец, в конце картографа, выделите все, что находится в вашей очереди. Для каждого элемента, который вы выделяете, используйте в качестве ключа приоритет в виде FloatWritable и некоторое представление соответствующей строки в качестве значения (идентификатор строки или, возможно, все содержимое строки). Вы будете выдавать толькоK значений для каждого картографа (или меньше, если в этом картографе было меньшеK совпадающих строк).

В вашем единственном редукторе Hadoop будет автоматически сканировать ключи в порядке от самого низкого до самый высокий. Выделите строки, соответствующие первымK ключам, которые вы видите (самый низкийK ), а затем завершите работу.

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

8

Картографы: Выведите все квалифицирующие значения, каждое со случайным целочисленным ключом.

Одиночный редуктор: Выведите первые N значений, выбросив ключи.

Сортировщик рандомизирует порядок вывода картографа для вас. Вы не знаете, сколько квалификационных значений найдет сопоставитель, поэтому каждый сопоставитель должен вывести все квалификационные значения из своего раздела.

В общем, мне нравится создавать простые инструменты для картографирования / редуктора, такие как этот, которые используют как можно больше машин Hadoop; я в конечном итоге их можно повторно использовать в различных задачах.

11

Подход Bkkbrad, возможно, наиболее эффективен в том, что количество записей, отправленных из каждого картографа, составляет (не более) K. с другой стороны, обратите внимание, что он предполагает, что сама выборка (т. е. K элементов) помещается в память одного редуктора.

Когда это не так, вы можете просто использовать полностью распределенный подход, где каждая совпадающая строка назначается отображателем случайным целым числом в {1,.., K} и затем фаза уменьшения выбирает один элемент для каждого ключа (Также см. этот вопрос ). Проблема с этим подходом, однако, заключается в том, что может случиться так, что случайно ни одна строка не будет назначена определенным ключам, и в этом случае конечный образец будет иметь меньше K элементов. Даже если это произойдет с малой вероятностью, если K намного меньше общего числа строк N, это произойдет с постоянной вероятностью, если K-постоянная часть N (скажем, когда K=N/3).

Решение, которое работает следующим образом: предположим, что у нас есть B ведер и генерируем случайный упорядочение элементов сначала путем размещения каждого элемента в случайном ведре, а затем генерации случайного упорядочения в каждом ведре. Элементы в первом ковше считаются меньшими (по отношению к порядку), Чем элементы во втором ковше и так далее. Затем, если мы хотим выбрать выборку размера K, мы можем собрать все элементы в первых J ведрах, если они в целом содержат число элементов t меньше K, а затем выбрать оставшиеся K-t элементов из следующего ведра. Вот Б является параметром таким, что N/B элементов помещаются в память. Ключевым аспектом является то, что ведра могут обрабатываться параллельно.

Mapper: вывести все квалифицирующие строки, каждая со случайным ключом (j, r), где j-случайное целое число в {1,..,B} и r-случайный поплавок. Кроме того, следует отслеживать количество элементов с ключом меньше j (для 1

Перемешивание: разбиение по j и вторичная сортировка по r.

Редуктор: рассмотрим ковш j и предположим, что редуктор знает, сколько элементов в корзинах меньше j и сколько в корзине j (путем агрегирования информации, полученной картографами). Если количество элементов в ведра меньше или равен J-это меньше или равно K, вывести все элементы в ведерко Дж; если число элементов с ведром строго меньше J Т Я не знаю более простого решения этой проблемы, но было бы неплохо, если бы оно было.

Вы можете найти более подробную информацию здесь, в моем блоге.

2