Similarity Search in Large Databases
News
- The joint kick-off meeting for all groups will take place on October 7, 2026 during the afternoon session at 14:15 in HS I – Christian Doppler. Attendance is mandatory.
About this Course
This course is included in the curricula of the following study programs:
- Master Computer Science (5 ECTS, UV)
- Master Data Science (5 ECTS, VO + PS)
Only the UV format is available in PlusOnline. Students enrolled in the Master Data Science program may register for the UV. After successfully completing the course, they can request recognition of the UV as separate VO and PS courses, as required by their study plan.
Questions and discussions
For questions and discussions about course-specific topics, including discussions among students, please use the Slack channel #ssdb-uv (workspace dbteaching.slack.com).
Slack registration: Students can register using their university email address here: https://dbteaching.slack.com/signup
Schedule
Course schedule according to PlusOnline. Changes to the schedule will be announced in the Slack channel #ssdb-uv and/or on the course website.
Lecture Material
Slides
Each set of slides covers a specific topic area and will be discussed in one or more lecture units. Slides that have not yet been discussed during the lecture may be subject to change. Once a slide set has been discussed in class, only corrections will be made. Each slide set has a version date on its title page.
The slides and their discussion during the lecture are essential for exam preparation.
Note: The slides from last year are already online to give you an overview, but they may be subject to change.
| Unit | Topics | Slides |
|---|---|---|
| 0. | Course Organisation and Demo | [1up] [4up] |
| 1. | Introduction to Similarity Search | [1up] [4up] |
| 2. | Edit Distance: Definition, Brute Force Algorithm, Dynamic Programming Algorithm, Edit Distance Variants | [1up] [4up] |
| 3. | 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. | Set Similarity Join: Signatures for Overlap and Hamming Distance, Implementation | [1up] [4up] |
| 5. | Trees: Tree Definition | [1up] [4up] |
| 6. | Tree Edit Distance: Definition, Edit Cost, Edit Mapping, Deriving the Recursive Formulas, Dynamic Programming Algorithm, Complexity | [1up] [4up] |
| 7. | Pruning: Traversal String Lower Bound, Constrained Edit Distance Upper Bound | [1up] [4up] |
| 8. | Token-Based Tree Distances: Tree Tokens, Binary Branches, pq-Grams | [1up] [4up] |
Grading
The course grade is based on:
- Two midterms: You will write two midterm exams.
- Homework and presentations: You will solve exercises at home and present your solutions in class.
The two midterms together contribute a maximum of 32 points, and the homework component contributes a maximum of 32 points for a total of 64 points.
Midterm Exams
The midterm exams will take place on the following dates:
- Wed Dec 2
- Wed Jan 27
You can earn a total of 32 points for the two midterms.
Cheat sheet: You may use one A4 sheet with your personal notes (single-sided, handwritten or printed).
Homework
You will solve exercises from worksheets at home during the semester. There will be 32 exercises in total. You do not have to solve all exercises. By the due date indicated on each worksheet, mark only the exercises you have completed as solved in Blackboard. Grading depends on both the number of solved exercises (#S) and the quality of the presentations (presentation factor PF). Each worksheet will be available at least 6 days before its due date.
Worksheet Presentation Schedule
| Date | Worksheet No. |
|---|---|
| 2026-11-04 | Worksheet 01 |
| 2026-11-11 | Worksheet 02 |
| 2026-11-18 | Worksheet 03 |
| 2026-11-25 | Worksheet 04 |
| 2026-12-09 | Worksheet 05 |
| 2026-12-16 | Worksheet 06 |
| 2027-01-13 | Worksheet 07 |
| 2027-01-20 | Worksheet 08 |
Presentations in Class
For each exercise on the worksheet, the lecturer will select a student who has marked that exercise as solved and ask the student to present the solution.
The quality of the presentation will be rated A, B, or C. The presentation will be assessed according to the following criteria:
- the technical correctness of the solution,
- the clarity of the presentation,
- the correct use of terminology, and
- the ability to answer in-depth questions.
Presentation ratings:
- A: excellent presentation and in-depth understanding of the solution
- B: sufficient understanding and presentation of the solution
- C: poor presentation or insufficient understanding of the solution
Each student starts with a presentation factor PF = 1. Each worksheet presentation contributes to the presentation factor PF as follows:
- If your presentation is rated A, then
PF <- PF + 0.25. - If your presentation is rated B, then PF remains unchanged.
- If your presentation is rated C, then
PF <- PF - 0.25.
The score for the homework assignments is then given by H = min{max{0, PF * #S}, 32}.
Absence during Class
If you are unable to attend a lab due to illness, you must provide a valid medical certificate. In addition, you must submit your solutions to the worksheet before the start of the class. The worksheet will be graded based on the submitted solutions. If you are absent without a valid medical certificate, the exercises from the corresponding worksheet will not count as solved.
Scores and Grades
The overall score is the sum of the midterm scores and the homework score. The maximum overall score is 64.
Passing the course requires meeting all of the following conditions. Failure to meet any of these conditions will result in a negative final grade of 5:
- achieving 50% of the total score achievable in the midterms,
- achieving 60% of the total score achievable for the homework assignments (
H >= 19), and - achieving an overall score of at least 32.
If these conditions are met, the final grade is computed from the overall score as follows:
| Score | Grade |
|---|---|
| [56, 64] | 1 |
| [48, 56) | 2 |
| [40, 48) | 3 |
| [32, 40) | 4 |
| [0, 32) | 5 |
Attendance and unenrollment:
Attendance at the kick-off meeting and the midterm exams is compulsory. Students must further attend at least 75% of the lab sessions with worksheet presentations to achieve a positive grade.
Unenrollment is possible only before the 3rd course unit (planned for October 28, 2026, at 14:15). All students who are still enrolled at the time of the 3rd course unit will be graded.