| 08.06.2011 |
Course evaluation: WS 2010/2011 |
| 26.01.2011 |
Project Presentations on Jan 31, 2011: Project
presentations on Jan 31, 14:30–17:45 (during lecture and lab). |
| 17.01.2011 |
No Lecture on Jan 24, 2011: The lecture of Jan 24 is
rescheduled to Wednesday, Jan 19, 8:30-10:00. |
| 20.12.2010 |
Updated project site: You find hints for doing good
experiments and links to test data on the project web site. |
| 20.12.2010 |
Deadline extended: The deadline for milestone 2 (Dec 20) has been extended to December 22. |
| 16.12.2010 |
The exam date has been fixed: Monday, Feburary 14, 2011 |
| 13.12.2010 |
Die Anmeldung zur Prüfung ist geöffnet. Prüfungsnummer: IN 310002 |
| 26.10.2010 |
Am Montag, 01.11.2010, findet keine Vorlesung statt. |
| 14.10.2010 |
Am Montag, 18.10.2010, findet keine Vorlesung statt. |
| Vorlesungsbeginn |
25.10.2010 |
| Vorlesungstermin |
Mo 14:30–16:00, wöchentlich |
| Vorlesungsraum |
02.09.014, Seminarraum
|
| Sprache |
Englisch |
| Inhalt |
This course will discuss similarity search techniques for
flat strings and hierarchical data (for example,
XML). Selected methods will be presented, their effectiveness
and efficiency will be discussed. Filtering techniques to
improve the efficiency will be introduced. In the exercises,
the students will implement and empirically evaluate
similarity search algorithms.
|
| Voraussetzungen |
Bachelor Informatik. Grundlagen von Datenbanken und
Algorithmen, grundlegende Kenntnisse von XML. Für die Übung
sind gute Programmierkenntnisse in Java erforderlich.
|
| Studienplan |
Ausgewählte Themen aus dem Bereich Datenbanken und
Informationssysteme (IN3100) im Studienplan von Informatik
Master/Diplom, Wirtschaftsinformatik Master.
Siehe
Beschreibung
in TUM
online.
|
| 1. Vorlesung |
General Introduction: Similarity Search, Course Organization, Introductory Example and Demo |
[1up][4up] |
| 2. Vorlesung |
String Edit Distance: Definition, Brute Force Algorithm, Dynamic Programming Algorithm, Edit Distance Variants |
[1up][4up] |
| 3. Vorlesung |
q-Gram Distance: Approximate String Join, Lower Bound Filtering, Length Filter, q-Gram Count Filter, q-Gram Position Filter, q-Gram Distance, Experiments |
[1up][4up] |
| 4. Vorlesung |
Trees and Relational Databases: Tree Definition, Adjacency List Encoding, Dewey Encoding, Interval Encoding, XML as a Tree |
[1up][4up] |
| 5. Vorlesung |
Tree Edit Distance: Definition, Edit Cost, Edit Mapping,
|
[1up][4up] |
| 6. Vorlesung |
Tree Edit Distance: Deriving the Recursive Formulas, Dynamic Programming Algorithm
|
(→ Unit 5) |
| 7. Vorlesung |
Tree Edit Distance: Dynamic Programming Algorithm, Example, Complexity
|
(→ Unit 5) |
| 8. Vorlesung |
Pruning: Traversal String Lower Bound, Constrained Edit Distance Upper Bound
|
[1up][4up] |
| 9. Vorlesung |
Reference Sets: Pruning with Reference Sets
|
[1up][4up] |
| 10. Vorlesung |
Binary Branch Distance: Algorithm, Lower Bound Proof, Complexity
|
[1up][4up] |
| 11. Vorlesung |
pq-Gram Distance: Algorithm and Lower Bound Theorem
|
[1up][4up] |
| 12. Vorlesung |
Windowed pq-Grams: Approximate Joins for Unordered Trees (Data-Centric XML)
|
[1up][4up] |
| Durchführung |
The final exam is oral. Each student will be examined
individually for 20 minutes. Here is a list of exam
questions [PDF]. The
student will randomly choose a question from the above list of
exam questions and present the topic in 20 minutes. The student
will be evaluated according to the correctness, clarity,
relevance, and completness of the answer, and the proper use of
the terminology. The examiner will ask follow-up questions, also
covering related topics, to verify the thorough understanding of
the chosen topic by the student.
|
| Anmeldung |
Die Anmeldung zur Prüfung erfolgt ausschließlich über das
TUMonline-Portal. Beachten
Sie bitte die Anmeldefristen und die Informationen zur
Anmeldung für die verschiedenen Studiengänge auf
den Webseiten
des Prüfungsamtes.
Prüfungsnummer: IN 310002
|
| Rücktritt |
Siehe allgemeine
Regelung für Rücktritte und Atteste.
|
| Ergebnisse und Notenbekanntgabe |
Die Ergebnisse werden unmittlebar nach der mündlichen Prüfung
mitgeteilt und außerdem über
das TUMonline-Portal
bekannt gegeben.
|
| Zulassung und Scheine |
Die Übungen stellen keine Zulassungsvoraussetzung für eine Teilnahme
an der Prüfung dar. Das Bestehen der Prüfung ist
Voraussetzung für den Schein.
|
