| Abstract |
|
Recently graph data models have become increasingly
popular in many scientific fields. Efficient query processing
over such data is critical. Existing works often rely
on index structures that store pre-computed transitive relations
to achieve efficient graph matching. In this paper,
we present a family of stack-based algorithms to handle
path and twig pattern queries for directed acyclic graphs
(DAGs) in particular. With the worst-case space cost linearly
bounded by the number of edges in the graph, our algorithms
achieve a quadratic runtime complexity in the average
size of the query variable bindings. This is optimal
among the navigation-based graph matching algorithms.
|
 Additional Information
|
Citation:
Li Chen, Amarnath Gupta, M. Erdem Kurul,
"Efficient Algorithms for Pattern Matching on Directed Acyclic Graphs,"
icde,
pp. 384-385,
21st International Conference on Data Engineering (ICDE'05),
2005
|
