Database Paper Browser

Back to papers

Stack-based Algorithms for Pattern Matching on DAGs

Summary: Stack-based algorithms for path, twig, and DAG pattern queries on DAGs, without precomputing transitive closure or path indexes. Optimal quadratic runtime in average binding size; soundness and completeness proven; experimental results validate practicality. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
9330
Venue
VLDB
Year
2005
Pagerank
0.00023598882
Overall Rank
425 | 97.05%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 27 of 27 citing papers.

Rank Citing Paper Year Venue Pagerank
279 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD 0.00029113513
334 Fast and Practical Indexing and Querying of Very Large Graphs 2007 SIGMOD 0.00027081079
376 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00025097452
461 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD 0.00022499343
788 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD 0.00016650034
1,414 Graph Pattern Matching: From Intractable to Polynomial Time 2010 VLDB 0.00012118275
1,777 Reachability Queries on Large Dynamic Graphs: A Total Order Approach 2014 SIGMOD 0.00010589591
1,880 TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph 2013 SIGMOD 0.00010226347
2,756 K-Reach: Who is in Your Small World 2012 VLDB 8.1682536e-05
2,938 Graph Homomorphism Revisited for Graph Matching 2010 VLDB 7.8524059e-05
3,127 SCARAB: Scaling Reachability Computation on Large Graphs 2012 SIGMOD 7.5046522e-05
3,671 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB 6.8560247e-05
4,364 Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents 2006 VLDB 6.2546168e-05
4,478 Reachability Querying: An Independent Permutation Labeling Approach 2014 VLDB 6.1506256e-05
5,479 Microblog Entity Linking with Social Temporal Context 2015 SIGMOD 5.4850984e-05
5,540 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 5.4498271e-05
5,802 An Optimal Labeling Scheme for Workflow Provenance Using Skeleton Labels 2010 SIGMOD 5.3209459e-05
6,844 Querying and Monitoring Distributed Business Processes 2008 VLDB 4.9095428e-05
7,315 Nearest Keyword Search in XML Documents 2011 SIGMOD 4.7645064e-05
7,367 Hash-based Subgraph Query Processing Method for Graph-structured XML Documents 2008 VLDB 4.7514687e-05
7,584 Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012 VLDB 4.7041255e-05
7,762 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 4.6583829e-05
9,042 HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs 2023 SIGMOD 4.4039656e-05
9,727 MatCo: Computing Match Cover of Subgraph Query over Graph Data 2025 SIGMOD 4.2942813e-05
12,156 Comments on “Stack-based Algorithms for Pattern Matching on DAGs” 2012 VLDB 4.1945683e-05
13,542 MEDIALIFE: From Images to a Life Chronicle 2009 SIGMOD -
13,634 OntoQuest: Exploring Ontological Data Made Easy 2006 VLDB -
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
171 Algorithmics and Applications of Tree and Graph Searching 2002 PODS 0.00038830709
193 On Supporting Containment Queries in Relational Database Management Systems 2001 SIGMOD 0.00035610321
240 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD 0.00031603463
246 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD 0.00030949575
391 Indexing and Querying XML Data for Regular Path Expressions 2001 VLDB 0.00024564567
501 Query Optimization for XML 1999 VLDB 0.00021530411
817 Covering Indexes for Branching Path Queries 2002 SIGMOD 0.00016352717
1,444 Finding Regular Simple Paths in Graph Databases 1989 VLDB 0.00011946075
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,957 Computing Label-Constraint Reachability in Graph Databases 2010 SIGMOD 7.8198686e-05
3,677 Efficient External-Memory Bisimulation on DAGs 2012 SIGMOD 6.8533416e-05
788 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD 0.00016650034
4,587 On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques 2005 SIGMOD 6.0658154e-05
4,838 Finding Patterns in a Knowledge Base using Keywords to Compose Table Answers 2014 VLDB 5.8887949e-05
4,946 Querying Graph Patterns 2011 PODS 5.8149362e-05
4,364 Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents 2006 VLDB 6.2546168e-05
240 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD 0.00031603463
4,143 Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs 2008 SIGMOD 6.4129418e-05
12,156 Comments on “Stack-based Algorithms for Pattern Matching on DAGs” 2012 VLDB 4.1945683e-05