🤖 AI

Panache: One-Pass Motif Discovery at Every Window Length

Cet article présente Panache, un nouvel algorithme de flux à passage unique qui atteint une complexité temporelle quasi linéaire pour la découverte de pan-motifs z-normalisés sur toutes les longueurs de fenêtre en maintenant des états spectraux en ligne pour filtrer efficacement les candidats, surpassant de manière significative les références CPU et GPU existantes en termes de vitesse et de précision.

Auteurs originaux : Tej Sanibh Ranade

Publié 2026-07-21

📖 9 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Tej Sanibh Ranade

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous êtes un détective essayant de trouver un son spécifique et répétitif dans un enregistrement massif et de plusieurs heures d'une rue citadine animée. Vous savez que le son se produit encore et encore, mais vous n'avez aucune idée de sa durée. Est-ce un « bip » court et sec ? Un « bourdonnement » long et traînant ? Ou un « gazouillis » de durée moyenne ? Si vous essayez de le trouver en écoutant l'enregistrement entier encore et encore, une fois en supposant que c'est un bip, puis une autre fois en supposant que c'est un bourdonnement, puis une autre en supposant que c'est un gazouillis, vous y passeriez une éternité. C'est le combat quotidien des scientifiques des données travaillant avec les séries temporelles — des listes de nombres qui changent au fil du temps, comme les battements de cœur, les cours boursiers ou les tremblements de terre. Ils veulent trouver des motifs : les motifs cachés et répétitifs qui racontent une histoire. La partie délicate est qu'ils ne connaissent rarement la « durée » (combien de secondes ou de points de données dure le motif) à l'avance. Pour résoudre cela, ils doivent généralement vérifier chaque longueur possible, ce qui revient à chercher une aiguille dans une botte de foin en vérifiant chaque brin de paille un par un, encore et encore.

Entrez en scène Panache, une nouvelle méthode qui agit comme un détective super intelligent effectuant une seule passe. Au lieu d'arrêter la bande pour revenir en arrière et vérifier différentes longueurs, Panache écoute l'enregistrement une seule fois. À mesure que le son arrive, il identifie instantanément les motifs répétitifs à toutes les longueurs possibles simultanément. Il y parvient en transformant le son en une « empreinte spectrale » — une signature unique basée sur la forme des ondes plutôt que sur leur simple volume. Si deux sons se ressemblent, leurs empreintes correspondent, et Panache sait qu'il doit les investiguer davantage. S'ils ne correspondent pas, il les ignore immédiatement. Le résultat ? Il trouve exactement les mêmes motifs que les anciennes méthodes lentes, mais en une fraction du temps. Lors de tests, alors que d'autres méthodes prenaient des heures pour analyser un ensemble de données massif, Panache a terminé en quelques minutes, prouvant qu'il n'est pas nécessaire de répéter le travail pour obtenir la bonne réponse.

Le Problème : La Fenêtre « Goldilocks »

Dans le monde des données de séries temporelles, un « motif » est un motif qui se répète. Mais un motif n'est pas seulement une forme ; c'est une forme plus une durée. Imaginez que vous essayiez de trouver un pas de danse spécifique dans une vidéo. Si vous regardez une fenêtre trop courte, vous ne voyez qu'un tapotement de pied. Si vous regardez une fenêtre trop longue, vous voyez le tapotement mélangé au mouvement suivant, à l'arrière-plan et à la tenue du danseur. Vous avez besoin de la fenêtre « Goldilocks » (juste ce qu'il faut) : la longueur idéale pour voir tout le mouvement clairement.

Le problème est que dans l'analyse exploratoire des données, nous ne connaissons souvent pas cette longueur « juste ce qu'il faut ». Nous pouvons devoir vérifier des longueurs allant de 10 points à 1 000 points. L'ancienne méthode, appelée Pan Matrix Profile (PMP), était comme un bibliothécaire très consciencieux mais incroyablement lent. Pour trouver la meilleure correspondance pour chaque longueur, le bibliothécaire devait lancer une recherche massive distincte pour la longueur 10, puis recommencer pour la longueur 11, puis la longueur 12, et ainsi de suite. Si vous aviez 50 longueurs différentes à vérifier, le bibliothécaire devait lire l'intégralité du livre 50 fois. C'est ce qu'on appelle faire des « auto-jointures quadratiques », une façon sophistiquée de dire « comparer chaque morceau de donnée à chaque autre morceau, encore et encore ». Cela fonctionne, mais cela devient douloureusement lent à mesure que les données s'agrandissent.

La Solution Panache : Une Seule Passe, Toutes les Longueurs

Les auteurs de cet article, Tej Sanibh Ranade, ont introduit Panache, qui est le premier algorithme capable d'accomplir cette tâche de « Pan Matrix Profile » en une seule passe. Au lieu de rembobiner la bande 50 fois, Panache lit le flux de données exactement une fois. À mesure que chaque nouveau nombre arrive, il met à jour son état interne pour toutes les différentes longueurs qui l'intéressent en même temps.

Comment réalise-t-il ce tour de magie ? Il s'appuie sur une observation mathématique ingénieuse. Lorsque vous prenez un bloc de données et que vous le « normalisez » (ce qui signifie l'ajuster de sorte qu'il ait une moyenne de zéro et un écart type de un, éliminant ainsi le volume pour se concentrer uniquement sur la forme), quelque chose d'incroyable se produit. La seule partie du « spectre » mathématique des données (sa transformée de Fourier) qui change est la composante DC (la moyenne). Le reste du spectre — les parties qui décrivent la forme réelle de l'onde — reste exactement le même, quel que soit la moyenne.

Panache utilise ce fait pour maintenir un état spectral glissant. À mesure que la fenêtre de données glisse vers l'avant d'un pas, l'algorithme ne recalcule pas toute la forme à partir de zéro. Au lieu de cela, il utilise une récurrence de « DFT glissante » (Transformée de Fourier Discrète). Pensez à un tapis roulant d'ingrédients. Lorsqu'un nouvel ingrédient arrive, vous ne jetez pas toute la recette pour recommencer ; vous remplacez simplement l'ancien ingrédient à l'arrière et ajoutez le nouveau à l'avant, en ajustant légèrement les calculs. Cela permet à Panache de maintenir une « empreinte » de la forme à jour pour chaque longueur de fenêtre en temps réel.

La Boîte à Outils du Détective : Hachage et Rejet

Une fois que Panache possède ces empreintes spectrales, il doit trouver lesquelles correspondent. Il ne peut pas comparer chaque empreinte à toutes les autres, sinon cela serait encore trop lent. Il utilise donc un Hachage Sensible à la Localité (LSH). Imaginez un immense classeur où les empreintes similaires sont automatiquement triées dans le même tiroir. Si deux fenêtres ont des formes similaires, leurs hachages (signatures numériques) seront très proches, et elles atterriront dans le même compartiment.

Cependant, le fait que deux éléments soient dans le même compartiment ne signifie pas qu'ils sont une correspondance parfaite. Pour éviter d'effectuer des calculs exacts et coûteux sur chaque paire dans le compartiment, Panache utilise une borne inférieure de Parseval. C'est un filet de sécurité mathématique. Il calcule une « distance minimale possible » entre deux formes en se basant uniquement sur leurs empreintes spectrales. Si cette distance minimale est déjà trop grande pour être une correspondance, Panache rejette la paire sans effectuer plus de travail. C'est comme un videur de boîte de nuit qui vérifie l'identité ; si l'identité semble fausse, il ne vous laisse même pas entrer pour vérifier votre visage. Cette étape rejette la vaste majorité des « presque correspondances », économisant ainsi un temps énorme.

La Stratégie de l'« Ancre »

Même avec ces astuces, garder trace de chaque longueur possible (disons, de 10 à 1 000) en mémoire serait trop lourd. Ainsi, Panache utilise une stratégie de Longueurs d'Ancre. Au lieu de maintenir une recherche active complète pour chaque longueur, il ne maintient la recherche « active » que pour quelques longueurs sélectionnées (les ancres), espacées comme des pierres de gué.

L'article soutient que les motifs sont « collants ». Si un motif est une bonne correspondance pour une longueur de 20, il est très probable qu'il soit aussi une bonne correspondance pour une longueur de 19 ou 21. Ainsi, Panache trouve les correspondances aux longueurs d'ancre, puis effectue une vérification locale rapide sur les longueurs situées entre elles. Cela signifie qu'il n'a pas besoin de faire le gros du travail pour chaque longueur, mais il trouve quand même les réponses car les « bonnes » longueurs sont regroupées.

Les Résultats : Vitesse et Précision

Les auteurs ont testé Panache sur 17 configurations différentes de données réelles, incluant des battements de cœur (ECG), des séismes et des données boursières. Ils l'ont comparé aux meilleures méthodes existantes, y compris celles utilisant de puissants processeurs graphiques (GPU).

Les résultats ont été frappants. Sur un ensemble de données appelé Wafer comprenant 5 millions de points de données et 51 longueurs différentes à vérifier :

La méthode CPU existante la plus rapide a pris 7,95 heures.
Une méthode GPU de haut niveau (Scamp sur un H100) a pris 38,3 minutes.
Panache a terminé le scan initial en 2,9 minutes et a émis les motifs exacts finaux en 6,0 minutes.

Panache était plus rapide que toutes les bases de comparaison CPU et GPU testées. Plus important encore, il n'a pas sacrifié la précision. Il a récupéré 100 % des 20 meilleurs motifs trouvés par les méthodes exactes et lentes. Chaque motif rapporté était une distance exacte par rapport à un voisin valide ; il ne s'agissait pas d'une estimation.

Pourquoi cela importe

L'article conclut que Panache résout un problème de longue date du forage de données : comment trouver des motifs répétitifs de longueur inconnue de manière continue (streaming) et en temps réel sans sacrifier la précision. En remplaçant l'approche répétitive et lente de « revenir en arrière et chercher » par une seule passe intelligente utilisant des empreintes spectrales et des raccourcis mathématiques, Panache rend possible l'analyse de flux de données massifs en quelques minutes plutôt qu'en quelques heures. Il prouve que l'on peut avoir le meilleur des deux mondes : obtenir les résultats exacts et rigoureux des anciennes méthodes avec la vitesse d'un algorithme de flux moderne. Le seul compromis est la mémoire ; parce qu'il conserve beaucoup de données en RAM pour effectuer ces recherches rapides, il nécessite plus de mémoire que certaines méthodes plus simples, mais pour la vitesse qu'il offre, les auteurs suggèrent que c'est un prix qui en vaut la peine.

Résumé Technique : Panache – Découverte de Motifs en un Seul Passage pour Toutes les Longueurs de Fenêtre

1. Énoncé du Problème

La découverte de motifs dans les séries temporelles recherche des formes récurrentes au sein d'une séquence. Un défi fondamental dans ce domaine est qu'un « motif » est défini par sa durée (longueur de fenêtre, $m$ ), que les analystes ne peuvent souvent pas spécifier à l'avance. Les approches traditionnelles définissent un intervalle de longueurs de fenêtre $[m_{min}, m_{max}]$ et tentent de trouver des motifs pour chaque longueur au sein de cet intervalle.

Les méthodes existantes pour le Pan Matrix Profile (PMP), qui agrège l'information de motif à travers toutes les longueurs d'un intervalle, souffrent d'une inefficacité critique : elles traitent chaque longueur de fenêtre comme un problème indépendant. Pour calculer le PMP, les algorithmes existants effectuent $L$ auto-jointures quadratiques séparées (où $L$ est le nombre de longueurs), ce qui revient à rescanner l'intégralité de la série temporelle pour chaque longueur de fenêtre. Cela se traduit par un coût computationnel qui évolue linéairement avec le nombre de longueurs et quadratiquement avec la longueur de la série, ce qui est prohibitif pour les grands ensembles de données ou les applications de streaming en temps réel.

L'objectif est d'atteindre une découverte de motifs en streaming en un seul passage capable de calculer le PMP pour un intervalle de longueurs sans rescanner les données, tout en garantissant l'exactitude des distances z-normalisées.

2. Méthodologie : L'Algorithme Panache

Panache introduit le premier algorithme de streaming en un seul passage pour la découverte de motifs PMP z-normalisés. Au lieu d'effectuer $L$ auto-jointures indépendantes, Panache maintient un état de recherche multi-longueur unique pendant qu'il parcourt la série.

Mécanismes Fondamentaux

L'algorithme repose sur quatre mécanismes clés pour s'adapter au flux de données :

Spectre AC Normalisé comme État de Streaming :
- Panache observe que la z-normalisation d'une sous-séquence (soustraction de la moyenne et division par l'écart-type) n'affecte que le coefficient de Fourier de courant continu (DC, fréquence zéro). Les coefficients non-DC conservent leur forme, étant simplement mis à l'échelle par l'écart-type.
- L'algorithme maintient un état en ligne des coefficients de Fourier non-DC pour chaque longueur d'ancrage en utilisant des récurrences de DFT glissantes. Lorsqu'un nouvel échantillon arrive, l'échantillon le plus ancien est supprimé et le nouveau est ajouté, mettant à jour les coefficients en un temps $O(K)$ (où $K$ est la largeur spectrale conservée).
- Ce vecteur spectral remplit un triple rôle :
  - État de Streaming : Il se met à jour de manière incrémentale.
  - Clé SimHash : Il sert de signature de hachage sensible à la localité (LSH). Les fenêtres ayant des formes normalisées similaires possèdent des vecteurs spectraux similaires et entrent donc en collision dans les mêmes compartiments de hachage.
  - Borne de Rejet : En utilisant le théorème de Parseval, l'algorithme calcule une borne inférieure sur la distance euclidienne entre deux fenêtres basée sur leurs vecteurs spectraux tronqués. Cette borne permet à Panache de rejeter la grande majorité des paires de candidats avant d'effectuer des calculs de distance exacts coûteux.
Longueurs d'Ancrage :
- Maintenir un index complet en ligne pour chaque longueur de l'intervalle est gourmand en mémoire. Panache sélectionne un sous-ensemble de longueurs d'ancrage (par exemple, toutes les $s$ -ièmes longueurs) pour maintenir des index en ligne.
- Il s'appuie sur l'observation empirique que les motifs persistent à travers les longueurs voisines. Si un motif est trouvé à une longueur d'ancrage, l'algorithme effectue une étape de complétion locale pour vérifier et affiner le motif aux longueurs non-ancres immédiatement voisines.
Hachage Contrôlé par l'Occupation :
- Pour gérer le flux croissant sans croissance illimitée de la mémoire, Panache utilise un répertoire à profondeur de préfixe globale (une variante du hachage extensible).
- Il contrôle l'occupation des compartiments (buckets) en divisant le répertoire globalement lorsque la population dépasse un seuil cible ( $\alpha$ ). Cela garantit que le nombre de candidats à inspecter par requête reste borné, quelle que soit la longueur du flux.
- Le multi-probing est utilisé pour gérer les collisions de hachage, en inspectant les compartiments à une distance de Hamming de 1 pour assurer un rappel élevé.
Complétion au Moment de l'Émission (Emit-Time Completion) :
- Le passage en streaming produit un « profil supérieur sonore » (une borne supérieure sur le profil réel). Pour garantir l'exactitude, une étape finale d'émission est exécutée après le flux :
  - Tamis de Classe Chaude (Hot-Class Sieve) : Pour les compartiments de hachage qui dépassent le budget de vérification (contenant de nombreuses fenêtres similaires), un tamis basé sur le tri évalue les distances exactes parmi les candidats les plus prometteurs.
  - Complétion Locale : Pour les longueurs non-ancres, l'algorithme prend les meilleurs motifs trouvés aux longueurs d'ancrage comme « graines » et effectue des calculs de distance exacts dans leurs voisinages locaux (en longueur et en position) pour combler les lacunes.

Déterminisme et Parallélisme

Panache traite les données par micro-lots (micro-batches). Au sein d'un lot, les fenêtres sont avancées en parallèle et les calculs de distance exacts sont mis en mémoire tampon. Un ordre de fusion fixe garantit que la sortie est déterministe, quel que soit le nombre de threads ou le planning d'exécution spécifique.

3. Contributions Clés

Formulation en un Seul Passage : Panache est le premier algorithme capable de calculer un PMP z-normalisé en un seul passage sur les données, remplaçant $L$ auto-jointures quadratiques par un seul balayage linéaire.
Représentation par État Spectral : Il introduit une représentation par spectre AC normalisé qui est maintenue en ligne, servant simultanément d'état de streaming, de clé LSH et de source d'une borne inférieure de Parseval pour l'élagage.
Mécanismes Scalables : L'article détaille l'intégration du hachage à profondeur globale contrôlé par l'occupation, de la recherche par longueurs d'ancrage et des mises à jour par lots déterministes pour gérer les flux de données massifs.
Garantie d'Exactitude : Contrairement à de nombreuses approximations en streaming, Panache garantit que chaque cellule écrite dans le profil est une distance z-normalisée exacte par rapport à un voisin valide. Il ne rapporte pas de distances estimées.

4. Résultats Expérimentaux

L'algorithme a été évalué sur 17 configurations à travers 10 jeux de données de séries temporelles UCR, allant de 1 600 à 5 millions d'échantillons, avec des longueurs de fenêtre allant de 30 à 80.

Précision de Récupération : Panache a récupéré 100 % des 20 meilleurs motifs (340/340 contre la vérité terrain de Stumpy ; 740/740 sur l'ensemble du benchmark) avec des distances exactes.
Performance vs Baselines CPU : Panache est nettement plus rapide que les baselines CPU exactes existantes (Scamp, Stumpy, SCRUMP).
- Accélération médiane : 6,6x par rapport à Scamp CPU et 7,3x par rapport à Scamp-GPU.
- Sur le jeu de données Wafer 5M (5 millions d'échantillons, 51 longueurs), Panache a terminé le passage de streaming en 2,9 minutes et a émis les motifs exacts en 6,0 minutes.
- En comparaison, la baseline CPU exacte la plus rapide (Scamp) a pris 7,95 heures, et Scamp sur un GPU H100 a pris 38,3 minutes.
Efficacité Mémoire : Bien que l'algorithme nécessite une mémoire linéaire par rapport à la longueur de la série (pour stocker les caractéristiques et le profil), il reste pratique. Pour l'exécution de 5M d'échantillons, la mémoire de pointe était de 23,3 Go pendant le streaming et de 35,5 Go lors de la matérialisation complète.

5. Signification et Revendications

L'article affirme que Panache résout le compromis de longue date entre efficacité en streaming et couverture multi-longueurs. Les méthodes précédentes pouvaient soit streamer une seule longueur, soit calculer plusieurs longueurs hors ligne avec un coût élevé. Panache réussit les deux :

Il traite l'intervalle complet de longueurs en un seul passage.
Il maintient l'exactitude (pas d'approximations probabilistes dans la sortie finale).
Il est dépendant des données dans sa sélection de paramètres (par exemple, la largeur spectrale $K$ est calibrée à partir des données), ne nécessitant qu'un seul budget de ressources ( $\alpha$ ) à ajuster par l'utilisateur.

Les auteurs soulignent que l'accélération de l'algorithme ne provient pas d'un sacrifice de la précision, mais de l'élimination des rescans redondants et de l'exploitation des propriétés mathématiques des spectres z-normalisés pour élaguer efficacement l'espace de recherche. Ce travail démontre que « un seul passage » et « exact » sont compatibles pour le problème du Pan Matrix Profile.