Reading Course "Graph Data Management"

Information

Lecturer	Dan Olteanu
Term	Trinity Term 2011
Sessions	Fridays 3pm-4pm in weeks 1-6 in Room 147

News

May 6, 2011 at 4pm in 147: We have a guest talk after the seminar in week 1: Vasilis Vasaitis talking about second order B+-trees.

Overview

This is a reading course for MSc and DPhil students. The goal is to discuss several research papers and surveys in graph data management.

Attending this seminar can count as one of the four courses that DPhil students have to take in their first year. The students will present one of the papers listed below and answer related questions.
There are seven slots in total for presentations, each presentation should take roughly 45 minutes with questions.
For any questions regarding this course, please contact Dan Olteanu.

Topics and research papers

[Week 1] Graph Data Models and Query Languages
- Survey of graph database models. R. Angles and C. Gutierrez. In ACM Comput. Surv., 40(1), 2008.
Presentation by Tim Furche.
[Week 2] Graph Databases
- An Overview of Existing Graph Databases, such as Neo4J, GraphDB, DEX, and others.
Presentation by Emanuel Ferm.
[Week 3] Reachability Queries on Graphs
- Efficiently answering reachability queries on very large directed graphs. R. Jin, Y. Xiang, N. Ruan, and H. Wang. In SIGMOD '08.
- 3-HOP: a high-compression indexing scheme for reachability query. R. Jin, Y. Xiang, N. Ruan, and D. Fuhry. In SIGMOD '09.
- A memory efficient reachability data structure through bit vector compression. Sebastiaan J. van Schaik and Oege de Moor. In SIGMOD '11.
Presentation by Sebastiaan van Schaik.
[Week 4] Shortest Path Queries on Graphs
- TEDI: Efficient Shortest Path Query Answering on Graphs. Fang Wei. In SIGMOD'10.
- Graph minors iii: Planar tree-width. P. D. Robertson, Neil; Seymour. In Journal of Combinatorial Theory, Series B 36:49-64. 1984.
- A tourist guide through treewidth. H. L. Bodlaender. Acta Cybernetica, 11:1-23. 1993.
- Tractable database design through bounded treewidth. G. Gottlob, R. Pichler, and F. Wei. In PODS, pages 124-133. 2006.
Presentation by Jakub Závodný.
[Week 5] Database Support for Social Networks
- The little engine(s) that could: scaling online social networks. Josep M. Pujol, Vijay Erramilli, Georgos Siganos, Xiaoyuan Yang, Nikos Laoutaris, Parminder Chhabra, Pablo Rodriguez. In ACM SIGCOMM '10.
Presentation by Andrey Kravchenko.
[Week 6] Mining Frequent Subgraphs Graph Indices
- Mining Frequent Subgraph Patterns from Uncertain Graph Data. Z. Zou, J. Li, H. Gao, S. Zhang. In TKDE'10.
Presentation by Ramon Granell.