Campus Event Calendar
Event Entry
What and Who
Indexing and Querying Graphs
Silke Trißl
Humbold-Universität zu Berlin
Talk
AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 2 August 2007
10:00
90 Minutes
E1 4
433 (Rotunda 4th floor)
Saarbrücken
Abstract
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.
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.
Contact
Ralf Schenkel
+49 681 9325 504
--email hidden
passcode not visible
logged in users only
Ralf Schenkel, 07/26/2007 12:52 -- Created document.