Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Wissensmanagement in der Bioinformatik

Seminar Similarity Search

Prof. Dr. Ulf Leser

Ähnlichkeitssuche liegt im Kern vieler Anwendungen, wie z.B. Suche nach ähnlichen Namen, nach ähnlichen Musikstücken, nach ähnlichen DNA Sequenzen, nach ähnlichen Ereignisse, nach ähnlichen Bildern, nach ähnlichen Objekten etc. Je nach Art der betrachteten Objekte (Strings, Bäume, Vektoren etc.) kommen dabei recht unterschiedliche Ähnlichkeitsmaße und Algorithmen zum Einsatz. Im Seminar betrachten wir verschiedene Probleme der (skalierbaren) Ähnlichkeitssuche und suchen nach Gemeinsamkeiten und charakteristischen Unterschieden in den verwandten Methoden.

Voraussetzungen

Gute Kenntnisse in Algorithmen, Indexstrukturen und Datenbanktechniken.

Schein und Anrechenbarkeit

Das Seminar ist anrechenbar für

  • Diplom Informatik
  • M.Sc. Informatik
  • Master Wirtschaftsinformatik

Voraussetzung für den Schein ist:

  • das Bestehen einer Kurzklausur zu Grundlagenthemen in der Mitte des Semesters (siehe unten),
  • das Halten eines wissenschaftlichen Vortrags am Ende des Semesters,
  • die einmalige Übernahme der "Opponentenrolle" (siehe unten) sowie
  • das Erstellen einer schriftlichen Ausarbeiten (Seminararbeit)

Anmeldung

Die Teilnehmerzahl ist begrenzt, die Anmeldung erfolgt über Goya.

Termine und Ablauf

Am 16.04.2012 findet von 11-13 Uhr die Einführungsveranstaltung statt, die für alle Teilnehmenden verpflichtend ist. Dort werden die Themen erläutert und vergeben.

Das Seminar wird als Blockseminar am Ende des Semesters abgehalten. Jede(r) Studierende muss einen ca. 30 minütigen Vortrag über das zugewiesene Thema halten. Vorher finden mindestens zwei Treffen mit dem/der Betreuer(in) statt, einmal zur Vorbesprechung des Themas und einmal zur Besprechung der Folien. Außerdem wird es in der Mitte des Semesters einen Termin geben, in dem alle Studierenden in einer 5-minütigen Flash-Präsentation ihr Thema vorstellen, um Querverbindungen zu erkennen und die rechtzeitige Beschäftigung mit dem Thema sicherzustellen. Schließlich muss zu jedem Thema eine 10-15 seitige Seminararbeit verfasst werden.

Zu jedem Thema wird ein(e) Studierende(r) am Semesteranfang als Opponent(in) ausgewählt. Der/Die Opponent(in) liest ebenfalls die zum Thema ausgegebene Literatur und bereitet für den Vortrag Fragen zu deren Inhalt vor, die dann im Seminar diskutiert werden. Ziel ist nicht das Aufdecken von Verständnislücken beim Vortragenden, sondern die kritische Auseinandersetzung mit dem Thema.

Zusätzlich zu der speziellen Literatur, über die die Vorträge gehalten werden, gibt es für alle Teilnehmer verpflichtende Einführungslektüre. In der Mitte des Semesters werden die dort vermittelten Kenntnisse im Rahmen einer Kurzklausur überprüft. Das Bestehen der Klausur ist Voraussetzung für die weitere Teilnahme.

Alle Pflichttermine in der Übersicht:

  • 16.04.2013, 11-13 Uhr, RUD 26 1'307: Einführung (Folien)
  • Bis 15.5.2013: Individuelle Themenbesprechung mit Betreuer(in)
  • Am 31.5.2013, 10-12 Uhr in Raum 4.112: Kurzklausur, Flash-Präsentationen aller Themen
  • Im Laufe des Juni: Individuelle Folienbesprechung mit Betreuer(in)
  • Blockseminar 1: Dienstag, 9.7., 10-12.30, EZ 0'313
  • Blockseminar 2: Freitag, 12.7., 10-12.30, EZ 1'305
  • Letzter Abgabetermin für die Seminararbeit: 30.8.2013

Vorlagen


Themen

Topic Paper Vortragende(r) Opponent(in) Betreuer(in)
Einführende Literatur für alle Teilnehmer Zezula, P., Amato, G., Dohnal, V. and Batko, M. (2006). "Similarity Search: The Metric Space Approach", Springer, Seiten 3-49      
String Similarity Join 1. Rheinländer, A., Knobloch, M., Hochmuth, N. and Leser, U. (2010). "Prefix Tree Indexing for Similarity Search and Similarity Join on Genomic Data". Int. Conf. on Scientific and Statistical Database Management, Heideberg, Germany. pp 519-536.

2. Rheinländer, A. and Leser, U. (2011). "Scalable Sequence Similarity Search and Join in Main Memory on Multi-Cores". 2nd Workshop on High Performance Bioinformatics and Biomedicine, France.

 

 Witt Adler Astrid Rheinländer
Web page duplicate detection 1. Manku, G. S., Jain, A. and Das Sarma, A. (2007). "Detecting near-duplicates for web crawling". WWW, Banff, Canada.

2. Theobald, M., Siddharth, J. and Paepcke, A. (2008). "SpotSigs: robust and efficient near duplicate detection in large web collections". SIGIR Conference on Research and Development in Information Retrieval, Singapore.

 Spindler Shi Ulf Leser
SimSearch in String Sets 1. Fenz, D., Lange, D., Rheinländer, A., Naumann, F. and Leser, U. (2012). "Efficient Similarity Search in a Very Large String Sets". Int. Conf. on Scientific and Statistical Database Management, Chania, Greece

2. Gerdjikov, S., Mihov, S., Mitankin, P. and Schulz, K. U. (2013). "WallBreaker - overcoming the wall effect in similarity search". Workshop on Scalable String Similarity Search and Join, Genua, Italy.

 Tran Salomon Sebastian Wandelt
Heuristics for fast local alignment search 1. Kent, W. J. (2002). "BLAT--the BLAST-like alignment tool." Genome Res 12(4): 656-64.

2. BLAST (irgendein Buch)

      
SimSearch mit BWT 1. Li, H. and Durbin, R. (2010). "Fast and accurate long-read alignment with Burrows-Wheeler transform." Bioinformatics 26(5): 589-95.

2. Langmead, Ben, et al. "Ultrafast and memory-efficient alignment of short DNA sequences to the human genome." Genome Biol 10.3 (2009): R25.

 Adler Valencia Ulf Leser
Multidimensional SimSearch by low dimensional embedding Hjaltason, G. R. and Samet, H. (2000). "Contractive embedding methods for similarity searching in metric spaces." Technical Report TR-4102, University of Maryland. Shi Glushanok Ulf Leser
Tree indexes for multidimensional simsearch

1. Ciaccia, P., Patella, M. and Zezula, P. (1997). "M-tree: An Efficient Access Method for Similarity Search in Metric Spaces". 23rd International Conference on Very Large Data Bases, Athens, Greece.

2. Skopal, T., J., P., Krátký, M. and Snášel, V. (2003). "Revisiting M-tree building principles". Advances in Databases and Information Systems, Dresden, Germany

 Laß Manthey Ulf Leser
SimSearch in Graphs: Subgraph matching Gouda, K. and Hassaan, M. (2013). "Compressed Feature-based Filtering and Verification Approach for Subgraph Search". Extending Database Technology, Genoa, Italy.

 

      
Graph Alignment 1. Kuchaiev, O., Milenkovi, T., Memisevic, V., Hayes, W. and Przulj, N. (2010). "Topological network alignment uncovers biological function and phylogeny." Journal of the Royal Society.

2. Przulj, N. (2007). "Biological network comparison using graphlet degree distribution." Bioinformatics 23(2): e177-83.

 Valencia Laß Andre Koschmieder
SimSearch in Workflows 1. Dijkman, R., Dumas, M. and García-Bañuelos, L. (2009). "Graph Matching Algorithms for Business Process Model Similarity Search". Business Process Management.

2.Dijkmana, R., Dumas, M., van Dongenc, B., Käärik, R. and Mendling, J. (2011). "Similarity of business process models: Metrics and evaluation." Information Systems 36(2).

      
Tree Similarity Search 1. Wang, J. T., Shan, H., Shasha, D. and Piel, W. H. (2003). "TreeRank: a similarity measure for nearest neighbor searching in phylogenetic databases. " Inc. Conf. on Scientific and Statistical Database Management.

2. Yang, R., Kalnis, P. and Tung, A. K. H. (2005). "Similarity evaluation on tree-structured data". SIGMOD, Baltimore, USA.

 Salomon Spindler Johannes Starlinger
Tree Edit Distance 1. Bille, P. (2005). "A survey on tree edit distance and related problems." Theoretical Computer Science 337(1).

2. Pawlik, M. and Augsten, N. (2011). "RTED: a robust algorithm for the tree edit distance." PVLDB 5(4).

 Glushanok Witt Ulf Leser
Similarity Search in Music Data 1. Serra, J., Gomez, E. and Herrera, P. (2010). Audio cover song identification and similarity: Background, approaches, evaluation and beyond. In (ed). Book "Advances in Music Information Retrieval", Springer Berlin Heidelberg
2. Yang, C. (2001). "Music Database Retrieval Based on Spectral Similarity". Technical Report. Stanford University. 		Manthey Tran Ulf Leser