Линейный фильтр (FIR) в Hadoop (упражнение Hadoop в действии) - PullRequest
Новая
       3

Линейный фильтр (FIR) в Hadoop (упражнение Hadoop в действии)

0 голосов
/ 30 марта 2011

Упражнение 4, глава 4 в Hadoop в действии, о реализации линейного фильтра, вычисляющего скользящее среднее временного ряда. То есть, учитывая N и ряд значений a (t) с метками времени, вычисляем y, где 

y(t) = a(t)*1/N + a(t-1)*1/N + ... + a(t-N)*1/N.

У меня проблемы с реализацией этого в Mapreduce. Редуктор должен получить N записей, необходимых для совместного вычисления элемента в y. Даже если записи упорядочены в хронологическом порядке, эти N записей могут быть разбиты на два сопоставителя. Какой ключ для передачи в маппере будет гарантировать, что тот же редуктор получит эти N записей? Их временные метки различны и поэтому не используются в качестве ключей.

Или я совсем не в своем подходе? Буду благодарен за подсказки.

1 Ответ

1 голос
/ 01 апреля 2011

Глядя на проблему из книги, вы немного исказили проблему.

Входными данными является последовательность ключей / значений (t -> x (t)), где t - время, а x (t) - значение, наблюдаемое в это время. Затем, чтобы вычислить скользящее среднее в любое время, вы используете формулу: 

y(t) = a0 * x(t) + a1 * x(t-1) + a2 * x(t-2) + ... + aN * x(t-N)

, где a0, a1, a2, ... aN - известные константы.

Ключом к реализации картографа для этой задачи является распознавание всех y (t) уравнений, содержащих конкретный x, и использование уравнения в качестве ключа. Это сделано, наблюдая образцы параметра времени, t. Для любого x (t) x (t) находится первым в y (t). x (t) также является вторым слагаемым в y (t + 1), третьим слагаемым в y (t + 2) и т. д. вплоть до (N + 1) места слагаемого в y (t + N).

Таким образом, для каждой для каждой (t -> x (t)) клавиши / значения на входе картограф должен вывести несколько новых пар ключ / значение: 

t   -> {a0, x(t)}
t+1 -> {a1, x(t)}
t+2 -> {a2, x(t)}
...
t+N -> {aN, x(t)}

После того, как картограф будет завершен, будет набор {{, x (t)} значений, определяемых уравнением y (t), частью которого они являются.

На стороне редуктора будет доставлен набор значений {an, x (t)} для конкретного y (t), для которого можно вычислить сумму произведений для получения значения y (t).

...