Reconstruir estado de eventos de dados de séries temporais

Question

Para um projeto particular, adquirir dados para uma série de eventos e variáveis ??coletamos sobre esses eventos ao mesmo tempo. Depois que os dados foram coletados, realizamos uma análise customizável pelo usuário na referida dados para determinar o que é que o usuário está interessado.

Os dados são obtidos sob uma forma semelhante a esta:

Timestamp    Event
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

Para compreender o estado inteiro, a qualquer momento, a abordagem mais simples é caminhar ao longo de todo o conjunto de dados. Por exemplo, se eu começar no tempo 0, e "analisar" até timestamp 5, eu sei que naquele ponto x = 2, y = 1, e Evento Um tenha ocorrido duas vezes. Isso é um exemplo muito simples. O usuário força ser (e geralmente é) interessado no tempo entre eventos, digamos, de A para B, e eles podem especificar a primeira ocorrência de A, então B, ou a última ocorrência de A, em seguida, B (respectivamente, 9-3 = 6 ou 9-4 = 5). Como eu disse, isso é fácil de analisar quando você está andando ao longo de todo o conjunto.

Agora, precisamos adaptar o modelo para analisar uma janela de tempo arbitrário. Se olharmos para 0-N, que é o caso fácil. Mas se eu olhar para 1-5, por exemplo, não tenho noção de y menos que eu começar em 0 e sabemos que y foi inicialmente 1 e não se alterou na janela 1-5.

A nossa abordagem é criar essencialmente um dicionário de variáveis, e retornos de chamada executado em eventos. Se uma análise foi "O que é x quando o evento A ocorre eo tempo é> 3" então poderíamos executar esse callback no primeiro evento A, e que iria retornar imediatamente porque o tempo não é maior que 3. Ele iria correr novamente a 4, e e seria relatam que x foi de 1 em t = 4.

Para se adaptar ao tack "em tempo de janelas", eu acho que eu vou (ao fundo) sobre as condições adicionais para a análise. Se a sua análise é apenas "o que é x quando o evento A ocorre", ea janela atual é 1-5, então eu vou mudá-lo para "O que é x quando o evento A ocorre e hora> = 1 e tempo <= 5". Então, se a janela seguinte é 6-10, I pode reajustar a condição de, se necessário.

A minha pergunta principal é: o padrão isso se encaixa Não são, obviamente, as primeiras pessoas a abordar um problema como este, mas eu não tenho sido capaz de encontrar como os outros se aproximaram dele?. Eu provavelmente só não sei o que exatamente para procurar no Google. Existe alguma outra abordagem além de manter um dicionário de todo o estado global para procurar um único estado em um determinado momento? Note também que os dados poderiam ter vários, talvez dezenas de milhares de registros, de modo que o menos iterações sobre o conjunto de dados, melhor.

Answer 1

Eu acho que sua melhor abordagem aqui seria a de tomar "instantâneos" periódicas dos dados de estado completas, dizer a cada 1000 amostras (por exemplo), juntamente com a gravação dos deltas. Quando você está armazenando seus dados como deslocamentos de algum valor original (aka deltas), você não tem escolha, mas para reconstruir os dados completos começando com os valores originais. Armazenar instantâneos periódicos irá diminuir a quantidade de reconstrução você tem que fazer -. A troca design é entre baixos requisitos de armazenamento, mas o tempo de reconstrução a longo por um lado, e os requisitos de armazenamento mais elevadas, mas o tempo de reconstrução mais curto por outro

MPEGs, por exemplo, armazenar cada quadro como as diferenças entre o quadro actual e o quadro anterior. Normalmente, isso iria forçar um MPEG para ser visto desde o início, mas o formato também armazena periodicamente quadros completos para que o decodificador não tem que retroceder todo o caminho para o início do arquivo.

Answer 2

Você pode procurar pelo tempo em Log (N), e você pode ter um sentimento sobre quantas atualizações ares aceitável ... portanto aqui está a minha solução:

Escolha um número, N, de alterações que são aceitáveis, a fim de retornar um resultado. 256 pode ser bom, dadas as escalas que você mencionou até agora.

registros cada N, cometer uma entrada de todo o estado a um dicionário, com um timestamp.

Agora, você tem uma troca, tamanho do dicionário contra velocidade. N -> \ infty está à procura regular. N <-1 é a sua solução atual, N em qualquer outro lugar exigirá menos memória, mas ser mais lento.

A sua implementação é agora (para o tempo X): Log (n) pesquisa de dicionário subamostrado global para timestamp antes X, (timestamped como Y). Log (n) pesquisa de eventlist para timestamp Y, e realizar menos de actualizações N.

Escolher N como uma potência de dois vai mesmo permitir que você faça alguns truques agradável mudança para fazer uma boa inteiro divisão arredondada para baixo e rápido.