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

Question

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

псевдокод:

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

Ты сделал что-то подобное? Есть ли хорошо известный алгоритм?

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

Спасибо.

Answer 1

Mappers: Выведите все подходящие значения, каждое со случайным целочисленным ключом.

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

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

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

Answer 2

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

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

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

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

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

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

Answer 3

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

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

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

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

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

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

Я не знаю более простого решения этой проблемы, но было бы неплохо, если бы он был.

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