Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Indexing and Querying Graphs
Speaker:Silke Trißl
coming from:Humbold-Universität zu Berlin
Speakers Bio:
Event Type:Talk
Visibility:D1, D3, D5, RG2, D2, D4, RG1, SWS
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 2 August 2007
Duration:90 Minutes
Building:E1 4
Room:433 (Rotunda 4th floor)
Many applications require efficient management and querying of graph structured data. For example, Systems Biology studies metabolic pathways and gene regulation networks modeled as directed graphs. These graphs consist of tens of thousands of molecules and interactions between them. To get a better understanding of these networks biologists need to query the networks and extract information.

In my talk I will briefly introduce PQL (Pathway Query Language) with which a graph query can be specified. The query graph contains nodes and paths, both of which can contain conditions such as the name of a node or the length of a path. The result of such graph queries is a set of subgraphs that match the given query graph. I will describe how to utilize techniques of classical cost-based query optimization to optimize such graph queries.

To answer reachability queries on even large graphs we developed GRIPP (GRaph Indexing based on Pre- and Postorder numbering).
GRIPP requires only linear time and space during index creation. Using GRIPP, we can answer reachability queries on average in less than 5 milliseconds on graphs with 5 million nodes and 10 million edges, which is unrivaled by previous methods. In my talk I will describe two implementations of GRIPP in more detail.

Name(s):Ralf Schenkel
Phone:+49 681 9325 504
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Ralf Schenkel, 07/26/2007 12:52 PM -- Created document.