Réduction de dimensionnalité localement adaptive pour l'indexation de grandes bases de données de séries temporelles

La recherche de similarité dans de grandes bases de données de séries temporelles a récemment attiré beaucoup d'intérêt de recherche. C'est un problème difficile en raison de la dimensionnalité généralement élevée des données. Les solutions les plus prometteuses impliquent de réaliser une réduction de dimensionnalité sur les données, puis d'indexer les données réduites avec une structure d'index multidimensionnelle. De nombreuses techniques de réduction de dimensionnalité ont été proposées, y compris la décomposition en valeurs singulières (SVD), la transformée de Fourier discrète (DFT) et la transformée en ondelettes discrète (DWT). Dans cet article, nous introduisons une nouvelle technique de réduction de dimensionnalité, que nous appelons Approximation Constante Par Morceaux Adaptive (APCA). Alors que les techniques précédentes (par exemple, SVD, DFT et DWT) choisissent une représentation commune pour tous les éléments de la base de données qui minimise l'erreur de reconstruction globale, l'APCA approxime chaque série temporelle par un ensemble de segments de valeur constante de longueurs variables de sorte que leurs erreurs de reconstruction individuelles soient minimales. Nous montrons comment l'APCA peut être indexée en utilisant une structure d'index multidimensionnelle. Nous proposons deux mesures de distance dans l'espace indexé qui exploitent la grande fidélité de l'APCA pour une recherche rapide : une approximation de distance euclidienne par estimation inférieure et une approximation de distance euclidienne très serrée, mais non par estimation inférieure, et montrons comment elles peuvent soutenir une recherche exacte rapide et même une recherche approximative plus rapide sur la même structure d'index. Nous comparons théoriquement et empiriquement l'APCA à toutes les autres techniques et démontrons sa supériorité.