Similarity Search Algorithms

Note

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

Betreuer

Dustin Lange, Tobias Vogel, Uwe Draisbach, Prof. Dr. Felix Naumann

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.

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.
  • Tutorial
  • Google Books

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:

• Similarity Search Wiki
• Similarity Search Lecture