[dbis logo]

.Mitarbeiter.Derzeitige
[Institut fuer Informatik] [Leerraum] [Humboldt-Universitaet zu Berlin]

Jörg Bachmann

Adresse: Institut für Informatik
Humboldt-Universität zu Berlin
Unter den Linden 6
D-10099 Berlin
Sitz: Rudower Chaussee 25
D-12489 Berlin
Raum: 4.208
Telefon: +49 30 2093-3022
E-Mail: Joerg.Bachmann@informatik.hu-berlin.de


Lehre

Forschung

Ich forsche im Bereich der Datenverarbeitung metrischer Zeitreihen. Während eine Zeitreihe üblicherweise als endliche Sequenz reeller Zahlen interpretiert wird, ist eine metrische Zeitreihe eine endliche Sequenz von Punkten eines metrischen Raumes (Zustandsraum). Dies umfasst insbesondere die folgenden beiden Fälle:

  • Zeitreihen über einen mehrdimensionalen Vektorraum mit dem euklidischen Abstandsmaß im Zustandsraum
  • Zeitreihen über einen Graphen mit der Länge des kürzesten Pfades zwischen zwei Knoten als Abstandsmaß im Zustandsraum

 

Bei der Verarbeitung von Zeitreihen gibt es eine immer wiederkehrende Aufgabe: Die Suche nach ähnlichen Zeitreihen in einer gegebenen Menge von Zeitreihen (Nearest Neighbour Query). In meiner Forschung behandle ich die folgenden Fragen:

  • Was bedeutet Ähnlichkeit zweier Zeitreihen und wie kann diese effizient berechnet werden (Abstandsmaße)
  • Wie kann eine Nearest Neighbour Query möglichst schnell berechnet werden (Indizierung von Zeitreihen)

Abstandsmaße

Bei der Wahl eines geeigneten Abstandsmaßes für einen konkreten Anwendungsfall steht insbesondere die folgende Frage im Mittelpunkt:

Gegen welche Transformationen soll das Abstandsmaß für Zeitreihen invariant sein?

Verschiedene Anwendungsfälle fordern verschiedene Invarianzen, wie die folgenden Beispiele zeigen:

  • Content Based Video Copy Detection: Betrachtet man ein Video als eine Zeitreihe über den Raum aller Bilder, so sollen zwei Videos ähnlich sein, wenn das eine Video eine Kopie des anderen Videos ist (eventuell in schlechterer Qualität, eventuell nur einige Szenen, etc.)
  • Audio Cover Recognition: Betrachtet man einen Song, der von zwei verschiedenen Interpreten gespielt wird, so kann es zeitliche Variationen geben. Ein Abstandsmaß, dass Cover erkennen soll, muss also invariant gegen "Local Time Shifting" sein.
  • Motion Gesture Recognition: Bei der Ähnlichkeitssuche einer aufgenommenen Geste (z. B. die Trajektorie einer Fingerspitze) sind Transformationen, wie z. B. Rotation, Translation und Skalierung (bis zu einem gewissen Grade) als invariant zu betrachten. In diesem Fall ist ein Abstandsmaß für Kongruenz von Zeitreihen gesucht.

Indizierung von Zeitreihen

Eine Nearest Neighbour Query gibt zu einer Anfragezeitreihe (Query) die ähnlichsten Zeitreihen einer gegebenen Menge von Zeitreihen (Datenbank) zurück. Im einfachsten Fall wird dazu die Query mit jeder Zeitreihe der Datenbank verglichen (linear scan). Unter gewissen Umständen kann die Anzahl der zu berechnenden Vergleiche reduziert werden.

  • Erfüllt das Abstandsmaß für Zeitreihen die Dreiecksungleichung, so können metrische Indexstrukturen verwendet werden, um Nearest Neighbour Queries durchzuführen und die Anzahl der zu berechnenden Vergleiche zu reduzieren.
  • In einigen Fällen (z. B. Video Copy Detection: Suche nach ähnlichen Subzeitreihen) wird die Dreiecksungleichung nur in bestimmten Fällen erfüllt. Selbst dieses teilweise Erfüllen der Dreiecksungleichung kann zur Indizierung ausgenutzt werden.


[Punkt]  Prof. Johann-Christoph Freytag

[aktiver Punkt]  Jörg Bachmann

[Punkt]  Saliha Irem Besik

[Punkt]  Fabian Fier

[Punkt]  Daniel Janusz

[Punkt]  Mathias Peters

[Punkt]  Jochen Taeschner

[Punkt]  Steffen Zeuch

[Punkt]  Christine Henze

[Punkt]  Thomas Morgenstern

[Punkt]  Martin Kost

[Punkt]  Heinz Werner