Campus Event Calendar
Event Entry
What and Who
PhD Application Talk: Tree 2-Hop Cover. An index structure for connectivity tests in graph databases
Christoph Wagner
Talk
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, RG2
MPI Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 25 February 2008
09:00
330 Minutes
E1 4
024
Saarbrücken
Abstract
Due to the growing number and size of well-analyzed metabolic networks, efficient access methods and query algorithms for graph structured data become more relevant. Up to now, queries on graph structured data are not supported sufficiently by current database managent systems. In my thesis, a new index structure called "Tree 2-Hop Cover" is developed, which allows to determine the reachability of nodes in a directed graph. The index is based on "2-Hop Cover", a data structure developed by Cohen et al., and combines the latter with the well-known concepts of strongly connected components and spanning trees. With this index structure, it is possible to create an index which needs less storage space than the original 2-Hop Cover. Furthermore, it is shown that the query times in relational databases for both 2-Hop Cover and Tree 2-Hop Cover are relatively independent of the graph size and thus approximately constant.
Contact
IMPRS-Cs
225
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Please note: The talks will take place in random order!
Lourdes Lara-Tapia, 02/22/2008 15:12
Lourdes Lara-Tapia, 02/21/2008 18:17 -- Created document.
Lourdes Lara-Tapia, 02/21/2008 18:17 -- Created document.