Schnelle Teilfolgenabgleichung in Zeitreihenbanken

Wir präsentieren eine effiziente Indexierungsmethode zur Lokalisierung 1-dimensionaler Teilfolgen innerhalb einer Sammlung von Sequenzen, sodass die Teilfolgen ein gegebenes (Abfrage-) Muster innerhalb einer bestimmten Toleranz entsprechen. Die Idee ist, jede Daten sequenz in eine kleine Menge von mehrdimensionalen Rechtecken im Merkmalsraum abzubilden. Anschließend können diese Rechtecke mit traditionellen räumlichen Zugriffsverfahren, wie dem R*-Baum 9, indiziert werden. Genauer gesagt verwenden wir ein gleitendes Fenster über der Daten sequenz und extrahieren deren Merkmale; das Ergebnis ist eine Spur im Merkmalsraum. Wir schlagen einen effizienten und effektiven Algorithmus vor, um solche Spuren in Unterspuren zu unterteilen, die anschließend durch ihre minimalen umschließenden Rechtecke (MBRs) dargestellt werden. Außerdem untersuchen wir Abfragen unterschiedlicher Längen und zeigen, wie man jeden Fall effizient behandelt. Wir haben unsere Methode implementiert und Experimente mit synthetischen und realen Daten (Aktienkursbewegungen) durchgeführt. Wir verglichen die Methode mit der sequenziellen Abtastung, die der einzige offensichtliche Konkurrent ist. Die Ergebnisse waren ausgezeichnet: Unsere Methode beschleunigte die Suchzeit von 3 bis zu 100 Mal.