Stack-based algorithms for pattern matching on DAGs Export

@inproceedings{citeulike:4168416, abstract = {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.}, author = {Chen, Li and Gupta, Amarnath and Kurul, Erdem M.}, booktitle = {VLDB '05: Proceedings of the 31st international conference on Very large data bases}, citeulike-article-id = {4168416}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1083592.1083651}, isbn = {1-59593-154-6}, keywords = {graph-pattern, holistic-twig-join, xml}, location = {Trondheim, Norway}, pages = {493--504}, posted-at = {2009-04-19 16:14:04}, priority = {2}, publisher = {VLDB Endowment}, title = {Stack-based algorithms for pattern matching on DAGs}, url = {http://portal.acm.org/citation.cfm?id=1083592.1083651}, year = {2005} }

TY - CONF ID - citeulike:4168416 L3 - citeulike-article-id:4168416 N2 - 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. CY - Trondheim, Norway SN - 1-59593-154-6 EP - 504 TI - Stack-based algorithms for pattern matching on DAGs PB - VLDB Endowment T2 - VLDB '05: Proceedings of the 31st international conference on Very large data bases SP - 493 KW - graph-pattern KW - holistic-twig-join KW - xml AU - Chen, Li AU - Gupta, Amarnath AU - Kurul, Erdem PY - 2005/// UR - http://portal.acm.org/citation.cfm?id=1083592.1083651 ER -