Группировка коллекции с пороговой фильтрацией

Question

Я пытаюсь придумать алгоритм, чтобы сделать следующее на карте уменьшить. Я получаю кучу объектов и идентификаторы пользователя владельца. Другими словами, я получаю кучу пар:

(object, uid) 

Я хочу, чтобы в конечном итоге со списком пар (object,count), где count относится к числу раз объект происходит в списке. Проблема заключается в том, что мы должны были бы отфильтровать все следующим образом:

1. Мы должны включать только пары объектов таким образом, что объект повторяются по крайней мере n различных жидкостей.

2. Мы должны включать только такие объекты, чтобы общее количество повторений повторений составляло не менее m.

Объекты и пользователи представлены в виде целых чисел. Проблема в том, что было бы тривиально преобразовать каждую пару (object,uid) в (object, 1), а затем свести их вместе путем суммирования вторых целых чисел. Затем я мог бы фильтровать все, что не попадает в порог (2). Однако в этот момент я потерял бы информацию, необходимую для фильтрации по (1), что я не знаю, как включить в нее. У кого-нибудь есть предложения?

Answer 1

Самый простой и естественный способ - запустить два задания MR в последовательности. Цель первой работы - подсчитать, сколько раз каждый object принадлежит каждому uid. Результат - триплеты (object, uid, count). uid поле здесь предназначено только для отладки - оно не требуется во второй работе. Вторая группа рабочих групп триплетов: object. В конце каждого уменьшение() вызова, вы знаете:

1. количества различных uid с для объекта (количество полученных триплетов)
2. общего количества, сколько времени object принадлежат (сумма count полеев)

Итак, теперь вы можете применять оба фильтра.

---

установка Single-работа также возможна, но она требует манипуляции с работой на немного более низком уровне с setSortComparatorClass(), setGroupingComparatorClass() и setPartitionerClass(). Идея в том, что карта() должен испускать составные ключи, которые содержат как object и uid поля, значение не используется при всех (NullWritable): только

1. перегородки класса Разметки ключи с помощью object поля ключа. Это гарантирует, что все записи с тем же object перейдут к одной и той же задаче сокращения.
2. Класс SortComparator реализован таким образом, что сначала он сравнивает поле object, и если они идентичны, поле uid.
3. GroupingComparatorClass использует только поле object для сравнения.

В результате ввод одного уменьшить задание будет выглядеть следующим образом:

object1 uid1 
object1 uid2 
object1 uid2 
object1 uid2 
object1 uid5 
object1 uid6 
object1 uid6 
------------ <- boundary of call to reduce 
object7 uid1 
object7 uid1 
object7 uid5 
------------- <-- boundary of call to reduce() 
object9 uid3 

Как вы можете видеть, UIDs строго упорядоченный внутри каждого вызова, чтобы уменьшить(), что позволяет рассчитывать и количество отдельных и нечетких uids одновременно.