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

Themen

Indizieren und Anfragen von Graphen in Datenbanken

Seminar im Wintersemester 2007/08
Silke Trißl

Themen- und Literaturliste

Die angebotenen Themen sollen von den Teilnehmern anhand einschlägiger Literatur erarbeitet werden. Im Folgenden findet sich eine Auswahl an Referenzen. Die Basis für jeden Vortrag bildet zumeist ein Fachartikel. Die Abgrenzung des Themas erfolgt zusammen mit dem Betreuer. Die meisten der erwähnten Fachartikel lassen sich sehr schnell auf dem (Google) üblichen Weg finden, viele auch bei DBLP oder über Google Scholar. Sollte ein Artikel dennoch nicht gefunden werden, kann man auch mal unter KOBV nachsehen. Nicht alle Artikel sind jedoch frei verfügbar - Kopien gibt es in diesem Falle bei dem Betreuer.


GraphDB und Complex Networks

Literatur

Güting, R.H.
GraphDB: Modeling and Querying Graphs in Databases.
VLDB Conference 1994, 297-308.
Barabasi, A. & Oltvai, Z.N.
Network biology: understanding the cell's functional organization.
Nature Reviews Genetics, 2004, 5, 101-113.

Transitive Hülle in der Datenbank

Literatur

Ioannidis, Y.E.
On the Computation of the Transitive Closure of Relational Operators
VLDB Conference1986, 403-411 .
Lu, H.
New Strategies for Computing the Transitive Closure of a Database Relation
VLDB Conference1987, 267-274 .

Nummerierungsschema - Pre- und Postorder Labeling

Literatur

Grust, T., van Keulen, M. & Teubner, J.
Accelerating XPath evaluation in any RDBMS.
ACM Trans. Database Syst., 2004, 29, 91-131.
Agrawal, R.; Borgida, A. & Jagadish, H.V.
Efficient Management of Transitive Relationships in Large Data and Knowledge Bases.
SIGMOD Conference 1989, 253-262.

Dual Labeling

Literatur

Wang, H., He, H., Yang, J., Yu, P.S. & Yu, J.X.
Dual Labeling: Answering Graph Reachability Queries in Constant Time.
ICDE Conference 2006, 75.

Transitive Hülle mit geometrischem Ansatz

Literatur

Cheng, J., Yu, J.X., Lin, X., Wang, H. & Yu, P.S.
Fast Computation of Reachability Labeling for Large Graphs.
EDBT Conference 2006, 961-979.

Distanz-Orakel

Literatur

Thorup, M. & Zwick, U.
Approximate Distance Oracles.
J. ACM 2005, 52, 1-24.

Index für Distanzen mit Update-Problematik

Literatur

Geerts, F., Revesz, P.Z. & Bussche, J.V.d.
On-line Maintenance of Simplified Weighted Graphs for Efficient Distance Queries.
Symposium on Geographic Information Systems 2006, 203-210.

Straßennetzwerk - Hierarchie-Ansatz

Literatur

Corman, T., Leiserson, C., Riverst, R. & Stein, C.
Introduction to Algorithms.
The MIT Press 2003, Chapter 24.3 Dijkstra's algorithm
Sanders, P. & Schultes, D.
Highway Hierarchies Hasten Exact Shortest Path Queries
European Symposium on Algorithms 2005, 568-579.

Straßennetzwerk - Transit-Knoten-Ansatz

Literatur

Bast, H.; Funke, S. & Matijevic
TRANSIT: Ultrafast Shortest-Path Queries with Linear-Time Preprocessing
DIMACS, 2006.
Bast, H., Funke, S., Matijevic, D., Sanders, P. & Schultes, D.
In Transit to Constant Time Shortest-Path Queries in Road Networks
SIAM, 2007, 46-59.

Twig-Query Processing auf Bäumen

Literatur

Bruno, N., Koudas, N. & Srivastava, D.
Holistic Twig Joins: Optimal XML Pattern Matching
SIGMOD Conference 2002, 310-321.

XML Query Optimierung

Literatur

Wu, Y., Patel, J.M. & Jagadish, H.V.
Structural Join Order Selection for XML Query Optimization.
ICDE Conference 2003, 443-454.
Wu, Y., Patel, J.M. & Jagadish, H.V.
Using histograms to estimate answer sizes for XML queries.
Inf. Syst., 2003, 28, 33-59.

Closure-Trees: Ähnlichkeit von häufigen Subgraphen

Literatur

He, H. & Singh, A.K.
Closure-Tree: An Index Structure for Graph Queries.
ICDE Conference 2006, 38.

Indizierung von Graphen durch häufige Subgraphen(1)

Literatur

Yan, X., Yu, P.S. & Han, J.
Graph indexing based on discriminative frequent structure analysis.
ACM Trans. Database Syst., 2005, 30, 960-993.

Indizierung von Graphen durch häufige Subgraphen(2)

Literatur

Cheng, J.; Ke, Y.; Ng, W. & Lu, A.
FG-Index: Towards Verification-Free Query Processing on Graph Databases.
SIGMOD Conference 2007, 857-872.

Graphanfragen - Sprachen und Umsetzung

Literatur

Leser, U.
A query language for biological networks.
Bioinformatics, 2005, 21 Suppl 2, ii33-ii39.
Eckman, B.A. & Brown, P.G.
Graph data management for molecular and cell biology
IBM J. Res & Dev., 2006, 50, 545 - 560.
Sohler, F.; Hanisch, D. & Zimmer, R.
New methods for joint analysis of biological networks and expression data.
Bioinformatics, 2004, 20, 1517-1521.

QPath - Suche nach Pfaden

Literatur

Shlomi, T.; Segal, D.; Ruppin, E. & Sharan, R.
QPath: a method for querying pathways in a protein-protein interaction network.
BMC Bioinformatics, 2006, 7, 199.

Netzwerke miteinander vergleichen

Literatur

Koyutürk, M., Grama, A. & Szpankowski, W.
An efficient algorithm for detecting frequent subgraphs in biological networks.
Bioinformatics, 2004, 20 Suppl 1, i200-i207.
Singh, R., Xu, J. & Berger, B.
Pairwise Global Alignment of Protein Interaction Networks by Matching Neighborhood Topology.
RECOMB, 2007, pages 16-31.

Allgemeine Literatur

Kurze Übersichten und Einführungen in die Materie finden sich in vielen Vorlesungsskripten und guten Standardwerken. Im Folgenden präsentieren wir eine Auswahl.

Vortrag und Ausarbeitung

Für das Seminar sind Folien für den Vortrag zu erstellen. Dafür gibt es keine Vorgaben, unsere Empfehlung ist es allerdings, dies in Microsoft PowerPoint oder in OpenOffice zu tun. Für den Aufbau des Vortrags und auch der Ausarbeitung sind im Anschluß noch einige Buchreferenzen für das Publizieren wissenschaftlicher Texte gegeben. Die Vorträge werden während des Blockseminars dann auf einem Windows-Rechner präsentiert.

Die Ausarbeitung ist in LaTeX zu machen. LaTeX ist eigentlich das einzige bekannte Satzsystem, mit dem man auch größere Texte und insbesondere mathematische Formeln bequem handhaben kann. In vielen Bereichen des wissenschaftlichen Publizierens wird diese System standardmäßig eingesetzt.
Unten ist ein on-line Tutorial angegeben, aber über Google findet man noch vieles mehr. Es gibt verschiedenste LaTeX-Bücher (auch in der Bibliothek) die sicherlich auch weiterhelfen können.
Die LateX-Vorlage fü die Ausarbeitung ist ebenfalls unten mit Beispielen zu finden.

Ebel H.F., Bliefert C.
Schreiben und Publizieren in den Naturwissenschaften.
Wiley-Vch 1998.
Rossig W. E., Prätsch J.
Wissenschaftliche Arbeiten
Weyhe 2005
Universität Gießen
Kochbuch für Latex
http://www.uni-giessen.de/hrz/tex/cookbook/cookbook.html
Mittelbach F.
The LaTeX Companion, w. CD-ROM
Addison-Wesley Professional 2004.

Latex-Vorlage

[Nach oben] - zurück zum Seminar