Hasso-Plattner-Institut
  
Hasso-Plattner-Institut
Prof. Dr. Felix Naumann
  
 

Note

See also our project page on similarity search with recent publications.

Beschreibung

Die Beschränkung von Suchanfragen auf exakte Ergebnisse ist nicht mehr zeitgemäß. Grund hierfür können Tippfehler oder unvollständige Daten im Datenbestand bzw. fehlendes Wissen der Nutzer über die gesuchten Objekte sein. Der Vergleich der Suchanfrage mit allen existierenden Objekten ist bei den heutigen Datenmengen zumeist ineffizient. Übliche Indexierungstechniken für die exakte Suche, wie sie aus dem Datenbankbereich seit vielen Jahren bekannt sind, bilden oben genannte Abweichungen nicht ab und können daher bei ungenauen Anfragen nicht verwendet werden.

In diesem Seminar beschäftigen wir uns mit Algorithmen zur effizienten Ähnlichkeitssuche. Diese Verfahren finden zu einer Anfrage auch bei Abweichungen passende Tupel in verschiedenen Datenbeständen. Wir untersuchen verschiedene Lösungsansätze und wollen die Qualität dieser Ansätze anhand eigener Implementierungen evaluieren.

Anwendungsbeispiele:

  • Suche ähnlicher Datenbanktupel (z.B. Anfrage "Meier", Ergebnismenge {"Meier", "Maier", "Meyer", "Mayer"})
  • Plagiatsuche (z.B. wissenschaftliche Texte)
  • Suche ähnlicher Bilder zu einem gegebenen Bild

Ergebnisse

Im Rahmen des Seminars wurde eine webbasierte Anfrageschnittstelle entwickelt, die das Anfragen verschiedener Datensätze mit unterschiedlichen Indexstrukturen ermöglicht. 

Zu diesem Seminar ist ein Bericht im Datenbank-Spektrum erschienen.

Themen und Termine

Themen:

  1. VP-tree

    Peter N. Yianilos. Data structures and algorithms for nearest neighbor search in general metric spaces. In SODA: ACM-SIAM Symposium on Discrete Algorithms (A Conference on Theoretical and Experimental Analysis of Discrete Algorithms), 1993.

  2. GNAT

    Sergey Brin. Near neighbor search in large metric spaces. In The VLDB Journal, pages 574–584, 1995.

  3. MVP-tree

    Tolga Bozkaya, Meral Ozsoyoglu. Distance-based indexing for high-dimensional metric spaces. In Proc. ACM SIGMOD International Conference on Management of Data, pages 357-368, 1997.

  4. M-tree

    Paolo Ciaccia, Marco Patella, and Pavel Zezula. M-tree: An efficient access method for similarity search in metric spaces. In Proceedings of the 23rd VLDB International Conference, Athens, Greece, September 1997.

  5. D-index

    Vlastislav Dohnal, Claudio Gennaro, Pasquale Savino, and Pavel Zezula. D-index: Distance searching index for metric data sets. Multimedia Tools Appl., 21(1):9–33, 2003.

  6. LAESA

    Mará Luisa Micó, José Oncina, and Enrique Vidal. A new version of the nearest-neighbour approximating and eliminating search algorithm (AESA) with linear preprocessing time and memory requirements. Pattern Recogn. Lett., 15(1):9–17, 1994.

 

Termine:

Das Seminar findet montags, 15:15-16:45 Uhr in Seminarraum A-1.2 statt.

Die Frist für die Anmeldung mit Wunschpartner und Wunschthema (Daten + Indexstruktur) per E-Mail an Dustin Lange ist der 26.04.2010.

Wann? Was?
19.04.2010Eröffnungsveranstaltung, Themenvorstellung (Folien, Datensatzbeschreibungen)
26.04.2010Anmeldefrist per E-Mail an Dustin Lange (mit Wunschpartner und Wunschthemen)
03.05.2010Einführung in das Framework und die GUI (Folien)
17.05.2010Präsentation der Ähnlichkeitsmaße (6 Vorträge)
07.06.2010Präsentation der Indexierungsalgorithmen (3 Vorträge)
14.06.2010Präsentation der Indexierungsalgorithmen (3 Vorträge)
19.07.2010Präsentation der Implementierungen und Evaluierungsergebnisse (3 Vorträge)
26.07.2010

Präsentation der Implementierungen und Evaluierungsergebnisse (3 Vorträge)

31.08.2010Abgabe Implementierung und Ausarbeitung

 

Eine Woche vor jedem Vortrag muss jedes Team/jeder Teilnehmer ein Betreuungsgespräch führen.

Anforderungen

  • Kenntnisse in Java und ggf. anderen Programmiersprachen
  • Hilfreich sind Vorkenntnisse über Indexierungstechniken für exakte Suche in Datenbanken (bekannt aus DBS II).

Leistungserfassungsprozess

  • Teilnahme an allen Seminarterminen
  • Implementierung eines Algorithmus' zur Erstellung einer Similarity-Search-Indexstruktur sowie zur Suche in/auf/über diesem Index
  • Implementierung von zwei Ähnlichkeitsfunktionen in vorgegebenen Domänen
  • 1. Vortrag: Ähnlichkeitsmaß vorstellen (ca. 10-15 min)
  • 2. Vortrag: Indexierungsalgorithmus vorstellen (ca. 20-25 min)
  • 3. Vortrag: Implementierung/Evaluierungsergebnisse vorstellen (ca. 20-25 min)
  • Regelmäßige Gespräche mit Betreuer
  • Ausführliche Dokumentation im Trac-Wiki (5 Druckseiten)
  • Abschlussnote berücksichtigt die folgenden Punkte

    • Implementierte Lösung
    • Vorträge
    • Dokumentation im Trac-Wiki
    • Mündliche Beteiligung
    • Regelmäßige Treffen mit dem Betreuer

Lehr- und Lernformen

Projektseminar im Umfang von 6 Leistungspunkten.

Literatur

Einführung:

  • Pavel Zezula, Giuseppe Amato, Vlastislav Dohnal, and Michal Batko. Similarity Search - The Metric Space Approach. Springer, Series: Advances in Database Systems, Vol. 32, 2006, XVIII, ISBN: 0-387-29146-6.

Survey-Paper:

  • Edgar Chávez, Gonzalo Navarro, Ricardo Baeza-Yates, and José Luis Marroqun. Searching in metric spaces. ACM Comput. Surv., 33(3):273–321, 2001.
  • Gisli R. Hjaltason and Hanan Samet. Index-driven similarity search in metric spaces. ACM Transactions on Database Systems, 28:2003, 2003.

Weitere hilfreiche Links: