Восстановление состояния из событий данных временных рядов

Question

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

Данные собираются в форме, подобной этой:

<b>Timestamp    Event</b>
0            x = 0
0            y = 1
3            Event A occurred
3            x = 1
4            Event A occurred
4            x = 2
9            Event B occurred
9            y = 2
9            x = 0

Чтобы понять все состояние в любое время, самый простой подход - просмотреть весь набор данных. Например, если я начинаю в момент времени 0 и «анализирую» до отметки времени 5, я знаю, что в этот момент x = 2, y = 1, и событие A произошло дважды. Это действительно простой пример. Пользователь может интересоваться (и часто интересуется) временем между событиями, скажем, от A до B, и они могут указывать первое вхождение A, затем B или последнее вхождение A, затем B (соответственно 9-3 = 6 или 9-4 = 5). Как я уже сказал, это легко анализировать, когда вы гуляете по всему сету.

Теперь нам нужно адаптировать модель для анализа произвольного окна времени. Если мы посмотрим на 0-N, это простой случай. Но если я смотрю, например, на 1-5, у меня нет понятия y, если я не начинаю с 0 и не знаю, что y изначально было 1 и не изменилось в окне 1-5.

Наш подход заключается в создании словаря переменных и выполнении обратных вызовов для событий. Если бы один анализ был «Что такое x, когда происходит событие A, а время> 3», то мы бы запустили этот обратный вызов для первого события A, и он немедленно вернулся бы, потому что время не больше 3. Он снова запустится в 4 и он сообщит, что х был 1 при t = 4.

Чтобы приспособиться к «временным окнам», я думаю (на заднем плане) прибегнуть к дополнительным условиям для анализа. Если их анализ - «Что такое x, когда происходит событие A», а текущее окно - 1-5, то я изменю его на «Что такое x, когда происходит событие A, время> = 1 и время <= 5». Затем, если в следующем окне будет 6-10, я смогу перенастроить условие по мере необходимости. </p>

Мой главный вопрос: к какому образцу это подходит? Мы, очевидно, не первые люди, которые подходят к такой проблеме, но я не смог найти, как другие подошли к ней. Я, наверное, просто не знаю, что именно искать в Google. Существует ли какой-либо другой подход, кроме хранения словаря всего глобального состояния для поиска одного состояния в данный момент времени? Обратите внимание также, что данные могут иметь несколько, может быть, десятки тысяч записей, поэтому чем меньше итерации по набору данных, тем лучше.

Answer 1

Я думаю, что вашим лучшим подходом здесь было бы делать периодические «снимки» данных полного состояния, скажем, каждые 1000 выборок (например), вместе с записью дельт. Когда вы сохраняете свои данные в виде смещений от некоторого исходного значения (иначе как дельты), у вас нет другого выбора, кроме как восстановить полные данные, начиная с исходных значений. Хранение периодических моментальных снимков уменьшит объем реконструкции, который вам нужно сделать - компромисс между дизайном заключается в низких требованиях к хранилищу, но, с одной стороны, в более длительных сроках восстановления и повышенных требованиях к хранилищу, а в других - в более короткие сроки. Например,

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

Answer 2

Вы можете искать по времени в журнале (N), и у вас может возникнуть ощущение, сколько обновлений допустимо ... отсюда и мое решение:

Выберите число N обновлений, приемлемых для возврата результата. 256 может быть хорошим, учитывая масштабы, которые вы упомянули до сих пор.

Каждые N записей фиксируют запись всех состояний в словарь с отметкой времени.

Теперь у вас есть компромисс между размером словаря и скоростью. N -> \ infty - это обычный поиск. N <-1 - ваше текущее решение, N где-либо еще потребует меньше памяти, но будет медленнее. </p>

Ваша реализация сейчас (для времени X): Записать (n) поиск глобального словаря с субдискретизацией в метку времени до X (отметка времени Y). Записать (n) поиск списка событий во временную метку Y и выполнить обновления менее N.

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