Direkt zum InhaltDirekt zur SucheDirekt zur Navigation
▼ Zielgruppen ▼
 

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

Seminar Indizierung von Graphen

Indizieren und Anfragen von Graphen in Datenbanken

Seminar im Wintersemester 2007/08
Silke Trißl

Übersicht




Inhalt

In diesem Seminar werden Arbeiten zum Indizieren und Anfragen von Graphen in Datenbanken besprochen. Dabei werden Themen wie die Indizierung von Graphen zur Beantwortung von Erreichbarkeits-, aber auch Distanz und Pfadanfragen besprochen. Dazu ist in der Literatur in den letzten Jahren einiges erschienen. Stehen Indexe zur Verfügung, mit denen solche Anfragen schnell zu beantworten sind, dann kann man auch Anfrageoptimierung betreiben, wie sie aus der Datenbankforschung bekannt ist.
Ein etwas anderes Thema ist die Indizierung von vielen kleinen Graphen, um nach homologen Subgraphen zu suchen. Auch darüber gibt es einige kürzlich erschiene Arbeiten. Wenn wir solche Graphen gefunden haben, möchten wir bestimmen, welche Graphen sich am ähnlichsten sind. Dazu gibt es einige Arbeiten, die eine 'Edit-Distanz' für Bäume und Graphen definieren. Auch diese Arbeiten werden wir uns während des Seminars ansehen.



Zeit und Ort

Das Seminar findet im Wintersemester als Blockseminar statt.
Der Termin für die Einführungsveranstaltung mit Vergabe der Themen ist der 23.10.2007 um 9 Uhr c.t. in RUD25, Raum 3.101. Dieser Termin ist eine Pflichtveranstaltung.
An diesem Termin wird auch der Termin für die Blockveranstaltung besprochen, die voraussichtlich am 12. und 19. Februar 2008 stattfinden wird.
Eine weitere Veranstaltung findet am 30.10.2007 um 9 Uhr c.t. ebenfalls in RUD25, Raum 3.101 statt. In dieser Veranstaltung gibt es auch eine Einführung in LaTeX.
Zusätzlich zur Blockveranstaltung gibt es auch noch eine Kurz-Präsentation der Themen, voraussichtlich am 08. Januar 2008.

Die Ausarbeitung zum Seminar muss am 21. Dezember 2007 abgegeben werden.


Themen

Die Themen werden bei der Einführungsveranstaltung vergeben. Die Themen im Einzelnen sind (Literaturliste):

Allgemeine Literatur
  Einführungsveranstaltung   [Folien]
  LaTeX   [Folien]
0 GraphDB, Complex Networks Alle -
Erreichbarkeitsanfragen
1 Transitive Hülle in der Datenbank - -
2 Nummerierungsschema - Pre- und Postorder Labeling Ganzer -
3 Dual Labeling - -
4 Transitive Hülle mit geometrischem Ansatz Shakhawat [Ausarbeitung]
Distanzanfragen
5 Distanz-Orakel Serediouk -
6 Index für Distanzen mit Update-Problematik - -
7 Straßennetzwerk - Hierarchie-Ansatz Wickert [Ausarbeitung]
8 Straßennetzwerk - Transit-Knoten-Ansatz Kibanov -
Anfrageoptimierung
9 Twig-Query Processing auf Bäumen Schulze -
10 XML Query Optimierung Sax [Ausarbeitung]
Suche nach Graphen
11 Closure-Trees: Ähnlichkeit von häufigen Subgraphen - -
12 Indizierung von Graphen durch häufige Subgraphen (1) Hellwig [Ausarbeitung]
13 Indizierung von Graphen durch häufige Subgraphen (2) Tsitiridou [Ausarbeitung]
Graphen & Biologie
14 Graphanfragen - Sprachen und Umsetzung - -
15 QPath - Suche nach Pfaden - -
16 Biologische Netzwerke vergleichen Kunath -



Teilnahmevoraussetzungen

Teilnahmeberechtigt sind alle Studenten der Informatik im Hauptstudium, die Interesse an dem Thema haben. Die Anmeldung zum Seminar erfolgt ausschließlich über Goya.



Scheinerwerb

Die Teilnehmer/innen des Seminars können am Ende einen Schein erhalten. Voraussetzungen dafür sind die aktive Teilnahme am Seminar, die Präsentation eines ausgewählten Themas, sowie die Anfertigung einer schriftlichen Ausarbeitung über dieses Thema (10-15 Seiten).
Verpflichtend ist die Teilnahme bei der Themenvergabe, an der Vorbesprechung sowie die Anwesenheit bei allen Vorträgen. Jeder Vortrag wird ca. 45 Minuten dauern und muss selbstständig erstellt sein. Ein Kurzvortrag soll etwa 5 Minuten dauern.
Das Thema ist mit dem Betreuer vor dem 07. Dezember 2007 und die Vortragsfolien etwa eine Woche vor dem Blockseminar zu besprechen. Termine für beide Vorbesprechungen (Thema & Folien) bitte rechtzeitig mir abklären. Die Anmeldung zum Seminar erfolgt ausschließlich über Goya.
Die Ausarbeitung ist ausschließlich mit LateX zu erstellen, die LateX-Vorlage ist unter 'Zusätzliches Material' zu finden.
Vorträge und Ausarbeitung können mit dem jeweiligen Betreuer der Arbeit nachbesprochen werden. Termine hierfür bitte individuell vereinbaren.



Vorträge

Das Blockseminar findet am Dienstag, den 19.02.2008 in der Zeit von 10 - 15 Uhr in RUD25, Haus 3, Raum 113.

Erreichbarkeitsanfragen
4 Transitive Hülle mit geometrischem Ansatz Shakhawat [Vortrag]
Anfrageoptimierung
10 XML Query Optimierung Sax [Vortrag]
Distanzanfragen
7 Straßennetzwerk - Hierarchie-Ansatz Wickert [Vortrag]
Suche nach Graphen
12 Indizierung von Graphen durch häufige Subgraphen (1) Hellwig [Vortrag]
13 Indizierung von Graphen durch häufige Subgraphen (2) Tsitiridou [Vortrag]


Kontakt

Bei Fragen wenden Sie sich bitte an Silke Trißl, RUD25, IV.116.