A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Index Interpolation: A Subsequence Matching Algorithm Supporting Moving Average Transform of Arbitrary Order in Time-Series Databases Interpolação de índice: um algoritmo de correspondência de subsequência que suporta transformação de média móvel de ordem arbitrária em bancos de dados de séries temporais

Woong-Kee LOH, Sang-Wook KIM, Kyu-Young WHANG

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Neste artigo propomos um algoritmo de correspondência de subsequências que suporta transformadas de média móvel de ordem arbitrária em bancos de dados de séries temporais. A transformação da média móvel reduz o efeito do ruído e tem sido usada em muitas áreas, como a econometria, uma vez que é útil para encontrar tendências gerais. O algoritmo proposto estende o algoritmo de correspondência de subsequências existente proposto por Faloutsos et al. (SUB94 em resumo). Se aplicássemos o algoritmo sem qualquer extensão, teríamos que gerar um índice para cada pedido de média móvel e teríamos sérios custos de armazenamento e tempo de CPU. Neste artigo abordamos o problema usando a noção de interpolação de índice. Interpolação de índice é definido como um método de busca que utiliza um ou mais índices gerados para alguns casos selecionados e realiza busca em todos os casos que satisfazem alguns critérios. O algoritmo proposto, que é baseado na interpolação de índices, pode usar apenas um índice para uma ordem de média móvel pré-selecionada. k e realiza correspondência de subsequência para ordem arbitrária m ( k). Provamos que o algoritmo proposto não causa falsa rejeição. O algoritmo proposto também pode usar mais de um índice para melhorar o desempenho da pesquisa. O algoritmo funciona melhor com seletividades menores. Para seletividades inferiores a 10-2, a degradação do desempenho da pesquisa em comparação com o caso totalmente indexado - que é equivalente ao SUB94 - não passa de 33.0% quando um índice é usado e 17.2% quando dois índices são usados. Como as consultas com seletividades menores são muito mais frequentes em aplicações gerais de bancos de dados, o algoritmo proposto é adequado para situações práticas.

Publicação
IEICE TRANSACTIONS on Information Vol.E84-D No.1 pp.76-86
Data de publicação
2001/01/01
Publicitada
ISSN online
DOI
Tipo de Manuscrito
PAPER
Categoria
Bases de dados

autores

Palavra-chave