Структура данных / алгоритм для эффективного сохранения взвешенного скользящего среднего

Question

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

Для разных страниц хотелось бы знать

• общее количество попаданий (просто)
• «последнее» среднее (например, около месяца)
• среднее «долгосрочное» (более года)

Существует ли какой-нибудь умный алгоритм / модель данных, которая позволяет сохранять такие скользящие средние без необходимости пересчитывать их путем суммирования огромных объемов данных?

Мне не нужен точный средний (ровно 30 дней или около того), а только трендовые индикаторы. Так что некоторая нечеткость не является проблемой вообще. Следует просто убедиться, что новые записи имеют больший вес, чем более старые.

Одним из решений, вероятно, было бы автоматическое создание статистических записей за каждый месяц. Тем не менее, мне даже не нужна статистика за последний месяц, так что это похоже на излишество. И это не даст мне скользящее среднее, а скорее переключит на новые значения из месяца в месяц.

Answer 1

Простым решением будет сохранение экспоненциально убывающего итога.

Его можно рассчитать по следующей формуле:

newX = oldX * (p ^ (newT - oldT)) + delta

, где oldX - старое значение вашего итогового значения.(во время oldT), newX - это новое значение вашей общей суммы (во время newT);delta - вклад новых событий в общее количество (например, количество хитов сегодня);p меньше или равно 1 и является фактором затухания.Если мы возьмем p = 1, то у нас будет общее количество попаданий.Уменьшая p, мы эффективно уменьшаем интервал, который описывает наш итог.

Answer 2

Если все, что вам действительно нужно, это сглаженное значение с заданной постоянной времени , то проще всего использовать однополюсный рекурсивный БИХ-фильтр (он же AR или auto-regressive фильтр в анализе временных рядов).Это принимает форму:

Xnew = k * X_old + (1 - k) * x

, где X_old - предыдущее сглаженное значение, X_new - новое сглаженное значение, x - текущая точка данных, а k - коэффициент, определяющий постоянную времени (обычно небольшое значение, <0,1).Возможно, вам придется определить два значения k (одно значение для «недавнего» и меньшее значение для «долгосрочного») эмпирически на основе вашей частоты выборки, которая в идеале должна быть достаточно постоянной, например, одно обновление в день. </p>

Answer 3

Это может быть решением для вас.

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

Это может быть лучше, чем автокорреляционные экспоненциальные алгоритмы, потому что вы можете понять, что вы рассчитываете легче, и не требует математики каждый шаг.Вы можете использовать ограниченные коллекции с ограниченным количеством записей.Они изначально поддерживаются некоторыми БД, например MongoDB.