Similarity Search Algorithms (Sommersemester 2010)

Lecturer: Prof. Dr. Felix Naumann (Information Systems)
Course Website: http://www.hpi.uni-potsdam.de/naumann/teaching/ss_10/similarity_search_algorithms.html

General Information

Weekly Hours: 4
Credits: 6
Graded: yes
Enrolment Deadline: 10.05.2010
Teaching Form:
Enrolment Type: Compulsory Elective Module

Programs

IT-Systems Engineering MA

Description

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

Learning

Projektseminar im Umfang von 4 SWS

Examination

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

Dates

Die Frist für die Anmeldung mit Wunschpartner und Wunschthema (Daten + Indexstruktur) per E-Mail an Dustin Lange ist der 26.04.2010. Es können maximal 12 Studenten (6 Teams à 2 Studenten) zugelassen werden.

Zurück