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: hcaed985af29849e6
Venue: VLDB
Year: 2005
Pagerank: 0.00017972038
Overall Rank: 453 | 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
274	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00022490994
288	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00021969641
330	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00020838159
382	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019485934
774	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00014083518
1,148	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00011809728
1,563	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010224369
1,849	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	9.5068688e-05
2,563	SCARAB: Scaling Reachability Computation on Large Graphs	2012	SIGMOD	8.2934229e-05
2,604	K-Reach: Who is in Your Small World	2012	VLDB	8.2302549e-05
2,773	Graph Homomorphism Revisited for Graph Matching	2010	VLDB	8.0351713e-05
3,348	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	7.3926236e-05
4,049	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.8302372e-05
4,156	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB	6.774434e-05
5,000	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	6.3202341e-05
5,717	Microblog Entity Linking with Social Temporal Context	2015	SIGMOD	6.0191048e-05
5,748	An Optimal Labeling Scheme for Workflow Provenance Using Skeleton Labels	2010	SIGMOD	6.0079624e-05
7,323	Nearest Keyword Search in XML Documents	2011	SIGMOD	5.5524474e-05
7,533	Querying and Monitoring Distributed Business Processes	2008	VLDB	5.5003978e-05
7,635	Hash-based Subgraph Query Processing Method for Graph-structured XML Documents	2008	VLDB	5.4785904e-05
7,752	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB	5.4595236e-05
7,768	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	5.4558207e-05
9,030	MatCo: Computing Match Cover of Subgraph Query over Graph Data	2025	SIGMOD	5.2340466e-05
9,303	HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs	2023	SIGMOD	5.1978865e-05
12,643	Comments on "Stack-based Algorithms for Pattern Matching on DAGs"	2012	VLDB	4.9793485e-05
14,052	MEDIALIFE: From Images to a Life Chronicle	2009	SIGMOD	-
14,146	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
166	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027254612
178	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026628894
192	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00025659453
294	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00021927874
351	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00020251513
482	Query Optimization for XML	1999	VLDB	0.00017598607
740	Covering Indexes for Branching Path Queries	2002	SIGMOD	0.00014325275
1,597	Finding Regular Simple Paths in Graph Databases	1989	VLDB	0.0001012429

Semantically Similar Papers

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