[Date Prev][Date Next][Date Index]

Vortragsankündigung Fang Wei "Treewidth-based Index for Efficient Reachability Query Answering on Digraphs" am 17.2.2009



Der Arbeitsbereich für Datenbanken und Artificial Intelligence am Institut
für Informationssysteme lädt zum folgenden Vortrag:

===================================================================


Dr. Fang Wei
http://dbis.informatik.uni-freiburg.de/index.php?person=fwei

Institut für Informatik
Albert-Ludwigs-Universität Freiburg

DATUM: Dienstag, 17.2.2009
ZEIT:  14-15 Uhr
ORT:   Seminarraum 184/2, 3.Stock, Favoritenstr. 9-11

Treewidth-based Index for Efficient Reachability Query Answering on 
Digraphs

Efficiently processing queries against very large graphs is an important
research topic largely driven by emerging real world applications, as
diverse as XML databases, GIS, web mining, social network analysis, 
ontologies, and bioinformatics. In particular, graph reachability has 
attracted a lot of research attention as reachability queries are not only 
common on graph databases, but they also serve as fundamental operations 
for many other graph queries. The main challenge of answering reachability 
queries is how to build efficient indices over the graphs in order to 
achieve the best space/time performance.

Many approaches have been proposed for building indices on these graphs.
However, due to the large number of vertices in many real world graphs, 
the computational cost and (index) size of the indices using existing 
methods would prove too expensive to be practical.

In this talk, we introduce our ongoing work on a novel index structure 
based on the treewidth of the underlying graph. We show that the size of 
the index for the underlying graph remains linear and the reachability 
query can be solved in $O(log n)$ where $n$ is the number of vertices in 
the graph. We demonstrate empirically the effectiveness of our approach.



Mit Unterstützung des Wolfgang-Pauli-Instituts und des Zentrums für
Informatikforschung


--
Eva Nedoma					Vienna University of Technology
Inst. for Information Systems			Knowledge Based Systems Group
Favoritenstr. 9-11/184-3, A-1040 Vienna		e-mail: eva@kr.tuwien.ac.at
Tel: +43 (01) 58801 18405			Fax: +43 (01) 58801 18493


DVR 0005886