[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
Institut für Informatik
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
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
Eva Nedoma Vienna University of Technology
Inst. for Information Systems Knowledge Based Systems Group
Favoritenstr. 9-11/184-3, A-1040 Vienna e-mail: firstname.lastname@example.org
Tel: +43 (01) 58801 18405 Fax: +43 (01) 58801 18493