Comments on "Stack based Algorithms for Pattern Matching on DAGs"
In this paper, the authors 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, they investigate the major results of that paper, pointing out several discrepancies and proposing solutions to resolving them. They show that the original algorithms do not find particular types of query solutions that are common in practice. They 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.