Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Institut für Informatik

Diplomverteidigung, Alexander Konrad

  • Wann 23.05.2017 von 11:00 bis 12:00
  • Wo 12489 Adlershof, Rudower Chaussee 25, Haus IV, Raum 210
  • iCal

Herr Alexander Konrad verteidigt seine Diplomarbeit zum Thema:

"Optimierung der Nächsten-Nachbarn-Suche in Metrischen Indexen"

Alle Interessenten sind herzlich eingeladen!

 


 

Abstract:

Eine Suche nach Elementen in unstrukturierten Daten, wie zum Beispiel Bilder oder Zeitreihen, kann als Nächste-Nachbarn-Suche (NN-Suche) ausgedrückt werden. Dabei werden Elemente gesucht, die einem Anfrage-Element ähnlich sind. Die Ähnlichkeit zwischen zwei Elementen wird über ein Abstandsmaß definiert. Die Berechnung eines Abstandes kann hohe Komplexität aufweisen und daher in der Ausführungszeit teuer sein. Zur Verbesserung der Berechnungszeit können günstigere untere Schranken eingesetzt werden. Eine Kaskade von unteren Schranken mit zunehmender Genauigkeit kann das Ergebnis immer weiter verfeinern und spart teure Berechnungen ein. Eine weitere Methode stellt die Indexierung der Datenelemente dar. Eine NN-Suche in einem Index kann ebenfalls Berechnungen des teuren Abstandsmaßes einsparen und damit die Suche beschleunigen. Das Konzept der Kaskade wird in dieser Arbeit auf die NN-Suche in indexierten Daten übertragen. Diese Arbeit verbindet beide Konzepte. Es wird ein Algorithmus vorgestellt, der durch eine Kaskade von Abstandsmaßen teure Distanzberechnungen einspart, als auch das Einsparungspotential von Indexstrukturen ausnutzt.