Title:   Stack-based Algorithms for Pattern Matching on DAGs
Speaker: Li Chen (SDSC)

Abstract:

Recently, graph data models have been increasingly in demand by modern
applications that utilize graph-structured data such as XML (if
considering ID and IDREF), RDF and ontology data. Existing work for query
processing over graph data models often relies on pre-computing the
transitive closure or path indexes. In this paper, we propose a family of
stack-based algorithms to handle path, twig, and dag pattern queries for
directed acyclic graphs (DAGs) in particular. Our algorithms do not
precompute the transitive closure nor path indexes for a given graph,
however they achieve an optimal runtime complexity quadratic in the
average size of the query variable bindings. We prove the soundness and
completeness of our algorithms and present the experimental results.

I will also discuss the possible directions of future work.