Qiang Zeng
Abstract
The paper "Stack-based Algorithms for Pattern Matching on DAGs" generalizes the classical holistic twig join algorithms and proposes PathStackD, TwigStackD and DagStackD to respectively evaluate path, twig and DAG pattern queries on directed acyclic graphs. In this paper, we investigate the major results of that paper, pointing out several discrepancies and proposing solutions to resolving them. We show that the original algorithms do not find particular types of query solutions that are common in practice. We also analyze the effect of an underlying assumption on the correctness of the algorithms and discuss the pre-filtering process that the original work proposes to prune redundant nodes. Our experimental study on both real and synthetic data substantiates our conclusions.
- R. Agrawal, A. Borgida, and H. V. Jagadish. Efficient management of transitive relationships in large data and knowledge bases. In Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, pages 253--262, 1989. Google Scholar
Digital Library
- N. Bruno, N. Koudas, and D. Srivastava. Holistic twig joins: optimal XML pattern matching. In Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, pages 310--321, 2002. Google ScholarDigital Library
- L. Chen, A. Gupta, and M. E. Kurul. Stack-based algorithms for pattern matching on DAGs. In Proceedings of the 31st International Conference on Very Large Data Bases, pages 493--504, 2005. Google ScholarDigital Library
- J. Cheng, J. X. Yu, and P. S. Yu. Graph pattern matching: A join/semijoin approach. IEEE Transactions on Knowledge and Data Engineering, 23(7):1006--1021, 2011. Google ScholarDigital Library
- A. Schmidt, F. Waas, M. Kersten, M. J. Carey, I. Manolescu, and R. Busse. Xmark: a benchmark for XML data management. In Proceedings of the 28th International Conference on Very Large Data Bases, pages 974--985, 2002. Google ScholarDigital Library
- H. Wang, J. Li, J. Luo, and H. Gao. Hash-based subgraph query processing method for graph-structured XML documents. Proceedings of the VLDB Endowment, 1(1):478--489, 2008. Google ScholarDigital Library
- H. Wang, J. Li, W. Wang, and X. Lin. Coding-based join algorithms for structural queries on graph-structured XML document. World Wide Web, 11(4):485--510, 2008. Google ScholarDigital Library
- H. Wu, T. W. Ling, G. Dobbie, Z. Bao, and L. Xu. Reducing graph matching to tree matching for XML queries with ID references. In Proceedings of the 21st International Conference on Database and Expert Systems Applications: Part II, pages 391--406, 2010. Google ScholarDigital Library
Index Terms
- Comments on "Stack-based Algorithms for Pattern Matching on DAGs"
Recommendations
Stack-based algorithms for pattern matching on DAGs
VLDB '05: Proceedings of the 31st international conference on Very large data basesExisting 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 ...
DAGmaps and ε-visibility representations of DAGs
GD'09: Proceedings of the 17th international conference on Graph DrawingDAGmaps are space filling visualizations of DAGs that generalize treemaps. Deciding whether or not a DAG admits a DAGmap is NP-complete. Recently we defined a special case called one-dimensional DAGmap where the admissibility is decided in linear time. ...
On Families of Planar DAGs with Constant Stack Number
Graph Drawing and Network VisualizationAbstractA k-stack layout (or k-page book embedding) of a graph consists of a total order of the vertices, and a partition of the edges into k sets of non-crossing edges with respect to the vertex order. The stack number of a graph is the minimum k such ...
Comments