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: 9331
Venue: VLDB
Year: 2005
Pagerank: 0.00023592024
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
280	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00029092277
334	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00027077424
377	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00025074538
460	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022679846
784	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016648392
1,419	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00012072488
1,776	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.0001058029
1,879	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010227906
2,762	K-Reach: Who is in Your Small World	2012	VLDB	8.1614818e-05
2,943	Graph Homomorphism Revisited for Graph Matching	2010	VLDB	7.8463193e-05
3,130	SCARAB: Scaling Reachability Computation on Large Graphs	2012	SIGMOD	7.5054361e-05
3,676	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	6.8500097e-05
4,360	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB	6.2486086e-05
4,478	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.1452192e-05
5,488	Microblog Entity Linking with Social Temporal Context	2015	SIGMOD	5.4798261e-05
5,548	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	5.4445937e-05
5,816	An Optimal Labeling Scheme for Workflow Provenance Using Skeleton Labels	2010	SIGMOD	5.3158435e-05
6,842	Querying and Monitoring Distributed Business Processes	2008	VLDB	4.904836e-05
7,313	Nearest Keyword Search in XML Documents	2011	SIGMOD	4.7599924e-05
7,362	Hash-based Subgraph Query Processing Method for Graph-structured XML Documents	2008	VLDB	4.7469116e-05
7,588	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	4.6996269e-05
7,761	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB	4.6543114e-05
9,042	HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs	2023	SIGMOD	4.3997447e-05
9,726	MatCo: Computing Match Cover of Subgraph Query over Graph Data	2025	SIGMOD	4.2901665e-05
12,164	Comments on “Stack-based Algorithms for Pattern Matching on DAGs”	2012	VLDB	4.1905499e-05
13,555	MEDIALIFE: From Images to a Life Chronicle	2009	SIGMOD	-
13,648	OntoQuest: Exploring Ontological Data Made Easy	2006	VLDB	-

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
172	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00038837872
193	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00035591171
239	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00031581944
255	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00030342925
392	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00024546229
504	Query Optimization for XML	1999	VLDB	0.00021513261
812	Covering Indexes for Branching Path Queries	2002	SIGMOD	0.00016343476
1,445	Finding Regular Simple Paths in Graph Databases	1989	VLDB	0.00011937596

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,958	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	7.8126329e-05
3,675	Efficient External-Memory Bisimulation on DAGs	2012	SIGMOD	6.8500291e-05
784	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016648392
4,584	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD	6.0599995e-05
4,838	Finding Patterns in a Knowledge Base using Keywords to Compose Table Answers	2014	VLDB	5.883146e-05
4,949	Querying Graph Patterns	2011	PODS	5.8090034e-05
4,360	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB	6.2486086e-05
239	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00031581944
4,143	Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs	2008	SIGMOD	6.4096394e-05
12,164	Comments on “Stack-based Algorithms for Pattern Matching on DAGs”	2012	VLDB	4.1905499e-05