Similarity Search Algorithms (Sommersemester 2010)
Dozent:
Prof. Dr. Felix Naumann
(Information Systems)
Website zum Kurs:
http://www.hpi.uni-potsdam.de/naumann/teaching/ss_10/similarity_search_algorithms.html
Allgemeine Information
- Semesterwochenstunden: 4
- ECTS: 6
- Benotet:
Ja
- Einschreibefrist: 10.05.2010
- Lehrform:
- Belegungsart: Wahlpflichtmodul
Studiengänge
- IT-Systems Engineering MA
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
Lern- und Lehrformen
Projektseminar im Umfang von 4 SWS
Leistungserfassung
- 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
Termine
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
