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.00017963727
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.00022480767
289	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00021960834
330	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00020828552
382	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019477423
776	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00014076975
1,150	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00011804185
1,563	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010219537
1,850	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	9.502574e-05
2,563	SCARAB: Scaling Reachability Computation on Large Graphs	2012	SIGMOD	8.2895644e-05
2,606	K-Reach: Who is in Your Small World	2012	VLDB	8.2264537e-05
2,774	Graph Homomorphism Revisited for Graph Matching	2010	VLDB	8.0313907e-05
3,348	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	7.3891319e-05
4,050	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.8270039e-05
4,156	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB	6.7712336e-05
5,004	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	6.3172422e-05
5,718	Microblog Entity Linking with Social Temporal Context	2015	SIGMOD	6.0162555e-05
5,749	An Optimal Labeling Scheme for Workflow Provenance Using Skeleton Labels	2010	SIGMOD	6.0051184e-05
7,326	Nearest Keyword Search in XML Documents	2011	SIGMOD	5.5500332e-05
7,539	Querying and Monitoring Distributed Business Processes	2008	VLDB	5.497794e-05
7,641	Hash-based Subgraph Query Processing Method for Graph-structured XML Documents	2008	VLDB	5.475997e-05
7,756	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB	5.4570169e-05
7,777	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	5.4532403e-05
9,038	MatCo: Computing Match Cover of Subgraph Query over Graph Data	2025	SIGMOD	5.2315688e-05
9,312	HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs	2023	SIGMOD	5.1954259e-05
12,649	Comments on "Stack-based Algorithms for Pattern Matching on DAGs"	2012	VLDB	4.9769913e-05
14,057	MEDIALIFE: From Images to a Life Chronicle	2009	SIGMOD	-
14,151	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.00027241844
179	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026617591
193	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00025647819
294	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00021917638
351	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00020241971
482	Query Optimization for XML	1999	VLDB	0.00017590408
741	Covering Indexes for Branching Path Queries	2002	SIGMOD	0.00014318553
1,597	Finding Regular Simple Paths in Graph Databases	1989	VLDB	0.00010119507

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,535	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD
2	4,434	Efficient External-Memory Bisimulation on DAGs	2012	SIGMOD
3	776	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD
4	4,201	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD
5	4,809	Finding Patterns in a Knowledge Base using Keywords to Compose Table Answers	2014	VLDB
6	5,099	Querying Graph Patterns	2011	PODS
7	4,156	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB
8	179	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,649	Comments on "Stack-based Algorithms for Pattern Matching on DAGs"	2012	VLDB