La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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 Interpolation d'index : un algorithme de correspondance de sous-séquences prenant en charge la transformation de moyenne mobile d'un ordre arbitraire dans les bases de données de séries chronologiques

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

  • Vues en texte intégral

    0

  • Citer

Résumé:

Dans cet article, nous proposons un algorithme d'appariement de sous-séquences qui prend en charge la transformation de moyenne mobile d'ordre arbitraire dans les bases de données de séries chronologiques. La transformation de moyenne mobile réduit l'effet du bruit et a été utilisée dans de nombreux domaines tels que l'économétrie, car elle est utile pour trouver les tendances globales. L'algorithme proposé étend l'algorithme d'appariement de sous-séquences existant proposé par Faloutsos et al. (SUB94 en bref). Si nous appliquions l'algorithme sans aucune extension, nous devrions générer un index pour chaque commande de moyenne mobile et cela entraînerait une surcharge importante en termes de stockage et de temps CPU. Dans cet article, nous abordons le problème en utilisant la notion d'interpolation d'index. Interpolation d'index est défini comme une méthode de recherche qui utilise un ou plusieurs index générés pour quelques cas sélectionnés et effectue une recherche de tous les cas satisfaisant certains critères. L'algorithme proposé, basé sur l'interpolation d'indices, ne peut utiliser qu'un seul indice pour un ordre de moyenne mobile présélectionné. k et effectue une correspondance de sous-séquence pour un ordre arbitraire m ( k). Nous prouvons que l’algorithme proposé ne provoque aucun faux licenciement. L'algorithme proposé peut également utiliser plusieurs index pour améliorer les performances de recherche. L'algorithme fonctionne mieux avec des sélectivités plus petites. Pour les sélectivités inférieures à 10-2, la dégradation des performances de recherche par rapport au cas entièrement indexé (qui équivaut à SUB94) ne dépasse pas 33.0 % lorsqu'un seul index est utilisé, et 17.2 % lorsque deux index sont utilisés. Puisque les requêtes avec des sélectivités plus petites sont beaucoup plus fréquentes dans les applications générales de bases de données, l’algorithme proposé est adapté aux situations pratiques.

Publication
IEICE TRANSACTIONS on Information Vol.E84-D No.1 pp.76-86
Date de publication
2001/01/01
Publicisé
ISSN en ligne
DOI
Type de manuscrit
PAPER
Catégories
Bases de données

Auteurs

Mots-clés

Table des matières