Stack-based Algorithms for Pattern Matching on DAGs

Summary: Stack-based algorithms evaluate path, twig, and DAG pattern queries directly on DAGs, avoiding transitive-closure and path-index materialization. They provide sound, complete, and experimentally validated processing with runtime quadratic in the average query-binding size. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 9521
Venue: VLDB
Year: 2005
Pagerank: 0.00018350865
Overall Rank: 444 | 96.96%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Li Chen (University of California San Diego)
2. Amarnath Gupta (University of California San Diego)
3. M. Erdem Kurul (University of California San Diego)

BibTeX Citation

@article{chen_vldb05,
        title = {{Stack-based Algorithms for Pattern Matching on DAGs}},
        author = {Chen, Li and Gupta, Amarnath and Kurul, M. Erdem},
        journal = {PVLDB},
        series = {{VLDB} '05},
        volume = {31},
        pages = {493--504},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 27 of 27 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
269	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00022786599
294	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022253507
322	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00021275303
370	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019937972
746	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00014402233
1,128	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.0001206219
1,533	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010467148
1,796	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	9.7380494e-05
2,575	K-Reach: Who is in Your Small World	2012	VLDB	8.3982298e-05
2,718	Graph Homomorphism Revisited for Graph Matching	2010	VLDB	8.209788e-05
3,021	SCARAB: Scaling Reachability Computation on Large Graphs	2012	SIGMOD	7.8401031e-05
3,278	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	7.5712342e-05
3,979	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.9754185e-05
4,066	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB	6.9298871e-05
5,044	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	6.3883109e-05
5,590	Microblog Entity Linking with Social Temporal Context	2015	SIGMOD	6.1557283e-05
5,724	An Optimal Labeling Scheme for Workflow Provenance Using Skeleton Labels	2010	SIGMOD	6.108728e-05
7,180	Nearest Keyword Search in XML Documents	2011	SIGMOD	5.6798251e-05
7,390	Querying and Monitoring Distributed Business Processes	2008	VLDB	5.626643e-05
7,494	Hash-based Subgraph Query Processing Method for Graph-structured XML Documents	2008	VLDB	5.6043267e-05
7,622	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	5.5806644e-05
7,664	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB	5.5720259e-05
8,871	MatCo: Computing Match Cover of Subgraph Query over Graph Data	2025	SIGMOD	5.35418e-05
9,132	HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs	2023	SIGMOD	5.31719e-05
12,352	Comments on "Stack-based Algorithms for Pattern Matching on DAGs"	2012	VLDB	5.093636e-05
13,741	MEDIALIFE: From Images to a Life Chronicle	2009	SIGMOD	-
13,835	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
163	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027839792
175	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00027226333
187	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00026138589
282	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.0002242162
341	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00020704572
470	Query Optimization for XML	1999	VLDB	0.00017965707
718	Covering Indexes for Branching Path Queries	2002	SIGMOD	0.00014642961
1,658	Finding Regular Simple Paths in Graph Databases	1989	VLDB	0.00010092304

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,490	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD
2	4,360	Efficient External-Memory Bisimulation on DAGs	2012	SIGMOD
3	746	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD
4	4,113	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD
5	4,703	Finding Patterns in a Knowledge Base using Keywords to Compose Table Answers	2014	VLDB
6	4,986	Querying Graph Patterns	2011	PODS
7	4,066	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB
8	175	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD
9	4,221	Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs	2008	SIGMOD
10	12,352	Comments on "Stack-based Algorithms for Pattern Matching on DAGs"	2012	VLDB